| COS 126 Traveling Salesperson Problem |
Programming Assignment 6 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.
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);
double TOURdist(void);
void TOURinsert(Point p);
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.
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.1223 201.3226 moveto 100.4524 101.6653 lineto 90.2345 304.1111 lineto 200.7356 240.8922 lineto 345.1848 392.2334 lineto closepath stroke showpage
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 commands. Multiply the point coordinates by 512 to convert them to PostScript coordinates as in the above program. To do this, replace the interface function TOURshow() so that it produces the desired PostScript output. If you save the output in a file with a.out < tsp.txt > tour.ps, then you can use gs tour.ps or lpr tour.ps to see the tour that your program produces.
What to submit. Submit the 4 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.