CS15-381 Artificial Intelligence, Fall semester 2002

Instructor: Tuomas Sandholm

Homework 1: IDA* and simulated annealing

Assigned: Thursday, September 12th

Due: Thursday, September 26th, in the beginning of class

Maximum points: 100

Start early: this homework requires quite some work. Do not discuss solution approaches with others or share code. All code must be written by yourself. Do not use components from the web or from your friends.

- (50 pts) Write a program that uses the IDA* algorithm to solve the Traveling Salesman Problem (TSP). Let the cost to move between cities be Euclidean distance, i.e., straight-line distance. In the code, try to separate the domain independent part (search algorithm) from the domain specific part (TSP related functions).

Generate and use a good admissible **h**
function, and describe it in detail in the writeup. Think carefully about how
to construct the **h** function since some choices of **h** functions may
be too bad to allow you to execute the search in practice. If your program
spends more than 20 minutes on a problem instance of 10 cities, something is
wrong: terminate the run and rethink your design.

Explain how you change the IDA* threshold between iterations.

Conventions: Always start from node A. (You might as well since every tour has to go through A; thus A never needs to be backtracked.) Generate the successors of any given node in alphabetical order. Count nodes as they are generated as successors.

Run the program on the 10-city problem instance problem10-1 available at

`http://www.cs.cmu.edu/~sandholm/cs15-381/hw1/`

For each iteration, show the threshold and the number of nodes created. How many nodes did IDA* create overall? Show the final solution. Is IDA* complete? Is it optimal?

Then, run IDA* on random problem instances with 1 to 10 cities (5 instances for each number of cities). These instances are given in files at the above directory, one instance per file (a tar file problems.tar including all of them is also provided to facilitate easier download). Plot how many nodes IDA* generates on average for each number of cities. Extrapolate from these results roughly how many nodes IDA* would generate for a 26-city problem instance [to do this, you may want to use a logarithmic scale on the value axis]. How long would that search take?

2. (50 pts) Write a program that solves the TSP using simulated annealing. Explain what local search operators you use [make sure that the operators preserve a circuit]. Experiment with different annealing schedules, and explain what schedule you choose to use. Run the program on the 26-city TSP problem instance given in the file problem26. Plot how the cost of the solution changes during one run of the algorithm. What is the cost of the best solution that your algorithm found (do not let it run for more than 5 minutes)? Is simulated annealing complete? Is it optimal?

The problem instances that are in the files are in the following format:

<number of cities>

<city id> <X> <Y>

<city id> <X> <Y>

.

.

.

<city id> <X> <Y>

The <city id> is a capital letter.
The identifiers <X> and <Y> represent the x and y coordinates
(integers) of the city. Each city is on its own line and the number of cities
is on the first line by itself.

Example:

3

A 17 55

B 24 38

C 91 57