COS 126 Traveling Salesperson Problem Programming Assignment

Given N points in the plane, the goal of a traveling salesperson is to visit all of them (and arrive back home) while keeping the total length traveled as short as possible. Implement two greedy heuristics to find good (but not optimal) solutions to the traveling salesperson problem (TSP).

 1,000 points optimal tour

Perspective. 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 traveling salesperson problem is a notoriously difficult combinatorial optimization problem, In principle, one can enumerate all possible tours and pick the shortest one; in practice, the number of tours is so staggeringly large (roughly N factorial) that this approach is useless. For large N, no one knows 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 are not guaranteed to produce the best possible tour. Such methods are called heuristics. Your main task is to implement the nearest neighbor and smallest increase insertion heuristics for building a tour incrementally. 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.)

Point data type. The Point data type represents points in the plane, as described by the following API:

```public class Point {
public        Point(double x, double y)  //  creates the point (x, y)
public double distanceTo(Point that)     //  returns the Euclidean distance between the two points
public   void draw()                     //  draws this point to standard drawing
public   void drawTo(Point that)         //  draws the line segment between the two points
public String toString()                 //  returns a string representation of this point
}
```
Download Point.java; do not implement it.

Tour data type. Your main task is to create a Tour data type that represents the sequence of points visited in a TSP tour. Represent the tour as a circular 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 {
public        Tour()                                    //  creates an empty tour
public        Tour(Point a, Point b, Point c, Point d)  //  creates the 4-point tour a->b->c->d->a (for debugging)
public    int size()                                    //  returns the number of points in this tour
public double length()                                  //  returns the length of this tour
public   void draw()                                    //  draws this tour to standard drawing
public   void show()                                    //  prints this tour to standard output
public   void insertNearest(Point p)                    //  inserts p using the nearest neighbor heuristic
public   void insertSmallest(Point p)                   //  inserts p using the smallest increase heuristic
}
```

Standard output format. The show() method must print the points to standard output, one per line, by (implicitly or explicitly) calling the toString() method for each point, starting with the first point in the tour. It should produce no other output.

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

Performance requirements. All instance methods should take time linear (or better) in the number of points currently in the tour. Each constructor should take constant time.

Corner cases. You may assume that any Point argument is not null.

Input and testing. The input format will begin with two integers w and h, followed by pairs of x- and y-coordinates. All x-coordinates will be real numbers between 0 and w; all y-coordinates will be real numbers between 0 and h. For example, tsp1000.txt contains the following data:

```% more tsp1000.txt
775 768
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 insertion heuristic.

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

Analysis.  In your readme.txt, estimate the running time of your program as a function of the number of points N. Use the client TSPTimer.java help collect your data points. (It relies on Stopwatch.java, which is part of stdlib.jar.) Run the two heuristics for N = 10,000, and repeatedly double N until the execution time exceeds 60 seconds.

Files provided.  The file tsp.zip contains Point.java; the four clients NearestNeighbor.java, SmallestInsert.java, TspVisualizer.java and TSPTimer.java; several sample input files; and the readme.txt templates.

Submission.   Submit Tour.java and readme.txt (or just the abbreviated partner readme.txt if your partner submitted the code).

Leaderboard (optional). Implement a better TSP heuristic. Here are some ideas. We will award a special prize to whoever finds the shortest tour around tsp1000.txt.

• API requirements. Name your program TSP.java. The only public method in TSP.java should be main(), which should read a sequence of points from standard input (in the standard format) and print the resulting tour to standard output, one point per line.

• Performance requirement. It should solve a 1,000-point instance in at most a few seconds.

• Submission. Submit the following to the TSP leaderboard: TSP.java; any accompanying files; and a leaderboard.txt file, which describes your heuristic.
Copyright © 2000–2016, Robert Sedgewick and Kevin Wayne.