CIS 579 Machine Problem 2

Summer 2007

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 version of the Frogs and Toads puzzle.

In this version of Frogs and Toads, there are an equal number (either 2 or 3) of Frogs and Toads facing one another (F F F * T T T) with one space between them. Frogs and Toads take turn moving. Moves consist of sliding a Frog or Toad into the empty or jumping over an opposing creature (Frogs cannot over themselves and neither can Toads). The object is to have the Frogs and Toads change ends of their world.

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. 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 discuss the relative effectiveness on A* to Branch & Bound using quantifiable language.

Assigned: 5/16/07

Due date: 6/04/07