1.  (Uninformed search; 24 points)

(a)  [14  points] Construct a search graph with no more than  10 nodes for which all of the following are true:

i.  Least-cost search returns an optimal solution.

ii.  Depth-first search returns the highest-cost solution.

iii.  Breadth-first search returns a solution whose cost is strictly less than the highest-cost solution and strictly more than the least-cost solution.

Note that this means your search graph must have at least 3 solution paths of differing costs.  (You are allowed to have multiple goal nodes.)  Be sure to include and formally describe each component of the search graph.  If necessary for concreteness, specify the order in which successor paths are added to the frontier by each algorithm.

(b)  [5 points] List the paths that are removed from the frontier by a depth first search of the problem you specified in part (1a), in the order in which they are removed.  The algorithm should stop as soon as it returns a solution.

(c)  [5 points] List the paths that are removed from the frontier by a least cost first search of the problem you specified in part (1a), in the order in which they are removed. The algorithm should stop as soon as it returns a solution.

2.  (Heuristic search; 100 points)

A group of researchers are being chased by zombies through a dark forest late at night. They come to a rope bridge over a ravine.  If they can all get over the bridge before the zombies arrive, they will survive.

At most two people can cross at a time. A person or pair of people can only cross when they have a flashlight with them.  The group has only a single flashlight among them, so one person must bring the flashlight back across the bridge to the starting side before anyone else can cross. Each pair moves at the pace of its slowest member; i.e., the Undergrad and the Professor will take 10 minutes to cross if they go together.

Each person moves at a different pace:

.  The Undergrad can cross the bridge in 1 minute

.  The Grad Student can cross the bridge in 2 minutes

.  The Postdoc can cross the bridge in 5 minutes

.  The Professor can cross the bridge in 10 minutes

How can the whole group get to the other side of the bridge in the shortest possible time?

(a)  [20  points] Represent this problem as a search graph.  Be sure to include and formally describe each component of the search graph.

(b)  [5 points] What is the forward branching factor for your representation from part (2a)? Justify your answer.

(c)  [10 points] Construct an admissible heuristic for this problem that is non-constant (i.e., returns different values for at least two states).

(d)  [5 points] Argue that the heuristic from part (2c) is admissible.

(e)  [60 points] Implement your representation from part (2a) and heuristic from part (2c) in Python 3 by editing the Zombie_problem class in the provided zombie.py.  We will run your code with the command python3  zombie.py. Your code must complete within 2 minutes for full marks.1