% java-introcs TspVisualizer tsp1000.txt
|
|
What are the main goals of this assignment? The goals of this assignment are to:
What preparation do I need before beginning this assignment? Read Section 4.3. Pay particular attention to the parts that deal with linked lists.
Can I program with a partner on this assignment? Yes. You are encouraged (not required) to work with a partner provided you practice pair programming.
Do I need to follow the prescribed API? Yes, 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 may not add public methods to the API; however, you may add private methods (which are only accessible in the class in which they are declared).
|
|
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 show() method should print nothing to standard output; 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? For any class, Java will by default already define 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.
Running TSPTimer.java with N = 10,000 already takes more than a minute. What should I do? You have a performance error. It should take only a few seconds when N is 10,000. If your code takes much much longer, try to discover why (think analysis of algorithms), and explain it in your readme.txt file.
When I run TSPTimer.java for 10,000 points, my nearest insertion heuristic runs quickly, but my smallest insertion heuristic takes more than 10 seconds to run. 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. You only need to 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 only take you so far, and you will quickly discover applications which cannot be solved without devising your own linked structures.
Do I have to use a linked list for the leaderboard? No, you are not required to use the Tour data type or linked lists for the leaderboard. Of course, you should exercise good modular design.
What is the length of the best known tour for tsp1000.txt? Eric Mitchell '18 holds the COS 126 record with a tour of length 15566.37. Using the Concorde TSP solver, we found a tour of length 15476.519.
|
|
Input. The files for this assignment include many sample inputs. Most are taken from TSPLIB.
Debugging. 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 city problems. Then, do a 4 city 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.
Checking your work. For usa13509.txt we get tour lengths of 77449.9794 and 45074.7769 for nearest insertion and smallest insertion, respectively. For circuit1290.txt we get 25029.7905 and 14596.0971.
Timing. You may use the client program TSPTimer.java to help you estimate the running time as a function of the input size N. It takes a command-line argument N, runs the two heuristics on a random input of size N, and prints out how long each took.
Interactive visualizer. TspVisualizer.java in an interactive visualizer. It reads the points from standard input: it displays both the nearest neighbor heuristic tour (in red) and the smallest insertion heuristic (in blue). When you click a point in the window, it will add it to your tour. You can toggle the visibility o the two tours by typing n (for nearest neighbor) or s (for smallest insertion).
% java-introcs TspVisualizer tsp1000.txt |
|||
|
|
If you want to test Tour.java afterimplementing only one of the insertion methods, you must declare the other method (even if it does nothing).
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.
Test your method by writing a main() function that defines four points, creates a new Tour object using those four points, and calls its show() method. Below is a suggested four point Tour for main(). Use it for testing.
// main method for testing
public static void main(String[] args) {
// define 4 points forming 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);
// Set up a Tour with those four points
// The constructor should link a->b->c->d->a
Tour squareTour = new Tour(a, b, c, d);
// Output the Tour
squareTour.show();
}
Test your method show() on tours with 0, 1 and 2 points to check that it still works. You can create such instances by modifying the 4-node debugging constructor to only link 0, 1 or 2 of the four points to the Tour. (If you don't define first, you will have an empty Tour. If you define first and link it back to itself, you will have a 1 point Tour.)(100.0, 100.0) (500.0, 100.0) (500.0, 500.0) (100.0, 500.0)
Put the debugging constructor back to the original four point Tour before continuing.
Test the size() method on some sample Tour objects in the main method.
Test! Add a call to the length() method in the main() and print the length and size. The 4-point example has a length of 1600.0.
Test! You will also need to include the statements
in your main() before you call the Tour draw() method. The four point example above should produce a square.StdDraw.setXscale(0, 600); StdDraw.setYscale(0, 600);
|
|
