Programming Assignment Checklist: Traveling Salesperson Problem


Pair programming. On this assignment, just like the last one, you are encouraged (not required) to work with a partner provided you practice pair programming (same rules as last assignment).


Frequently Asked Questions

What are the main goals of this assignment? You should (i) learn about the notorious traveling salesperson problem, (ii) learn to use linked lists, and (iii) get more practice with data types.

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 my program do if the tour has 0 points? The size() method should return 0; the distance() method should return 0.0; the show() method should write nothing to standard output; the draw() method should draw nothing to standard draw.

How do I represent infinity in Java? Use Double.POSITIVE_INFINITY.

How long should my programs take to execute? It should take less than a minute for the 13,509 city example (substantially less if you have a fast computer). If your code takes much much longer, try to discover why (think analysis of algorithms), and explain it in your readme file.

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.

When I run TSPTimer 10000, my TSP program takes more than a minute to run. How can I fix this? This is usually a problem with smallest insertion. 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 distance() method to compute the new tour distance at each potential insertion point, you are effectively adding another loop inside your first loop (even though it looks like a simple method call), which is too slow. You do not need to recompute the entire distance for each possible insertion point. You only need to compute the change in the distance and keep track of which insertion point results in the smallest 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.

For the extra credit, how fast should my solution be? It depends on your computer, but a maximum of one minute for tsp1000.txt is a good rule of thumb, and it is even better if it can handle the 13509-point tour within a minute.

Do I have to use a linked list for the extra credit? No, you are not required to use the Tour data type or linked lists for the extra credit. Of course, you should exercise good modular design.

What is the distance of the best known tour for tsp1000.txt? Mark Tengi '16 holds the COS 126 record with a tour of length 15892.3. Using the Concorde TSP solver, we found a solution of length 15476.519.

Input, Output, and Testing

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 distances 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.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

  1. Download the .zip file mentioned on the assignment page. Extract it; later you should save Tour.java in the same directory.

  2. Study the Point API. Its main() method reads in data from standard input in the TSP input format and draws the points to standard draw.

  3. Create a file Tour.java. Include the standard linked list data type Node. Include one instance variable, say first, of type Node that is a reference to the "first" node of the circular linked list.

    For debugging purposes only, make a constructor that takes four points as arguments, and constructs a circular linked list using those four Point objects. First, create four nodes and assign one point to each. Then, link the nodes one to another in a circle.

  4. Implement the method show(). It should traverse each Node in the circular linked list, starting at first, and printing each Point using StdOut.println(). This method requires only a few lines of code, but it is important to think about it carefully, because debugging linked-list code is notoriously difficult and frustrating. Start by just printing out the first Point. With circular linked-lists the last node on the list points back to the first node, so watch out for infinite loops.

    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 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();
  }
    If your method is working properly, you will get the following output for the 4 city problem above. 
    (100.0, 100.0)
(500.0, 100.0)
(500.0, 500.0)
(100.0, 500.0)
    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.)

    Put the debugging constructor back to the original four point Tour before continuing.

  5. Implement the method size(). It is very similar to show().

  6. Implement the method distance(). It is very similar to show(), except that you will need to invoke the method distanceTo() in the Point data type. Add a call to the Tour distance() method in the main() and print out the distance and size. The 4-point example has a distance of 1600.0.

  7. Implement the method draw(). It is also very similar to show(), except that you will need to invoke the method drawTo() in the Point data type. You will also need to include the statements 
     
StdDraw.setXscale(0, 600);
StdDraw.setYscale(0, 600);
    in your main() before you call the Tour draw() method. The four point example above should produce a square.
After arriving at this point, you should feel a sense of accomplishment: working with a linked list is quite difficult at first!

  1. 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, here is the resulting tour for the 10 city problem which has distance 1566.1363. Note that the optimal tour has distance 1552.9612 so this rule does not, in general, yield the best tour.

  2. After doing the nearest insertion heuristc, you should be able write the method insertSmallest() 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, here is the resulting tour which has distance 1655.7462. In this case, the smallest insertion heuristic actually does worse than the nearest insertion heuristic (although this is not typical).

Enrichment