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:
Point data type. The Point data type represents points in the plane, as described by the following API:
Download Point.java; do not implement it.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 }
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:
Your Tour data type must implement the following API:private class Node { private Point p; private Node next; }
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:
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.% 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
% 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.