Description

CptS 440/540 Artificial Intelligence
Homework 3

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, Right, Down, Left. 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 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. 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. Take Quiz 3 on Canvas. You have multiple attempts. Your answers will be graded, but the main point of this exercise is to make sure you are setup to take an exam via Canvas.

3. CPTS 540 Students Only: Given that CityBlockDistance is an admissible heuristic for the 8-puzzle problem, answer the following:
a. Is (CityBlockDistance – 1) an admissible heuristic for the 8-puzzle problem? Justify your answer.
b. Is (CityBlockDistance + 1) an admissible heuristic for the 8-puzzle problem? Justify your answer.

1