Experiment1: Search
实验资料 实验源码

Experimental Requirements

In this experiment, I should design and implement A-Star algorithm in Python and apply it to two problems——Fifteens Puzzle & Superqueens. Based on the helper code, I need to fill in the missing parts to complete the algorithm. I need to code up the function Astar in search.py and a few methods(is_goal, generate_children, evaluate_heuristic) of the FifteensNode and SuperqueensNode classes.

Configuration

I coded up the algorithm and run it on vscode(Visual Studio Code) with the python package of edition 3.9.6. Additionally, I store my code on gitee in case of need.

Implementation

Fifteens Puzzle

As for Problem Fifteens Puzzle, I need to start with initial state and implement the A-Star algorithm to reach the goal state, the process of which made up of several moves is as follows. Each move has a cost of 1. Plus, I need to find the optimal solution composed of optimal moves.

Here is the initial state, for example, and the goal state:

1

2

The initial state is just one move away from the goal state.

Whether the initial state is able to reach the goal state or not depends on its inversion number. Approximately half of these states will succeed. On finding the next move, we should firstly check if the current state is the goal state using the method is_goal(self). If not, we will get a list of child nodes generated by method generate_children(self) after trying all 4 possible moves of the empty cell. Before moving to the next state, we should estimate the minimum number of moves required to reach the goal state from this node with the method evaluate_heuristic(self). By carrying out the A-Star algorithm, we can find the optimal solution to this problem theoretically.

is_goal: to check if the current state is the goal state.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
return (self.board[0][0]==1 and 
self.board[0][1]==2 and
self.board[0][2]==3 and
self.board[0][3]==4 and
self.board[1][0]==5 and
self.board[1][1]==6 and
self.board[1][2]==7 and
self.board[1][3]==8 and
self.board[2][0]==9 and
self.board[2][1]==10 and
self.board[2][2]==11 and
self.board[2][3]==12 and
self.board[3][0]==13 and
self.board[3][1]==14 and
self.board[3][2]==15 and
self.board[3][3]==0)

generate_child(self): to get a list of child nodes.

Firstly find the empty position by loop. Then try out 4 possible moves namely up, down, left and right to generate the list. At last return the children list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
empty_x=0; # column
empty_y=0; # row
for i in range(len(self.board)):
for j in range(len(self.board[i])):
if self.board[i][j]==0:
empty_x=i
empty_y=j
# Taking going up as an example
if empty_y != 0:
newBoard=copy.deepcopy(self.board)
newBoard[empty_x][empty_y]=newBoard[empty_x][empty_y-1]
newBoard[empty_x][empty_y-1]=0
childNode1=FifteensNode(parent=self,g=self.g+1,board=newBoard)
children.append(childNode1)
# Moving down, left and right are similar to moving up.

evaluate_heuristic(self): to estimates the number of moves required to reach the goal state from current state.

1
2
3
4
5
6
7
8
9
10
11
h=0
for i in range(len(self.board)):
for j in range(len(self.board[i])):
if self.board[i][j]!=0:
row_diff=abs(i-int((self.board[i][j]-1)/4))
if self.board[i][j]%4==0:
col_diff=abs(j-3)
else:
col_diff = abs(j - (self.board[i][j] % 4 - 1))
h=h+row_diff+col_diff
return h

Superqueens Puzzle

As for Problem Superqueens Puzzle, I need to start with the initial state, remove the existing attacks and implement the A-Star algorithm to reach the goal state. I should guarantee each row and each column can have at most one superqueen and try to minimize the number of pairs of superqueens that attack each other (either diagonally or with a knight’s move).

Here is the initial state, for example. There are three attacks in the state.

3

On finding the next state, we should firstly check if the current state is the goal state using the method is_goal(self). If not, we will get a list of child nodes generated by method generate_children(self) after adding a new superqueen. By carrying out the A-Star algorithm, we can find the optimal solution to this problem theoretically.

is_goal(self): to check if the current state is the goal state.

1
2
3
# if the number of placed superqueens is equal to n, return true
if len(self.queen_positions)==self.n: return True
return False

generate_children(self): to generate children by adding a new superqueen.

Firstly get the number of placed superqueens as well as the column of the next queen.

1
2
3
4
5
6
7
column=len(self.queen_positions)  
for row in range(self.n):
isEmpty=True
for i in self.queen_positions:
if i[0]==row:
isEmpty=False
break

Then find the empty row by loop and keep the constraint either diagonally or with a knight’s move. Finally return the children list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if isEmpty: 
updated_queens_positions=copy.deepcopy(self.queen_positions)
updated_queens_positions.append((row, column))

updated_g = self.g
new_row = row
new_col = column
# 对角线冲突
while new_row > 0 and new_col > 0:
new_row = new_row-1
new_col = new_col-1
if (new_row, new_col) in self.queen_positions:
updated_g = updated_g + 1
# 次对角线冲突
# 骑士走法冲突 4种
new_row = row-2
new_col = column-1
if (new_row, new_col) in self.queen_positions:
updated_g = updated_g + 1

A-Star Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fringe = [root]
visited = []
while fringe:
min = 0
# 找到消耗最少的子状态
for i in range(len(fringe)):
if fringe[i].f < fringe[min].f:
min = i
# 若该子状态没有被访问过 则到达该状态
exploreNode = fringe.pop(min)
if exploreNode._get_state() not in visited:
visited.append(exploreNode._get_state())
# 如果是目标状态 返回
if exploreNode.is_goal():
return exploreNode.get_path()
else:
# 反之将该状态生成的若干个子状态添加到序列中
fringe.extend(exploreNode.generate_children())
return None

Result Analysis

4

5

Conclusion

In this experiment, I learnt how to design and implement A-Star algorithm. Plus I can solve some problems such as Fifteens Puzzle and Superqueens Puzzle by carrying out this algorithm. I’ve got a advanced apprehension of heuristic search algorithm especially the importance of heuristic function. It’s crucial to design a optimal heuristic function when using the search algorithm. A-Star algorithm helps to find optimal solution efficiently and precisely.

Additionally, it’s the first time for me to use python coding up the algorithm. I need to search plenty of information on the Internet during the process to make sure the code is correct. Looks like I’ve got a lot to learn.