F 400.1 201.3 G 100.4 101.6 G 90.2 304.1 G 200.7 240.8 G 345.1 392.2 G 400.1 201.3
| COS 126 Traveling Salesperson Problem |
Programming Assignment 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.
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, many of which seem to have nothing to do with the TSP at first glance. Real world application areas include: vehicle routing, circuit board drilling, VLSI design, robot control, X-ray crystallography, machine scheduling, and computational biology.
Part 1: two tour construction 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 the first 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 in
TOUR.h:
Point p;
while (POINTread(&p) != EOF)
TOURinsert(p);
TOURshow();
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.
void TOURshow(void); // display the tour
int TOURdist(void); // compute the distance of the tour
void TOURinsert(Point p); // insert point p into the tour
The Point data type is supplied in
POINT.h and
point.c.
typedef struct node* link;
struct node {
Point p;
link next;
};
The following TOURinsert() function from
tour-inorder.c.
takes a Point
and makes it the last city visited in the tour.
Your main task is to modify this insertion function
to perform the two heuristics discussed above.
int POINTdist(Point p, Point q); // compute (integer) distance between p and q
int POINTread(Point* pp); // read in a point from stdin
void POINTprint(Point p); // print point to stdout
void POINTprintScaled(Point p) // print point to stdout, scaled to 512 x 512 box
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.
static link first = NULL; // first node on tour
static link last = NULL; // last node on tour
void TOURinsert(Point p) {
link new = NEWnode(p, NULL);
if (first == NULL) { // degenerate case
first = new;
first->next = new;
last = new;
}
else { // insert new node at end of list
last->next = new;
new->next = first;
last = new;
}
}
Compiling and testing. Use "gcc126 tsp.c tour.c point.c" 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: Turtle graphics 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 turtle graphics program that draws the tour created from the smallest-increase heuristic. We have enhanced the turtle graphics language to support flying to an absolute (x, y) coordinate with the pen down. This will simplify the task of tracing out the tour. As an example, the following turtle graphics program draws a tour connecting 5 points in the plane:
F 400.1 201.3 G 100.4 101.6 G 90.2 304.1 G 200.7 240.8 G 345.1 392.2 G 400.1 201.3 |
|
Your program should produce a program exactly like this one, except with the point coordinates on your tour as arguments to the F and G commands. To do this, replace the interface function TOURshow() so that it produces the desired turtle graphics output. Use the POINTprintScaled() function to calculate the turtle coordinates corresponding to each Point. If you save the output in a file with
then you can then see the tour that your program produces via your PostScript viewer as usual. Note that you will need to download and compile the latest version of turtle.c to use the G commmand.a.out < tsp10.txt | turtle > tsp10.ps
What to submit. Submit the files readme.txt, tour-nearest.c, tour-smallest.c, and tour-turtle.c. 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.
