COS 126

Traveling Salesperson Problem
Programming Assignment 7

Due: Wednesday, 11:59pm

Given a set of 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. Write a program to compute an approximate solution to the traveling salesperson problem, and use it to find the shortest tour that you can, connecting a given set of points in the plane.

Part 1: two heuristics. The traveling salesperson problem is notoriously difficult: 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 one 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.

  • Smallest increase heuristic.   Read in the next point, and add it to the current tour between two successive points at the position where it results in the least possible increase in the tour length.
  • To implement these heuristics you will create a tour ADT. The client program tsp.c reads in the points, and uses your ADT's interface functions to output a good tour:

          #include <stdio.h>
          #include "POINT.h"
          #include "TOUR.h"
          int main(void) {
             Point p;
             while (POINTread(&p) != EOF)
                TOURinsert(p);
             TOURshow();
             printf("total distance = %f\n", TOURdist());
          }
    
    The above client program uses the interface TOUR.h:
          void   TOURshow(void);            /* display the tour                           */
          double TOURdist(void);            /* compute the distance of the tour           */
          void   TOURinsert(Point p);       /* insert point p into the tour               */
    
    Your job is to write an implementation for all three interface functions. To do this, represent the tour as a circular linked list of nodes, one for each point. Each node will contain a Point and a pointer to the next node in the list. Use the Point data type given in POINT.h and point.c.
    double POINTdist(Point p, Point q);     /* compute Euclidean distance between p and q */
    int    POINTread(Point* p);             /* read in a point from standard input        */
    void   POINTprint(Point p);             /* print point to standard output             */
    void   POINTprintps(Point p)            /* print PostScript coordinates of point      */
    
    The following TOURinsert() function takes a Point and inserts it into the tour between the first and second nodes. Your main task is to modify this insert function to perform the two heuristics discussed above.
          #include <stdlib.h>
          #include "POINT.h"
          #include "TOUR.h"
          typedef struct node* link;
          struct node {
             Point p;
             link next;
          };
          static link tour = NULL;
    
          link NEWnode(Point p, link next) {
             link t = malloc(sizeof *t);
             if (t == NULL) {
                printf("Error allocating memory.\n");
                exit(EXIT_FAILURE);
             }
             t->p = p; t->next = next;
             return t;                
          }
    
          void TOURinsert(Point p) {
             link new = NEWnode(p, NULL); 
             if (NULL == tour) {
                tour = new;
                tour->next = new;
             }
             else {
                new->next = tour->next;
                tour->next = new;
             }
          }
    
    Before you implement the heuristics, you should first implement the functions TOURshow() (to print the points on the tour) and TOURdist() (to print its length). These both cycle around the linked list and require only a few lines of code, but it is important to think about them carefully, because debugging linked-list code is notoriously difficult and frustrating. Assume that the points are in the unit square (both coordinates are between 0 and 1).

    Compiling and testing. Use "gcc tsp.c tour.c point.c -lm" to jointly compile your files. Debug your TOURshow() and TOURdist() code by running it on a simple sequence of points, such as tsp5.txt. Make sure that TOURshow() function prints out all the points and that TOURdist() gets the distance right, including the distance back to the starting point. For more test data, use the files tsp10.txt, tsp100.txt, tsp1000.txt, and tsp13509.txt. These points represent various US cities.

    Part 2: PostScript output. The second part of the assignment is much the same as in the Mandelbrot assignment: make a version of your program that outputs a PostScript program that draws the tour created from the smallest-increase heuristic. As an example, the following PostScript program draws a tour connecting 5 points in the plane:
    %!
    50 50 translate
    0 0 512 512 rectstroke
    400.1 201.3 moveto 
    100.4 101.6 lineto 
     90.2 304.1 lineto 
    200.7 240.8 lineto 
    345.1 392.2 lineto 
    closepath stroke showpage
    
    Sample TSP PostScript

    Your program should produce a program exactly like this one, except with the point coordinates on your tour as arguments to the moveto and lineto routines. To do this, replace the interface function TOURshow() so that it produces the desired PostScript output. Use the POINTprintps() function to calculate the PostScript coordinates corresponding to each Point. If you save the output in a file with "a.out < tsp10.txt > tsp10.ps", then you can use "gs tsp10.ps" or "lpr tsp10.ps" to see the tour that your program produces.

    What to submit. Submit the files readme, tour-nearest.c, tour-smallest.c, and tourps-smallest.c. Also, your readme file should include answers to the questions from the online checklist.

    Contest and extra credit. Implement a better heuristic. For example, modify your program to check all the points not yet on the tour, and then add the one that increases the length of the tour the least. Or 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. The checklist page contains several other ideas. We will award a special prize to whomever finds the shortest tour around the 1000-point set.

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