Homework 8: Due 11/1

This homework asks you to implement a recursive algorithm that uses "search with backtracking" to compute an optimal solution to the travelling salesman problem (TSP). You will use ideas similar to those used to solve the n queens problem (see Queens.java). You will test your implementation on the set of 128 cities given in miles.dat. This homework is an important part of Project 2.

The travelling salesman problem (TSP) takes as input a set of cities and pairwise distances between these cities and outputs a shortest tour that visits every city exactly once and returns to the starting city. The basic "search with backtracking" algorithm for this problem is quite simple. Suppose we have somehow computed a tour T, representing our current best solution to the problem. We would now like to systematically generate all possible tours, rejecting long (i.e., bad) tours as quickly as possible. Specifically, as soon as we have a partial tour whose length is longer than the length of T, we should reject that tour immediately and move on to generating the next tour. On the other hand if we have completed the generation of a tour, say R, then that must mean that R is shorter than T, and therefore we replace T by R. When I say "partial tour" I mean a tour that starts at a city, visits a few cities (not necessarily, all) exactly once and returns to the starting city. Here is the pseudocode for a function called TSP that expresses this algorithmic idea.

	// R is a partial tour; initially, it may be empty or just contain the first city
	// T is the current best tour; it may be computed greedily, initially
	void TSP(R, T)

		// Base case: we have discovered a tour better than T
		if (R is a complete tour)
			T <- R;

		// Another base case: our partial tour is not worth completing
		if (R is longer than T)
			delete the last city from R;

		// Recursive case: R is not complete and is currently better than T
		// and is therefore worth completing
		for (each city c not in R) do
			append c to R;
			TSP(R, T);
		} // end of for-loop

	} // end of TSP

The use of the "current best" tour T to prune our search is critical and is our only hope that we can compute a traveling saleman tour of 128 cities in a reasonable amount of time. Notice that as the algorithm proceeds, T gets shorter and this may lead to quicker pruning later. Initially, T can be computed greedily. One version of a greedy algorithm is the following. Suppose we have a partial tour, say P. Consider each city c not in P and consider all ways of inserting c between a pair of adjacent cities in P. The cost of inserting c is the smallest increase in the cost of P by inserting c between any pair of adjacent cities. The best city to add to P in this greedy step is the city with smallest cost of inserting. The partial tour P grows in this manner until it becomes a complete tour. To get the greedy algorithm started, you can pick the shortest triangle (i.e., a tour with 3 cities) as P.

Even though the pseudocode is given, there are a number of implementation decisions to be made. How are the tours going to be represented (a String[], an int[], or maybe a doubly linked list)? Does the function TSP need additional arguments that will make it easier to check base case conditions? What should the return type of TSP be (is it ok to leave it void)? Think carefully about these choices; not all choices are equal and some can make your life quite complicated.

You can break up what you have to do for this homework into 3 main steps:

  1. Read the names of cities and their pairwise distances from miles.dat. Recall that you have already done this for Project 1. You may use the code I posted, if you wish. Note that only the array containing the names of the cities and the 2-d array containing pairwise distances between cities is relevant to this homework.
  2. Implement a method called greedyTSP that uses the greedy algorithm described above to compute a traveling salesman tour (which may not be optimal).
  3. Implement the TSP method using the pseudocode described above.
Implement all of this in a program called TSPTester.java.

Recall that the data file miles.dat contains a list of 128 cities and their pairwise distances. The number of permutations of 128 cities is roughly 3 followed by 215 zeros! This is an incredibly large number - e.g., larger than the number of atoms in the universe. So unless our algorithms prunes most possible tours, there is no way we can solve TSP for 128 cities. Even with pruning, it is quite likely that we cannot solve TSP on 128 cities quickly enough. So make sure that you first test your implementation on smaller sets of cities. For example, you can take the first 20 cities in miles.dat to see if your program can compute a solution to TSP with 20 cities. In addition to TSPTester.java, submit a file called TSPTester.pdf that answers the following questions:

  1. How long does your program take to solve TSP of 5, 10, 15, 20, 25, ..., 100, 125, 128 cities? It is quite possible that your program is unable to solve TSP for more than a few cities; state clearly the largest problem size that your program was able to handle.
  2. Can you think of any other ways in which we can substantially speedup the solution of a TSP?