HW #4: SEARCH, Part II

1. R & N, Ch. 3, p. 88: #3.6

2. R & N, Ch. 3, p. 90: #3.17 a, b

3. R & N, Ch. 4, p. 118: #4.1

4. In the following state-space tree, the nodes are labelled A-I, the start node is A, the goal nodes are E and I, each node represents a different state, the cost of each operator is shown next to the arc that represents the operator, and the value of the h function applied to each state is shown next to the node label.

   For each search method listed, list the nodes in the order they are chosen for expansion, assuming that each search method only looks for a goal node when the node is chosen for expansion.

                                  A:3
                                 / | \
                                /  |  \
                              2/  1|   \3
                              /    |    \
                             /     |     \
                            B:2   C:2    D:1
                           / |     | \
                          /  |     |  \
                        2/  1|    2|   \3
                        /    |     |    \
                       /     |     |     \
                      E:0   F:1   G:1    H:2
                                   |
                                   |
                                  1|
                                   |
                                   |
                                  I:0
   

   (a) depth-first search
   (b) breadth-first search
   (c) uniform-cost search
   (d) best-first search
   (e) A*

5. Do a complete A* search tree for the 8-puzzle whose initial state is:

   2	8	3
   1	6	4
   7	x	5

   and whose goal state is:

   1	2	3
   8	x	4
   7	6	5

   showing:

   • (a) the priority queue of nodes, together with their f values,

   • (b) the order in which each node is chosen for expansion, and

   • (c) the correct sequence of moves that solves the problem,

   using h_c(n) = P(n) + 3*S(n), where:

   • P(n) = the sum of the city-block distances that each tile is from its "home", and

   • S(n) = the sequence score = for each non-central tile, score 2 for each tile not followed by its correct successor, else score 0, and the central tile scores 1 if not "x".