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:  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.

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.

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

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. 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.

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.

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

A-Star Algorithm

Result Analysis  The implementation time fluctuates between 0.33s and 0.37s which meets my expectations.

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.