For your second assignment, you are to write a program that compares the use of the branch and bound algorithms to solve a puzzle. My preference is that your program should use A* and ordinary Branch and Bound to solve the string permutation problem described below, but you may use any two branch and bound algorithms if you wish.

In this problem the task is to transform a string like "ART---" into some goal string like "---TAR". The "-" denotes an open position. The only operational constraints for moving characters are:

1. Only one character may be moved at a time.
2. Characters may be pushed into an adjacent open space immediately to the right of its current position.
3. Characters may be jumped over one another to the right like in checkers (e.g. to an open space to the right of a character adjacent to the one being jumped).

You may use any language you wish for your solution. As part of your solution, you might define a function Solve which would take an initial state and a final state as an input arguments, and Then returns a list of moves in the optimal solution to the problem. For example, if you were using Lisp, the function call:

  (SOLVE '(A R T - - -) '(- - - T A R)) 

might return the following:

  ((A R T - - -) (A - T R - -) (- A T R - -) (- A T - R -) (- A - T R -) (- - A T R -) (- - A T - R) (- - - T A R))

Ideally, your program should be able to handle strings of any length greater than 2. Impossible problems, (SOLVE '(N O - -) '(O N - -)), should have NIL or some appropriate message returned as their solution.

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 which underestimates 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 (an ordered list like shown above might be helpful, but a string or 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). In your memo you should discuss the relative effectiveness of A* to Branch & Bound using quantifiable language (as evidenced by your sample runs.

Assigned: 5/17/06
Due date: 6/05/06