HOMEWORK (chapter 3: informed search)

Q-1: Prove each of the following statements, or give a counterexample:

- Breadth-first search is a special case of uniform-cost search.

- Depth-first search is a special case of best-first tree search.

- Uniform-cost search is a special case of A* search.

Q-3: n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n x n grid. The vehicles must be moved to the top row but in reverse order; so the vehicle i that starts in (i, 1) must end up in (n – i + 1, n). On each time step, every one of the n vehicles can move one square up, down, left, or right, or stay put; but if a vehicle stays put. one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannot occupy the same square.

- Calculate the size of the state space as a function of n.

- Calculate the branching factor as a function of n.

- Suppose that vehicle i is at (xi, yi): write a
nontrivial admissible heuristic h, for the number of moves it will
require to get to its goal location (n – r + 1, n), assuming no other
vehicles are on the grid.

- Which of the following heuristics are admissible for the problem of moving all n vehi-cles to their destinations? Explain.

(ii) max{h1,h2,...,hn)

(iii) min{h1,h2,...,hn)