CSE571 Homework2 Solution

Only typed answers will be accepted.

Exercise 1.1 
Prove each of the following statements, or give a counterexample:
a. Breadth-first search is a special case of uniform-cost search.
b. Depth-first search is a special case of best-first search.
c. Uniform-cost search is a special case of A search. Exercise 1.2 (18pt)
from textbook
Consider the unbounded version of the regular 2D grid shown above. The start state is at the origin, (0, 0), and the goal state is at (x, y). The agent can choose action North, South, East, West or Stay in any state. Consider tree search below (unless noted otherwise):

a. What is the branching factor b?
b. How many distinct states are there at depth k (for k > 0) in the search tree?
c. What is the maximum number of nodes expanded by breadth-first search?
d. What is the maximum number of distinct nodes expanded by breadth-first search?
e. What is the maximum number of nodes expanded by breadth-first graph search?
f. Is h = |u − x| + |v − y| an admissible heuristic for a state at (u, v)? Explain.
g. How many nodes are expanded by A graph search using h in (f)?
h. Does h remain admissible if some links are removed? Explain.
i. Does h remain admissible if some links are added between nonadjacent states? Explain.

Exercise 1.3 (15pt)
n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n × n grid. The vehicles must be moved to the top row but in reverse order; 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. Any vehicle is allowed to hop at most one other vehicle at a time. Two vehicles cannot occupy the same square.
a. (2pt) Calculate the size of the state space as a function of n.
b. (2pt) Calculate the branching factor as a function of n.
c. (2pt) Suppose that vehicle i is at (xi, yi); write a nontrivial admissible heuristic hi for the number of moves it will require to get to its goal location (n−i+1, n), assuming no other vehicles are on the grid.
d. (9pt) Which of the following heuristics are admissible for the problem of moving all n vehicles to their destinations? Explain either way for each proposal below.
(i) åi hi
(ii) max {h1 ... hn}
(iii) min {h1 ... hn}

Exercise 1.4 (11pt)
from wiki
Once upon a time a farmer went to a market and purchased a wolf, a goat, and a cabbage. On his way home, the farmer came to the bank of a river and rented a boat. But crossing the river by boat, the farmer could carry only himself and a single one of his purchases: the wolf, the goat, or the cabbage.
If left unattended together, the wolf would eat the goat, or the goat would eat the cabbage.
The farmer's challenge was to carry himself and his purchases to the far bank of the river, leaving each purchase intact. He also wants to make as fewer trips as possible.

a. (7pt) Formulate this puzzle as a search problem.
b. (4pt) Design at least two non-trivial admissible heuristics and explain.