COS 226 Programming Assignment

Backtracking for the TSP

Write a program that finds the exact solution to the Euclidean traveling salesperson problem: Given N points in the plane, find the shortest tour that visits all of the points and returns back home.

The goal of this assignment is to develop respect for intractability and to introduce you to the idea of using backtracking to substantially reduce the amount of computation required to solve typical inputs of an intractable problem.

Starting point. Your first task is to write a program that tries all possible tours and keeps track of the best one. Start with the permutation-generation program Rooks.java from lecture and Point.java (which you have used before). Rename the permutation-generation program TSPbrute.java and make the following changes:

• Replace the instance variable int[] rooks with Point[] tour to hold the current partial tour.

• Add an instance variable Point[] best to hold the best tour seen so far.

• Change the constructor to take a Point array as argument.

• Change the process() method to copy tour[] into best[] if it represents a shorter tour and to draw the improved tour on standard draw.

Also, write a main() driver to read from standard input an integer N followed by the N points (two double values per line). For the input file tsp10.txt, your program should output the following optimal tour (in exactly the format specified):

% more tsp10.txt 10 0.70501 0.58793 0.26077 0.84765 0.12284 0.19949 0.20125 0.85198 0.48505 0.08244 0.94810 0.30570 0.69991 0.32967 0.15261 0.59770 0.56046 0.39271 0.80336 0.23430		% java TSPbrute < tsp10.txt 10 0.70501 0.58793 0.94810 0.30570 0.80336 0.23430 0.69991 0.32967 0.56046 0.39271 0.48505 0.08244 0.12284 0.19949 0.15261 0.59770 0.20125 0.85198 0.26077 0.84765 Distance = 2.7600550582605496

Estimate the running time. Of course, TSPbrute.java is prohibitively slow even for small N, because its running time is proportional to about N! (N factorial). Your next task is to answer the following two questions (and justify your answers):

• What is the largest value of N for which you can find the optimal tour in 1 minute? (Assume that the points are random points in the unit square.)

• What is the largest value of N for which your program would find the optimal tour if it could run for 1 million centuries?

Answer these two questions for each successive (cumulative) improvement that you implement in this assignment (and justify your answers).

Backtracking (by pruning with a lower bound). Your next task is to implement a simple backtracking test: if the length of the current path (from tour[0] to tour[n]) plus the distance connecting the two endpoints is greater than or equal to the length of the best tour seen so far, then backtrack. You can use Queens.java from lecture as a model: you need only implement a backtrack() method that does the job. Be sure that you get the optimal tour for the small input files that you can check, then answer the two standard questions.

Initial tour. To improve the performance of the backtracking test, implement the farthest insertion heuristic compute a decent initial tour.

• Start with the two points that are farthest apart, and repeat the following steps until N points are on the tour.

  • Among all points not in the tour, find the one that is the farthest from the nearest point already in the tour. (That is, for each point not on the tour, compute the Euclidean distance between it and every point on the tour. Its distance to the tour is the minimum such distance. The point to add is the one the has maximum distance to the tour.)

  • Insert that point into the tour in the position where it causes the smallest increase in the tour length.

Begin the backtracking algorithm with the resulting permutation. This provides a better initial lower bound; it also provides a more favorable ordering of the points. Be sure that you get the optimal tour for the small input files that you can check, then answer the two standard questions.

Backtracking (by edge exchange). Next, add to your backtrack() method an edge exchange test: if there is an edge (tour[i] to tour[i+1]) on the current path such that exchanging endpoints of that edge with the last edge (tour[n-1] to tour[n]) yields a shorter path from tour[0] to tour[n], then backtrack. In particular, this test prevents the current path from crossing itself. This test requires very little code, but you need to think carefully about it to avoid difficult-to-track bugs. Be sure that you get the optimal tour for the small input files that you can check, then answer the two standard questions.

Backtracking (MST-based lower bound). Finally, improve the first backtracking test to take the points not yet on the current path into account. In particular, the length of the shortest tour that contains the current path from tour[0] to tour[n] is greater than or equal to:

• the length of the current path, plus

• the length of the MST of the points not on the current path, plus

• the distance from the two endpoints of the current path to points not on the current path.

Extra credit. This part of the assignment can add at most 2 point to your grade. It is not our intention to pose an open-ended competition at this busy time in the semester, but we realize that some students may not be able to resist trying some more advanced ideas. See the checklist for some ideas, but feel free to devise your own.

Deliverables. Submit TSPbrute.java, TSPbacktracker.java, Point.java, TSPextra.java, and any other files other than the standard ones (e.g., FarthestInsertion.java, EuclideanMST.java, and Tour.java) needed to run your program. Also include a readme.txt file, answering the questions.