CSE 472/572, Spring 2002

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:

    and whose goal state is:

    showing:

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

DUE: AT THE START OF LECTURE: WED, FEB 27



Copyright © 2002 by William J. Rapaport (rapaport@cse.buffalo.edu)
file: 572/S02/hw4.12fb02.html