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:

You will need various code (to initialize the instance variables, compute tour lengths, and so forth) to complete this part of the assignment.

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
        TSP instance of 10 points         Optimal tour for 10 points

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):

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.

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.

edge exchange test

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:

MST distance test

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.

This assignment was developed by Robert Sedgewick and Kevin Wayne.
Copyright © 2007.