HOMEWORK (chapter 3: informed search)
Q-1: Prove each of the following statements, or give a counterexample:
Q-2: Apply A* to a 8-puzzle problem instance using the Mahanttan-distance heuristic. Is the solution found optimal?
- 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
- 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.