9. TSP (Partner Assignment) | COS 126 Fall'21 Search COS 126 Fall'21 COS 126 Fall'21 Syllabus Schedule Assignments Project Resources Exams People Light Dark Automatic 9. TSP (Partner Assignment) Due November 21 at 23:59 Goals To learn about the notorious traveling salesperson problem. To learn to use linked lists. To get more practice with data types. Getting Started Download the project zip file for this assignment from TigerFile This is a partner assignment. (See instructions on Ed for creating a TigerFile group.) Read Section 4.3. Pay particular attention to the parts that deal with linked lists. In this assignment, “linked list” always refers to a “circular linked list.” 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 Overall Requirements You must implement one class: Tour.java We provide several other classes and files: Point.java NearestNeighbor.java SmallestInsertion.java TSPTimer.java TSPVisualizer.java data files readme.txt template 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 {
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
}
Do not implement Point.java - use the class we provided. Tour.java 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 String toString() // returns a string representation of this tour
public void draw() // draws this tour to standard drawing
public void insertNearest(Point p) // inserts p using the nearest neighbor heuristic
public void insertSmallest(Point p) // inserts p using the smallest increase heuristic
// 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 Click here for some suggestions for how you might make progress. You do not have to follow these steps. Review the CircularQuote exercise from precept. This exercise illustrates circular 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 circular linked list. To assist with debugging, define the constructor that takes four points as arguments and constructs a circular 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 points: public static void main(String[] args) {
// define 4 points that are the corners of a square
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 squareTour = new Tour(a, b, c, d);
// print the size to standard output
int size = squareTour.size();
StdOut.println("Number of points = " + 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
double length = squareTour.length();
StdOut.println("Tour length = " + 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. You should get the following output: // print the tour to standard output
StdOut.println(squareTour);
(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. StdDraw.setXscale(0, 600);
StdDraw.setYscale(0, 600);
Congratulations on reaching this point: writing linked list code is always a challenge! Implement insertNearest(). 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 circular 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. As a check, 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. After completing the insertNearest() method, you should be able write the insertSmallest() 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. As a check, the file tsp10-smallest.ans contains the resulting tour, which has length 1655.7462. In this case, the smallest insertion heuristic actually does worse than the nearest neighbor insertion heuristic (although this is not typical). 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 circular 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
Submission Before submitting the assignment, please ensure you have read the COS 126 Style Guide and that your code follows our conventions. Style is an important component of writing code, and not following guidelines will result in deductions. Submit the files Tour.java and a completed readme.txt file to TigerFile . Leaderboard - Optional 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. Run the original greedy heuristic (or any other heuristic). Then repeat the following: Choose a pair of edges in the tour, say 1–2 and 3–4. Replace them with 1–3 and 2–4 if this improves the tour. This requires some care, as you will have to reverse the orientation of the links in the original tour between nodes 3 and 2 so that your data structure remains a circular linked list. After performing this heuristic, there will be no crossing edges in the tour, although it need not be optimal. Enrichment Here’s a 13,509-point problem that contains each of the 13,509 cities in the continental US with population over 500. The optimal solution was discovered in 1998 by Applegate, Bixby, Chvatal, and Cook using theoretical ideas from linear and integer programming. The record for the largest TSP problem ever solved exactly is a 85,900-point instance that arose from microchip design in the 1980s. It took over 136 CPU-years to solve. Here’s an excellent and very accessible book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, William J. Cook about the TSP. Here’s a nice pictorial survey of the history of the TSP problem. Some folks even use the TSP to create and sell art. Check out Bob Bosch’s page. You can even make your own TSP artwork. Copyright © 2000–2021 Robert Sedgewick and Kevin Wayne, All Rights Reserved Published with Wowchemy — the free, open source website builder that empowers creators. Cite × Copy Download
