Question 1
◆
For the Sudoku problem in week 8’s exercise, use the local search with hill climbing to solve it (please give intermediate assignments and how many constraints they violate). Let us say the rule of hill climbing is that 1) always consider the variable which violates the most constraints and 2) swap that variable’s value with a cell, such that the total number of violated constraints can be reduced most. Suppose a randomly generated initial assignment is below (in red). (to simplify the calculation, let us say cell tie is broken first from top to bottom and then from left to right, and number tie is broken numerically)
Local search:
◆ Start with an (arbitrary) complete
assignment, so constraints can be violated.
◆ Try to improve the assignment iteratively based on some rule.
◆
3
4
1
2
1
2
3
2
4
3
1
3
4
2
4
1
Question 1
◆ Rule
◆ 1) always consider the variable which violates the most constraints,
◆ 2) swap that variable’s value with a cell, such that the total number of violated constraints can be reduced most.
3
4
1
2
1
2
3
2
4
3
1
3
4
2
4
1
1
2
0
0
3
2
1
2
1
3
1
1
if swap Cell24 with Cell13, in total 18
if swap Cell24 with Cell21, in total 18
Number of the constraints each cell violates; in total 17 constraints violated
if swap Cell24 with Cell23, in total 17
3
4
1
2
2
2
3
1
4
3
1
3
4
2
4
1
2
0
2
0
2
2
1
2
1
3
1
2
3
4
1
2
1
2
2
3
4
3
1
3
4
2
4
1
1
1
0
2
1
2
1
2
2
3
1
1
3
4
2
2
1
2
3
1
4
3
1
3
4
2
4
1
2
2
1
0
2
2
1
1
1
3
1
2
if swap Cell24 with Cell41, in total 11
3
4
1
2
1
2
3
4
4
3
1
3
2
2
4
1
1
0
0
0
0
0
1
2
1
2
3
1
……………………..
……………………..
Cell24 is the cell to be considered first
This swap reduces violated constraints most
Question 1
◆ Rule
◆ 1) always consider the variable which violates the most constraints,
◆ 2) swap that variable’s value with a cell, such that the total number of violated constraints can be reduced most.
3
4
1
2
1
2
3
4
4
3
1
3
2
2
4
1
1
0
0
0
0
0
1
2
1
2
3
1
3
1
4
2
4
2
1
3
1
3
2
4
2
4
3
1
0
0
0
0
0
0
0
0
0
0
0
0
Number of the constraints each cell violates; in total 11 constraints violated
Cell42 is the cell to be considered first
if swap Cell42 with Cell33, in total 4
This swap reduces violated constraints most
3
4
1
2
1
2
3
4
4
3
2
3
2
1
4
1
0
0
0
0
0
0
1
0
1
0
1
1
……………………..
Next iteration:
……………………..
……………………..
if swap Cell32 with Cell42, in total 0
……………………..
Question 1
◆ Rule
◆ 1) always consider the variable which violates the most constraints,
◆ 2) swap that variable’s value with a cell, such that the total number of violated constraints can be reduced most.
◆ We can always design different rules, different search strategies (the above strategy might not be the best one because it seems very greedy).
◆ We can also initialise multiple assignments and deal with them in a parallel way, like in population-based search.
Question 2
◆ Crossover and mutation are two components in genetic algorithms. Are they both necessary? can we remove one of them during the search?
Single-point
Parents crossover Offspring
0
1
1
1
0
1
1
0
0
0
0
0
0
0
0
1
Bit flip
Parent mutation Offspring
◆ Mutation is necessary since it can ensure that every part of the search space can be reached, whereas crossover only exchange the existing genes.
0
1
0
1
0
1
1
1
Question 3
◆ Question 3.1. Give the minimax value at each node for the game tree below.
8
Min 8 4
8 20 4
Max
Max
15
8
5
20
3
2
4
15
6
Question 3
◆ Question 3.2. Find the nodes of the above tree pruned by alpha-beta pruning algorithm. Assuming child nodes are visited from left to right. There are four layers and you can use L𝑚-𝑛 to denote the 𝑛th node from left to right in the layer 𝑚, e.g., the first node (with value 8) at the bottom layer can be denoted by L4-1.
Max Min
Max
V>=8
8
5
Question 3
◆ Question 3.2. Find the nodes of the above tree pruned by alpha-beta pruning algorithm. Assuming child nodes are visited from left to right. There are four layers and you can use L𝑚-𝑛 to denote the 𝑛th node from left to right in the layer 𝑚, e.g., the first node (with value 8) at the bottom layer can be denoted by L4-1.
Max Min
Max
8
V<=8
V>=20
8
5
20
Question 3
◆ Question 3.2. Find the nodes of the above tree pruned by alpha-beta pruning algorithm. Assuming child nodes are visited from left to right. There are four layers and you can use L𝑚-𝑛 to denote the 𝑛th node from left to right in the layer 𝑚, e.g., the first node (with value 8) at the bottom layer can be denoted by L4-1.
Max Min
Max
V>=8
8
8
V>=20
V>=2
8
5
20
2
4
Question 3
◆ Question 3.2. Find the nodes of the above tree pruned by alpha-beta pruning algorithm. Assuming child nodes are visited from left to right. There are four layers and you can use L𝑚-𝑛 to denote the 𝑛th node from left to right in the layer 𝑚, e.g., the first node (with value 8) at the bottom layer can be denoted by L4-1.
Max Min
Max
V>=8
8
8 V>=20
V<=4
4
8
5
20
2
4
Question 3
◆ Question 3.2. Find the nodes of the above tree pruned by alpha-beta pruning algorithm. Assuming child nodes are visited from left to right. There are four layers and you can use L𝑚-𝑛 to denote the 𝑛th node from left to right in the layer 𝑚, e.g., the first node (with value 8) at the bottom layer can be denoted by L4-1.
Max Min
Max
8
8 V>=20
8
V<=4
4
8
5
20
The pruned nodes: L4-4, L3-4, L4-7, L4-8
2
4