CSE 352 Spring 2003 Stony Brook |
Artificial Intelligence
Annie Liu Assignment 3 |
Handout A3 Feb. 6, 2003 Due Feb. 20 |
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.
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
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
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.