CIS 579 Machine Problem 2

Summer 2004

For your second assignment, you are to write a program (using Lisp or some other language) that will allow you to examine the effectiveness of the A* search algorithm compared to that of ordinary branch and bound search. The problem to be solved is a simplified (2 disk) version of the Towers of Hanoi.

In this version of the Towers problem, there are 3 pegs and two disks. Both disks start on peg 1 and must be moved to peg 3, subject to the usual constraints. (You can only move one disk at a time and you may never place a larger disk on top of a smaller disk). There are only 9 legal states for this problem.

To use A* you will need an estimate of the cost of traversing each path and an underestimate of the distance remaining to the goal state. For cost of path traversal you may use path length.

You are left to your own devices to design a measure that uses underestimates of the remaining distance to the goal.

You will need to devise an expand function that does not rely on hard coded problem state relations. You will also need to devise a data structure for the nodes in the problem state space. Using an ordered pair (big.disk.peg small.disk.peg) might be one possibility, but array would also work. It may also prove to be helpful to rethink the structure of the elements in the queue of partial paths. It may be wise to store the accumulated cost and the underestimate as part of the path stored in the queue.

You will need to turn in a well-commented program listing, sample runs (with neatly organized output), and a memo discussing your solution. In your memo you should describe your rationale for choosing the particular branch and bound algorithm variation that you did (including the operational definitions of your measures).

Assigned: 5/19/04

Due date: 6/07/04