Project 2

Due October 31, 2000

This project assignment involves implementation and performance comparison of Hill-climbing and A* search algorithms to solve the geometric Traveling Salesman Problem (TSP).

1. Problem description: In a geometric TSP each city is represented by a point (x[i] , y[i]) on a unit square plane. These points form a complete graph (i.e., every city is connected to every other city). The distance between two cities (x[i], y[i] ) and (x[j], y[j] ) is measured by the Euclidean distance sqrt((x[i] - x[j] )^2 + (y[i] - y[j] )^2)). The goal of problem-solving is to find the shortest tour that visits every city exactly once and then returns to the starting city (the shortest Hamilton circuit in graph theoretic term).

2. Data: Randomly generate 5 problem instances of 5 cities, and 5 instances of 10 cities, with x and y uniformly distributed between 0 and 1.

3. Hill-climbing: Choose the unvisited city that is closest to the end city of the partial tour represented by the “current” node to visit next.

4. A*: You may choose one of the two heuristics discussed in the class as your heuristic function, or make one of your own. (Make sure the one you choose is admissible!)

5. Comparison and analysis:

(1) For both algorithms record the following for each problem instance:

· The coordinates of all cities

· The tour found and its length

· Total number of nodes generated (a measure of time complexity)

· For A*, the largest size of the OPEN list during the execution (a measure of space complexity)

(2) The comparison is to be done in two dimensions: between two algorithms and between problem instances of different sizes. At least the following three aspects should be compared: accuracy, time and space complexities.

6. Language: No specific requirement.

7. Report: Beside the source code for your implementation of both HC and A* algorithms and the execution results on all problem instances, you are required to submit also a report, which should include the following:

· A brief description of the project assignment

· The heuristic function you selected (and if it is not one discussed in the class, justify that it is admissible)

· Summary of your comparison (both in word and in tabulation)

· Any issues you wish to comment on

Additional work for graduate students (registered for 671)

Run multiple sessions of HC algorithm on all problem instances with each session starting from a different city. Record the best tour found for each instance.
Re-run A* algorithm for all problem instances, using the tour length of the best tour found from HC search to control the size of OPEN list in A* search.
Extend A* to IDA* and run it on all problem instances, using the h value of the start node as the initial f-limit.
Compare the time and space complexity of A* and its two variations above