General Instructions: Put your answers to the following problems into a PDF document and submit as an attachment under Content Homework 3 for the course CptS 440 Pullman (all sections of CptS 440 and 540 are merged under the CptS 440 Pullman section) on the Blackboard Learn system by the above deadline. Note that you may submit multiple times, but we will only grade the most recent entry submitted before the above deadline.
1. Consider the following initial and goal states for the 8-puzzle problem (same as HW1). 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 (different than HW1). Also, be sure to use the search algorithms as defined in the lecture notes.
[NOTE: The repeated states in the frontier are marked by ‘*’ and the goal state is colored red.]
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 Iterative- Deepening 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. Consider a variant to the city-block heuristic that also adds in the city-block distance of the blank tile. Is this heuristic admissible for the 8-puzzle search problem? Justify your answer.
e. 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.
f. CPTS 540 Students Only: Draw the search tree showing all nodes generated by Breadth- First Search to solve the above problem using the actions in order left-to-right (U, U2, D, D2, L, L2, R, R2), where the (U2, D2, L2, R2) actions can move two tiles at once.
g. CPTS 540 Students Only: Is the city-block heuristic described in part (c) admissible for the search problem in part (f)? Justify your answer.
