Programming A* Search

Your task is to write a Java program that does A* search. Follow the hints and requirements below. Remember that programming assignments are to be done in pairs; if you didn't have a partner the previous one, you are encouraged to have one this time.

You should design the program before you sit at the terminal. Try to break down the code into short, simple, and meaningful methods. This is very important for a good design.

All your code should be put in one file and be well-commented or clearly self-explanatory. You should also provide code for testing your programs as automatically as possible and include instructions for demo/testing.

Submission

Submit a printout of the following items in class on the due date, preferably printed 2 pages per sheet.

1. Your design (what classes and methods you are writing; for each variable, what values they are holding; for each method, what arguments they expect, what they return, and what they are supposed to do, in as few words as possible; no need to write a long description of the method: one or two sentences in English will suffice).
2. Your commented Java source code.
3. A trace of runing your program, as stated in hint 5. Make sure to print out the labels of all the nodes generated, as required in hint 4.

Grading

This homework is worth 5% of the course grade. Exceptionally well-thought-out and well-written homeworks will receive appropriate extra credit. Partial solutions get partial credit, but if you only manage to write some of the components, you should test each of them and hand in the results of the test.

Hints and requirements

1. Start by defining a class Node, which represents a node in the search tree. A node represents a state in the search space, so it is also called state. It should have the following fields. In particular, use 0-1 strings for labels.

     f        // = g+h, estimate of cost for the current node
     g        // cost of getting from the start node to the current node
     h        // estimate of the cost of getting from the current node to a goal node
     parent   // the parent of the current node
     children // the list of children of the current node
     label    // identification (ID) label of the current node 
   

2. Make sure you do an A* search following the Graph-Search steps given in the textbook.

3. Write the following methods and use them in your A* search program.

   expand  /* given the ID label of the current state,
              return a list of its children's ID labels.
   
     if label="0101" then return "01", "01010", and "01011",
     else return label+"0" and label+"1".
   
     This generates a binary tree, with an extra loop from node '0101' to
     node '01'.  Nodes in the tree are labeled as follows.  The root node
     has label '0'.  Every node with label 's' has children 's0' and 's1'. 
     For example, if a node has label '001', its two children have labels
     '0010' and '0011'. */
   
   goal-test  /* given the ID label of the current state,
   	      returns non-nil iff it is a goal state:
   
     return true if the label is "11010111110000" or "0101010101",
     and false otherwise. */
   
   heuristic  /* given the ID label of the current state, 
   	      returns its h value.
       
     return |(number of 1's in label)-(number of 0's in label)|
     / (length of label) * 30
   
     This takes the absolute value of the difference between the number
     of 1's in label and number of 0's in label, divides it by the total
     number of digits in label, and multiplies the result by 30. */
   

   Assume that each move from a node to one of its children cost 1 unit. Then the value of g for a node is the number of moves from the start node to the node itself.

4. Your program is not required to return a path to the root upon success, but just the ID label of the goal node. However, you are required to write the program so that it prints the ID label of a node every time the node is generated.

5. Test your program by running it with argument "0", the ID label of the start node.