[an error occurred while processing this directive]
Traveling Salesperson Problem Programming Assignment


Goals

Submission

Submit Tour.java and your readme_tsp.txt file, and answer the questions. You may also submit an extra.zip file containing your extra credit implementation and any additional files it requires. Like the NBody extra credit, this must be a zip archive (not any other compression format), even if it only contains one .java file. Our grading scripts will not work properly with any other type of submission, and you will not receive extra credit.

Background

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 distance traveled as short as possible. Implement two greedy heuristics to find good (but not optimal) solutions to the traveling salesperson problem (TSP). In doing 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.
          1000 points in the plane                          optimal tour (we think) - 15476.51924889754
1,000 points optimal tour

Perspective. The importance of the TSP does not arise from an overwhelming demand of salespeople to minimize their travel distance, 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.

Getting Started:

Part I: Tour Data Type

Your 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. Your Tour data type must implement the following API exactly:
public class Tour
----------------------------------------------------------------------------------------------
       Tour()                                   // create an empty tour
       Tour(Point a, Point b, Point c, Point d) // create a 4 point tour a->b->c->d->a
  void show()                                   // print the tour to standard output
  void draw()                                   // draw the tour to standard draw
   int size()                                   // number of points on tour
double distance()                               // return the total distance of the tour
  void insertNearest(Point p)                   // insert p using nearest neighbor heuristic
  void insertSmallest(Point p)                  // insert p using smallest increase heuristic
After arriving at this point, you should feel a sense of accomplishment: working with a linked list is quite difficult at first!

Part II: Creating the Tour

Part III: Analysis

Estimate the running times of your programs as a function of the number of points N.

Contest and extra credit.

Implement a better heuristic. For example, observe that any tour with paths that cross can be transformed into a shorter one with no crossing paths: add that improvement to your program. Here are some other ideas. The speed of your program may vary depending on your computer, but in general it should be at most one minute for tsp1000.txt. You are also not required to use the Tour data type or linked lists for the extra credit. If you are shooting for an A or A+, this is a good opportunity to impress us. However, be warned, this is a difficult extra credit. Answer the relevant questions in the readme_tsp.txt file. We will award a special prize to the student who finds the shortest tour around the 1,000-point set.

Enrichment.

This assignment was developed by Bob Sedgewick and Kevin Wayne.
Copyright © 2000 Robert Sedgewick