1. 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.
a. Draw the search tree showing all nodes generated by the Breadth-First Search algorithm to solve this problem.
b. Draw the search trees showing all nodes generated for each iteration of the IterativeDeepening Search algorithm to solve this problem.
c. 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.
d. 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.
2. 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.
3. : 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.
