I am doing the following question:
- Consider the 3-puzzle problem, where the board is a 2X2 matrix. There are three tiles numbered 1,2, and 3, and there is one blank tile. There are four operators that move the blank up, down, left, or right. The start and goal states are given in the following figure. With the help of search trees, show how a path to the goal can be found using:
a. depth first search (3 marks)
b. breadth first search (3 marks)
c. A* search with the heuristic being the sum of the number of moves and the number of misplaced tiles. (3 marks)
If a search method does not find a solution, explain why it does not. (2 marks)
START state
2 3
1 _
GOAL state
1 2
3 _
Obviously as you move to one state from another, you can move from that state to a new one or to the state that you have just moved from (due to the nature of the operators), in the search tree do we re-state the nodes that we have already branched from? In other words, if you are at stage 4 would you re-state a node at stage 3?
