[SOLVED] CSE571-Homework 2 

Description

Exercise 1.1

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

1. Breadth-first search is a special case of uniform-cost search.
2. Depth-first search is a special case of best-first search.
3. Uniform-cost search is a special case of A Exercise 1.2

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):

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

Exercise 1.3

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.

1. Calculate the size of the state space as a function of n.
2.  Calculate the branching factor as a function of n.
3. Suppose that vehicle i is at (x_i, y_i); write a nontrivial admissible heuristic h_i 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.
4.  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 h_i
   • max {h₁ … h_n}
   • min {h₁ … h_n}

Exercise 1.4

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.