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.
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