CSE    571  Homework    2

CSE    571 
Homework    2

Only    typed    answers    will    be accepted.    
Be    precise    and    concise    in    your    answers. You    may add    hand-drawn    figures    when    necessary.    
Exercise    1.1    (6pt)
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.