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-2: Apply A* to a 8-puzzle problem instance using the Mahanttan-distance heuristic. Is the solution found optimal?
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.