%! 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
| 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.
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:
The above client program uses the interface TOUR.h:
#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());
}
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.
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 */
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.
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 */
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).
#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;
}
}
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 |
|
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.
