Program 3: Search Methods

Test Data

• nzgraph.dat
• nzdists.dat
• test.l

Due Date

This assignment is due at the beginning of the lecture on Friday, November 12th.

Partners

You may work with (at most) one other person on this assignment. If you work with a partner, submit one solution with both of your names on it.

General Requirements

The implementation must be in Common Lisp and/or CLOS.

Driving in New Zealand

In this assignment, the goal is to find driving routes between pairs of New Zealand cities. Each city is given in terms of X and Y coordinates. We are also given information describing which cities have roads between them. The original data set comes to us compliments of Professor Ken Hawick of Massey University in New Zealand.

Remember the functions from the text:

• h(n) = estimated cost of cheapest path from current node to goal node
• g(n) = cost to go from the start node to the current node

Data Files

• A file showing the X and Y coordinates of various New Zealand cities.
• A file showing which pairs of cities are connected and what the toll rate on the road is.

Part I

Implement each of the search algorithms below. Use the A* framework so that each search has the same architecture.

• Breath First
• Depth First
• Greedy Best First
• A*

Use the Euclidean distance for h(n). Use the Euclidean distance for the roads traversed for g(n).

Part II

Repeat the searches in Part I. This time, use the Euclidean distance multiplied by the average toll rate for h(n) and use the Euclidean distance multiplied by the actual toll rate for g(n).

Hints

• Remember to exclude cycles when you are searching for a solution. Use an appropriate, efficient data structure to achieve this.
• Make sure your implementation can handle the case where no solution exists.
• Here is a file that demonstrates how to read from a file.

Required Function

Write a function that has the template (test-all city-1 city-2) The function should conduct eight searches: the four searches described in Part I and the four searches described in part II.

Required Output

For each algorithm, print the following in a readable format:

• The route found
• The number of hops used in the route
• The total cost of the route
• The total number of cities encountered during the search (count duplicates)

What to Submit

1. A printout of the source code that you produce.
2. A printout of your program running on the data file for these city pairs:
   • (test-all 'wellington 'cape-reinga)
   • (test-all 'hamilton 'gisborne)
3. An e-mail of your solution to John at paxton@cs.montana.edu on or before Friday, November 12th at noon.

Grading

• 50% Quality of Answers. We will be testing your program with several new input cases.
• 20% Elegant Code, Good Style, Good Comments.
• 10% Error-Free and Warning-Free.
• 10% Readable Output Format
• 10% Write a one page analysis of the results. Explain the performance of each algorithm in isolation and in comparison to the other algorithms.