Description
- Consider the following initial and goal states for the 8-puzzle problem. In the search algorithms below, when iterating over possible actions (i.e., moving the blank tile), always consider the actions in the order: Up, Down, Left, Right. Be sure to use the search algorithms as defined in the lecture notes.
- Draw the search tree showing all nodes generated by the Breadth-First Search algorithm to solve this problem.
- Draw the search trees showing all nodes generated for each iteration of the IterativeDeepening Search algorithm to solve this problem.
- Draw the search tree generated by the A* search algorithm to solve this problem using the city-block distance for the heuristic h. The city-block distance for an 8-puzzle state is the sum of the city-block distances of each tile in the puzzle (excluding the blank tile). Next to every node, show the values of f, g and h. If two nodes have the same f value, then prefer nodes farther to the left in the search tree.
- Draw the search tree generated by the Hill-Climbing search algorithm to solve this problem, where a state’s Value = 1 / (h + 1), where h is the heuristic from part (c). Next to every node, show its Value. Finally, indicate which node is returned. Be careful; note that the Hill-Climbing algorithm does not employ the goal test, but stops only after none of the generated neighbor nodes has a strictly better Value.
- Consider the heuristic which is the average of the city-block distances of each tile, instead of the sum. Is this heuristic admissible for the 8-puzzle search problem? Justify your answer.
- CPTS 540 Students Only: Suppose you want to replace the initial state in problem 1 with a state such that the optimal solution to the 8-puzzle problem is exactly 10 moves. Explain how you could use one of the search algorithms discussed in class to find such a state.
1
