# ICS 171: Homework #5

1. (50) Solve your Towers of Hanoi problem with breadth first search, depth first search (if possible), depth first search with a depth limit (of 10) and depth first search with duplicate node detection. Record the amount of time (nodes-visited) and space (maximum length of the node list) for each algorithm. What are the advantages and disadvantages of each on this problem and in general. The code for all search functions can be found in the file blind-search.lisp Your discussion should focus on
• Completeness (Can it always find a solution if one exists?)
• Optimality (Can it always find the shortest solution?)
• Time Complexity (Number of nodes visited.)
• Space Complexity (Maximum length of the node list.)

2. (50) Implement depth-first iterative deepening search (see lecture notes and/or section 12.5) and test it on the Towers of Hanoi problem. Hint: One way is to use a loop with a thereis condition calling depth-first-search-with-depth-limit. If your solution is more than 5 lines long, you're making this much too complicated.

STUDY Tip:

You can get a graphic display of the cities used in the train problem.

To do this:

3. load mac-map-grapher.lisp if you are using a mac or load sun-mac-grapher.fasl if you are on a Sun

On the Mac, a search menu will appear on the menu bar. You can select any search function, any start and any goal state and watch it solve the search problems. On the Sun, you must call the search functions as normal from lisp, but will see the search space graphed. By default, it will pause after expanding a state, and wait for you to type "p" to proceed, or "n" to proceed and permanently turn off pausing.

Extra Credit Problem #1: Bi-directional search

In class, we have studied search methods that start at an initial state and apply operators that expand states until a goal state is found. Why not start at the goal state and apply the inverse of operators to get to the start state? Even better, why not apply operators to the start state doing breadth first search and apply the inverse of operators from the goal state doing breadth first search and stop searching when you get to some state from the start state and from the goal state. This is called bi-directional search.

Some potential problems:

1. Not all problems have a unique goal state

2. Not all operators have inverses (e.g., you can't take 3 gallons of water out of the four gallon jug and put in the faucet).

Nonetheless, when applicable, bi-directional search may be better than breadth-first search.

What is the time and space complexity of this method in terms of b (branching factor) and d (depth of shortest solution)? Implement it, and for each of the following problems, indicate whether it is applicable, and if so, compare its time and space complexity to breadth-first.

Test it on the train-problem.lisp, farmer-wolf-goat-cabbage.lisp, jug-problem.lisp, 8puzzle.lisp and your Towers of Hanoi problem if possible.

Back to http://www.ics.uci.edu/~pazzani/171-p.html (text only) or http://www.ics.uci.edu/~pazzani/171.html .

Michael Pazzani
Department of Information and Computer Science,
University of California, Irvine
Irvine, CA 92717-3425
pazzani@ics.uci.edu