Artificial Intelligence Homework 3

CptS 440/540 Artificial Intelligence
Homework 3

General Instructions: Put your answers to problem 1 (and problem 3 for 540 students) into a PDF document and
upload the document as your submission for 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 Canvas system by the above deadline. Note
that you may submit multiple times, but we will only grade the most recent entry submitted before the deadline.
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.