## Heuristic Search: Route Finding

### Due: Friday, September 28, 2007.

In this assignment, we will use A* and IDA* search to find routes for driving between cities.

Functions and data are provided in the file txcities.lsp for use with this assignment; these are described later.

1. Write a function (astar start goal hfn) that finds a driving route from the city start to the city goal, using the A* algorithm and the heuristic function hfn. You can call the heuristic function using (funcall hfn city goal) where city is the current city being examined; hfn will give an estimated distance to the goal. The astar function can use the citypath function described below. You do not need to implement the closed list, nor check for duplicates on the open list.

Test your function by finding routes:

1. austin to temple
2. austin to dallas
3. corsicana to muleshoe
5. dumas to houston

Try the heuristic functions h0, h1, and h2 on each of the above routes. Print out the number of nodes removed from the open list each time. Print out the mileage of the route that is found. How does the number of nodes vary depending on the heuristic function? How do the routes vary? Are the routes good ones?

2. Write function(s) (citypath node) that reverses the sequence of cities starting with the node node, its parent, and so forth. node is the goal node; the result should be a list of city names, from the start to the goal.

3. Write function(s) (idastar start goal hfn) that finds a driving route from the city start to the city goal, using the IDA* algorithm. Test using the same routes and heuristic functions as above. Count the number of nodes examined; global variables *nodes*, *minover*, and *gvalue* are provided (you will need to initialize them).