9. TSP

Goals

To learn about the notorious traveling salesperson problem.
To learn to use linked lists.
To get more practice with data types.

Getting Started

This is a partner assignment. Instructions for help finding a partner and creating a TigerFile group can be found on Ed.
Download and expand the project zip file for this assignment, which contains the files you will need for this assignment.
Read Section 4.3. Pay particular attention to the parts that deal with linked lists.
In this assignment, linked list always refers to a “circularly linked list.
Review the precept case study: CircularQuote.java before starting this assignment.
This is a partner assignment. Instructions for help finding a partner and creating a TigerFile group can be found on Ed.
The rules for partnering:
- Choose a partner whose skill level is close to your own - only two partners per group.
- Your partner does not have to be in your precept.
- Complete all work with your partner, sharing the same screen. This includes debugging, testing, commenting, writing the readme.txt and acknowledgments.txt, and submitting the files.
- You and your partner must work together on all components. You may not split up the work. One partner may not start the assignment without the other partner present.
- Go to office hours or the Lab TAs with your partner; one partner may not edit the code without the other partner present.
- Use the following pair programming protocol: one partner, the driver, types the code and the other partner, the navigator, reviews the code, identifies bugs, and asks questions. Swap roles every thirty (30) minutes.
- Do not post your code where it is visible to anyone but you and your partner. Code can be shared using Google Drive, Dropbox, etc.
- You may not combine late days with your partner, or use your partner’s late days. For example, if one partner has used one late day, and the other partner has used three late days, and your assignment is submitted two days late, each partner will be charged two late days. So you may want to discuss this before you form a partnership.
- You and your partner must indicate that you both adhered to the partner collaboration rules in the acknowledgments.txt file.
- To dissolve a partnership, you must contact the course administrator.

Background

Goal. Given $n$ points in the plane, the goal of a traveling salesperson is to visit all of them and return to the starting point, while keeping the total length traveled as short as possible. In this assignment, you will implement and evaluate two greedy heuristics to find good, but not optimal, solutions to the traveling salesperson problem. For example the figure on the left (below) shows 1000 points in the plane. The figure on the right (below) shows an optimal tour for these points.

1,000 points	Optimal

Context. The importance of the TSP does not arise from an overwhelming demand of salespeople to minimize their travel length, but rather from a wealth of other applications such as vehicle routing, circuit board drilling, VLSI design, robot control, X-ray crystallography, machine scheduling, and computational biology.

Greedy heuristics. The TSP is a notoriously difficult combinatorial optimization problem. In principle, you can enumerate all possible tours and pick the shortest one; in practice, the number of tours is so staggeringly large (nearly n factorial) that this approach is useless. For large n, no one knows of an efficient method that can find the shortest possible tour for any given set of points. However, many methods have been studied that seem to work well in practice, even though they do not guarantee to produce the best possible tour. Such methods are called heuristics.

Approach

Your main task is to implement the nearest neighbor and smallest increase insertion heuristics for building a tour incrementally, one point at a time. Start with a one-point tour (from the first point back to itself), and iterate the following process until there are no points left:

