COS 226 Programming Assignment Checklist: Backtracking for the TSP

Frequently Asked Questions

Which files should I submit? Submit everything you need except for the standard libraries and the standard data structures. Be sure to hit the Run-Script button to make sure everything compiles.

I can't access Rooks.java or Queens.java from the booksite. Sorry, the Algorithms in Java booksite is currently only accessible from the Princeton network. You can find the two files in the ftp directory. If you need access, send Kevin your IP address and he'll add it to the whitelist.

I get the same tour, but starting at a different point (or visiting the points in a different orientation). Is that OK? Yes, that's fine. Also, the distance might differ from the one in reference solution in the last one or two digits (as a result of floating-point roundoff error).

Input, Output, and Testing

Input. The directory backtrack contains a number of sample input files and optimal tours.

Output format. Your output format must exactly match ours: an integer N, followed by the N points (two double values using "%6.5f %6.5f" formatting), followed by the distance of the tour. We will use diff to compare your optimal tour against our reference solutions (though your optimal tour may use a different starting point or orientation.)

Testing.

• One way to check that TSPbacktracker.java is producing an optimal tour is to use standard draw to superimpose your tour (in blue) with the optimal tour provided (in red). (Extra credit if you discover any bugs in our solutions.)

• To independently check FarthestInsertion.java, we have included solutions farthest10.txt and farthest50.txt to the 10- and 50-point instances.

• To independently check that you are computing the Euclidean MST correctly, the distance for the 10-point instance is 2.1158879340974117 and the distance for the 50-point instance is 4.8060373089797475.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

• Download the directory backtrack to your system. It contains a number of sample input files (tsp*.txt) and optimal tours (opt*.txt).

• Create a library of static methods Tour.java with the following API:

  // read in Euclidean TSP instance from input stream
  public static Point[] read(In in)
  
  // print the tour to standard output
  public static void show(Point[] tour)
  
  // return the distance of the tour
  public static double dist(Point[] tour) 
  
  // draw the tour to standard draw
  public static void draw(Point[] tour)
  
  // return a copy of the Point array
  public static Point[] copy(Point[] tour)
  
  

• To implement the farthest insertion heuristic, create a class FarthestInsertion with the following API:

  // constructor
  public FarthestInsertion(Point[] points)
  
  // return the tour create by the heuristic as an array of points
  public Point[] tour()
  

• To compute the Euclidean MST, create a class EuclideanMST with the following API:

  // constructor
  public EuclideanMST(Point[] points)
  
  // return the cost of the Euclidean MST
  public double cost()
  

Extra Credit Ideas

Here are a few ideas that are likely to improve the backtracking algorithm.

• Eliminate different representations of the same tour. There are 2N permutations corresponding to each tour because the starting point and the orientation of the tour are unimportant. Fix three points p, q, and r on the tour and assume that the salesperson visits them in that order, starting from p.

• Better backtracking. Backtrack if moving tour[n-1] to immediately after tour[i] would decrease the length of the current path from tour[0] to tour[n]. Backtrack if one of the two 3-way edge-swaps involving tour[i], tour[i+1], tour[j], tour[j+1], tour[n-1], and tour[n] would decrease the length of the current path.

• Better initial tour. Finding a better initial tour enables the backtracking algorithm to prune more branches. One approach to finidng a better tour is to start with tour produced by the farthest insertion heuristic, and then repeatedly apply local changes that decrease the length of the tour. A 2-opt move removes two edges and reconnects the two resulting paths in a different way (there is only one possible way) to obtain a new tour. A 3-opt move removes three edges and reconnects the three resulting paths in a different way (there are two possible ways) to obtain a new tour.

• Better lower bound. The MST-based lower bound is weak unless most of the vertices in the resulting MST have degree 2 (which rarely happens). To tighten the lower bound, learn about 1-tree Lagrangean relaxation. This is likely to provide the biggest overall improvement, but requires the most effort.