Nearest neighbor heuristic: Read in the next point, and add it to the current tour after the point to which it is closest. (If there is more than one point to which it is closest, insert it after the first such point you discover.)
Smallest increase heuristic: Read in the next point, and add it to the current tour after the point where it results in the least possible increase in the tour length. (If there is more than one point, insert it after the first such point you discover.

Implementation Tasks

You must implement one class: Tour.java
We provide several other classes and files:
- Point.java
- NearestInsertion.java
- SmallestInsertion.java
- TSPTimer.java
- TSPVisualizer.java
- data files

`Point.java`

We provide a Point data type in the project folder. The Point data type represents points, $(x, y)$ in the plane, as described by the following API:

public class Point {

  // creates the point (x, y)
  public        Point(double x, double y)  

  // returns the Euclidean distance between the two points
  public double distanceTo(Point that)     

  // draws this point to standard drawing
  public   void draw()                     

  // draws the line segment between the two points
  public   void drawTo(Point that)         

  // returns a string representation of this point
  public String toString()                 
}

Do not implement Point.java - use the class we provided.

`Tour`

Create a Tour data type that represents the sequence of points visited in a TSP tour. Represent the tour as a circularly linked list of nodes, one for each point in the tour. Each Node contains two references:

one to the associated Point and
the other to the next Node in the tour.

Within Tour.java, define a nested class Node in the standard way:

private class Node {
    private Point p;
    private Node  next;
}

Your Tour data type must implement the following API:

public class Tour {

  // creates an empty tour
  public        Tour()                                    

  // creates the 4-point tour a->b->c->d->a (for debugging)
  public        Tour(Point a, Point b, Point c, Point d)  

  // returns the number of points in this tour
  public    int size()                                    

  // returns the length of this tour
  public double length()                                  

  // returns a string representation of this tour
  public String toString()                                

  // draws this tour to standard drawing
  public   void draw()                                    

  // inserts p using the nearest neighbor heuristic
  public   void insertNearest(Point p)                    

  // inserts p using the smallest increase heuristic
  public   void insertSmallest(Point p)                   

  // tests this class by directly calling all constructors and instance methods
  public static void main(String[] args)
}

String representation format.

The toString() returns a String containing the points, one per line, by (implicitly or explicitly) calling the toString() method for each point, starting with the first point in the tour.

Standard drawing format.

The draw() method draws the tour to standard drawing by calling the drawTo() method for each pair of consecutive points. It must produce no other output.

Requirements

You must follow the prescribed API for Tour.java. We will be testing the methods in the API directly. If your method has a different signature or does not behave as specified, you will lose a substantial number of points.
You must not add public methods to the Tour API; however, you MAY add private instance variables or methods (which are only accessible in the class in which they are declared).
Each constructor must take constant time.
All instance methods must take time linear (or better) in the number of points currently in the tour.
Corner cases. You may assume that no Point argument is null.

Possible Progress Steps

We provide some additional instructions below. Click on the ► icon to expand some possible progress steps or you may try to solve TSP without them. It is up to you!

Click here to show possible progress steps

Definitely review the CircularQuote case study from precept. This exercise illustrates circularly linked lists and how to use the do {...} while (...) loop to traverse them.
Study the Point API. In this assignment, you will use the constructor to create a point, the toString() method to print it, the distanceTo() method to compute the distance between two points, and the drawTo() method to draw a line segment connecting two points.
Create a file Tour.java. Include the standard linked list data type Node as a nested class. Include one instance variable, say first, of type Node that is a reference to the first node of the circularly linked list.
To assist with debugging, define the constructor that takes four points as arguments and constructs a circularly linked list using those four points. First, create four Node objects and assign one point to each. Then, link the nodes to one another in a circular manner.
Implement the size() method.

To test the size() method, write a main() method that defines four points, constructs a new Tour object using those four points, and calls its size() method. For example, base your example on this template, though you should try defining your own coordinates for the point values:

public static void main(String[] args) {

   // define 4 points that are the corners of a tour
   Point a = new Point(100.0, 100.0);
   Point b = new Point(500.0, 100.0);
   Point c = new Point(500.0, 500.0);
   Point d = new Point(100.0, 500.0);

   // create the tour a -> b -> c -> d -> a
   Tour testTour1 = new Tour(a, b, c, d);

   // print the size to standard output
   StdOut.printf("Test #1 - check size - should be %d\n", 4);
   StdOut.printf("**** Number of points is %d\n", testTour1.size());
}

Implement the length() method. It is very similar to the size() method, except that you need to access two successive points in the tour and call the distanceTo() method from the Point data type. Using the example above, the length() method on the 4-point tour—the length should be 1600.0. (Again, test the length() method using different points for a 4-point tour.)
```
   // print the tour length to standard output
   StdOut.printf("Test #2 - check length - should be %.2f\n", 1600.00);
   StdOut.printf("************ length is %.2f\n", testTour1.length());
```
Implement the toString() method. It is similar in structure to size(), except that you must create a StringBuilder object and append each Point to the StringBuilder object. Test the toString() method on the 4-point tour:
```
   // print the tour to standard output
   StdOut.println("Test #3 - check toString");
   StdOut.println(testTour1);
```
You should get the following output:
```
(100.0, 100.0)
(500.0, 100.0)
(500.0, 500.0)
(100.0, 500.0)
```
Implement the draw() method. It is very similar to length(), except that you will need to call the drawTo() method from the Point data type. You will also need to include the following statements in main() to resize the x- and y-coordinates of standard drawing. For example:
```
   // Test 4 - draw
   StdOut.println("Test #4 - check draw");
   StdDraw.setXscale(0, 600);
   StdDraw.setYscale(0, 600);
   testTour1.draw();
```
Implement the default constructor Tour() and then in your main

Create a Tour object using the the default constructor, for example:
```
   Tour testTour2 = new Tour();
```

Test each method using the testTour2 object: size, distance, toString, and draw. For example:

    // Test 5 - empty tours
    StdOut.print("Pause - press the enter key to continue");
    StdIn.readChar();
    StdOut.println("Test #5 - check empty tour");
    Tour testTour2 = new Tour();
    StdOut.printf("          - check size - should be %d\n", 0);
    StdOut.printf("          *** size is %d\n", testTour2.size());
    StdOut.printf("          - check length - should be %.2f\n", 0.0);
    StdOut.printf("          *** length is %.2f\n", testTour2.length());
    StdOut.println("         - check toString - should be empty");
    StdOut.println(testTour2);
    StdOut.println("         - check draw");
    StdDraw.clear(); // clear the old drawing
    testTour2.draw();

Congratulations on reaching this point: writing linked list code is always a challenge!
Implement insertNearest(Point p). To determine which node to insert the point p after, compute the Euclidean distance between each point in the tour and p by traversing the circularly linked list. As you proceed, store the node containing the closest point and its distance to p. After you have found the closest node, create a node containing p, and insert it after the closest node. This involves changing the next field of both the newly created node and the closest node.
- To test insertNearest, try inserting various points into a 4-point tour and the empty tour. How can you test insertNearest? Hint: use the testing framework above to see the results of calling insertNearest. What should size, distance, toString, and draw do after inserting a node into some tour?
- Once you are confident inserting various points into tours, you can further test:
  - Compile the NearestInsertion.java client.
  - The file tsp10-nearest.ans contains the resulting tour for the 10-point problem, which has length 1566.1363. Note that the optimal tour, the file tsp10-optimal.ans, has length 1552.9612 so this rule does not, in general, yield the best tour.
  - Run the client: java-introcs NearestInsertion < tsp10.txt
  - Compare your results to tsp10-nearest.ans
After completing the insertNearest(Point p) method, you should be able write the insertSmallest(Point p) method by yourself, without any hints. The only difference is that you want to insert the point p where it will result in the least possible increase in the total tour length.
- Again, to test insertSmallest, try inserting various points into a 4-point tour and the empty tour. Then call the size, distance, toString, and draw methods.
- Once you are confident inserting various points into test tours, you can further test:
  - Compile the SmallestInsertion.java client.
  - The file tsp10-smallest.ans has length 1655.7462. In this case, the smallest insertion heuristic actually does worse than the nearest insertion heuristic (although this is not typical).
  - Run the client: java-introcs SmallestInsertion < tsp10.txt
  - Compare your results to tsp10-smallest.ans

Frequently Asked Questions

Click here for answers to some frequently asked questions.

What should the various methods do if the tour has no points? The size() method should return 0; the length() method should return 0.0; the toString() method should return the empty string; the draw() method should draw nothing to standard drawing.
How do I represent infinity in Java? Use Double.POSITIVE_INFINITY.
How can I produce an animation of the heuristic in action? It’s easy and instructive—just redraw the tour after each insertion. See the instructions in SmallestInsertion.java. It could take a while on a big input file, so you might want to modify it so that it redraws only after every 20 insertions or so. Note: when timing your program, don’t show the animation or else this may become the bottleneck.
What is the file Tour$Node.class? When you declare a nested class like Node, the Java compiler uses the $ symbol to mark its name.
How can the suggested definition of private class Node work when it has no constructor declared? If you do not declare a constructor, Java automatically defines a no-argument constructor that sets all of the instance variables to their default values (here null since Point and Node are reference types).
What is a NullPointerException? You can get one by initializing a variable of type Node, say x, to null and then accessing x.next or x.p. This can happen in your insertion routine if you inadvertently break up the circularly linked list.
When should I create a new linked-list node with the keyword new? To create a tour with $n$ points, you should use new exactly $n$ times with Node, once per invocation of insert(). It is unnecessary (and bad style) to use new with your list-traversal variables since this allocates memory that you never use.
When I run TSPTimer.java with 10,000 points, it already takes more than a minute. What should I do? You have a performance error. Try to discover why (think analysis of algorithms) and explain it in your readme.txt file.
When I run TSPTimer.java with 10,000 points, my nearest neaighbor insertion heuristic runs quickly, but my smallest insertion heuristic takes forever. How can I fix this? You probably have a loop that looks at inserting the new point at each possible insertion point. That is fine. However, if you are calling the length() method to compute the new tour length at each potential insertion point, you are effectively adding a second loop inside your first loop (even though it is a single method call), which is too slow. You do not need to recompute the entire tour length for each possible insertion point. Instead, compute the change in the tour length and keep track of which insertion point results in the smallest such change.
Can I use Java’s built in LinkedList class? Absolutely not! One of the main goals of this assignment is to gain experience writing and using linked structures. The Java libraries can take you only so far, and you will quickly discover applications which cannot be solved without devising your own linked structures. (For example, Java’s built in LinkedList is not circular.)

Testing

A good debugging strategy for most programs is to test your code on inputs that you can easily solve by hand. Start with 1- and 2-point problems. Then, do a 4-point problem. Choose the data so that it is easy to work through the code by hand. Draw pictures. If your code does not do exactly what your hand calculations indicate, determine where they differ. Use the StdOut.println() method to trace.
The input files for this assignment include many sample inputs. Most are taken from TSPLIB.
The input format begins with two integers width and height, followed by pairs of x- and y-coordinates. All x-coordinates will be real numbers between 0 and width; all y-coordinates will be real numbers between 0 and height. For example, tsp1000.txt contains the following data:
```
> more tsp1000.txt
800 800
185.0411 457.8824
247.5023 299.4322
701.3532 369.7156
563.2718 442.3282
144.5569 576.4812
535.9311 478.4692
383.8523 458.4757
329.9402 740.9576
...
254.9820 302.2548
```
After implementing Tour.java, use the client program NearestInsertion.java, which reads the points from standard input; runs the nearest neighbor heuristic; prints the resulting tour, its length, and its number of points to standard output; and draws the resulting tour to standard drawing. SmallestInsertion.java is analogous but runs the smallest increase heuristic. For example:

# Nearest Neighbor                                   # Smallest Increase
> java-introcs NearestInsertion < tsp1000.txt        > java-introcs SmallestInsertion < tsp1000.txt
(185.0411, 457.8824)                                 (185.0411, 457.8824)                          
(198.3921, 464.6812)                                 (195.8296, 456.6559)                          
(195.8296, 456.6559)                                 (193.0671, 450.2405)                          
(216.8989, 455.126)                                  (200.7237, 426.3461)                          
(213.3513, 468.0186)                                 (200.5698, 422.6481)                          
(241.4387, 467.413)                                  (217.4682, 434.3839)                          
(259.0682, 473.7961)                                 (223.1549, 439.8027)                          
(221.5852, 442.8863)                                 (221.5852, 442.8863)                          
...                                                  ...                                           
(264.57, 410.328)                                    (186.8032, 449.9557)                          
                                                                                              	   
Tour length = 27868.7106                             Tour length = 17265.6282                 	   
Number of points = 1000                              Number of points = 1000

Nearest Neighbor	Smallest Increase

Interactive visualizer. The client TSPVisualizer.java in an interactive TSP visualizer. When you click a point in the window, it will add it to your tour. It displays both the nearest neighbor heuristic tour (in red) and the smallest insertion heuristic (in blue). You can toggle the visibility of the two tours by typing n (for nearest neighbor) or s (for smallest insertion). For example:

> java-introcs TSPVisualizer tsp1000.txt

Showing Both Heuristics	Showing Smallest Increase Heuristic

Analysis - `readme.txt`

In your readme.txt, estimate the running time (in seconds) of your program as a function of the number of points n. You should use the client program TSPTimer.java to help you estimate the running time as a function of the input size n. TSPTimer takes a command-line argument n, runs the two heuristics on a random input of size n, and prints how long each took. Run the two heuristics for n = 1,000, and repeatedly double n until the execution time exceeds 60 seconds.

In order to get consistent timing results:

Repeat each experiment for n more than once.
Execute java-introcs using the -Xint flag. The -Xint flag turns off various compiler optimizations, which helps normalize and stabilize the timing data that you collect. For example:

> java-introcs -Xint TSPTimer 1000
Tour length = 26338.42949015926
Nearest insertion:  0.056 seconds

Tour length = 15505.745750759515
Smallest insertion:  0.154 seconds

Note:

Explain how you determined each of your answers. You must include your experimental data in the tables provided.

Submission

Submit to TigerFile : the files Tour.java, readme.txt and acknowledgments.txt files.

Leaderboard - Optional

Submit to Leaderboard | View Current Leaderboard

You can also implement a better TSP heuristic for class fame and glory. You are not required to use the Tour data type or linked lists. We will award a special prize to whoever finds the shortest tour for a mystery tour with about 1,000 points. Here are some ideas.

API requirements. Name your program TSP.java. The only public method in TSP.java is main(), which reads a sequence of points from standard input (in the standard format) and prints the resulting tour to standard output, one point per line.
Performance requirements. It must solve a 1,000-point instance in at most a few seconds and a 10,000-point tour in at most a minute.
Submission. Submit the following to the TSP Leaderboard:
- TSP.java;
- any accompanying files; and
- leaderboard.txt, which includes your experimental results and describes your heuristic.

Here are some ideas for finding a better TSP tour. None of the methods guarantees to find an optimal tour, but they often lead to good tours in practice.

Crossing edges.

If two edges in a tour cross, you can decrease the length of the tour by replacing the pair that crosses with a pair that does not cross.

Farthest insertion.

It is just like the smallest increase insertion heuristic described in the assignment, except that the cities need not be inserted in the same order as the input. Start with a tour consisting of the two cities that are farthest apart. Repeat the following:

For each city not in the tour, consider the shortest distance from that city to a city already in the tour. Among all cities not in the tour, select the city whose distance is largest.
Insert that city into the tour in the position where it causes the smallest increases in the tour distance. You will have to store all of the unused cities in an appropriate data structure, until they get inserted into the tour. If your code takes a long time, your algorithm probably performs approximately $n^3$ steps. If you’re careful and clever, this can be improved to $n^2$ steps.

Node interchange local search.

Run the original greedy heuristic (or any other heuristic). Then repeat the following:

Choose a pair of cities.
Swap the two cities if this improves the tour. For example, if the original greedy heuristic returns 1–5–6–2–3–4–1, you might consider swapping 5 and 3 to get the tour 1–3–6–2–5–4–1. Writing a function to swap two nodes in a linked list provides great practice with coding linked lists. Be careful: it can be a little trickier than you might first expect (e.g., make sure your code handles the case when the two cities occur consecutively in the original tour).

Edge exchange local search.