| COS 126 Star Tours |
Programming Assignment 4 Due: Wednesday, 11:59pm |
Write a program to compute an approximate solution to the traveling salesperson problem, and use it to find the shortest tours that you can connecting given sets of points that are drawn from astronomical data.
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. For large N, no one knows a feasible method that can find the shortest possible tour for any given set of points, but 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 following heuristic for building a tour incrementally: Start with a two-point tour (from one point to the other, then back), and iterate the following process until there are no points left. Add the next point to the tour by inserting it between two successive points in the tour at the position where it results in the least possible increase in the tour length.
To implement this heuristic, 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 that is described in Algorithms in C (pp. 78-79). To get started, you may use the following code, which reads points from standard input and builds a circular list from them.
#include <stdio.h>
#include <stdlib.h>
#include "Point.h"
typedef struct node* link;
struct node { point p; link next; };
main()
{ int i;
link t, tour = NULL; point p;
while (scanf("%f %f\n", &p.x, &p.y) != EOF)
{
t = malloc(sizeof *t); t->p = p;
if (tour == NULL) { tour = t; tour->next = t; }
t->next = tour->next;
tour->next = t;
}
showtour(tour);
printf(" %f\n", tourdist(tour));
}
Your first task is to implement the functions showtour
(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 between
0 and 1). Debug your showtour and tourdist code by
compiling it with the code given above and running it on a simple
sequence of points such as the following:
Make sure that your showtour function prints out all the points and that your tourdist function gets the distance right, including the distance back to the starting point. You'll note that the above code doesn't bother to put the points into the list in the order that they appear in the input. What matters is the order in which they appear on the list.0.0 0.5 1.0 0.5 0.5 1.0 0.5 0.0
Your main task is to modify the code above so that it uses the heuristic described above to insert each new point into the tour (rather than just inserting it at the beginning). This part of the assignment accounts for 80 per cent of your grade. For test data, use the attached files for 10 points, 100 points, and 1000 points. These points are stars from a map of the universe, so you might imagine that our salesperson has a starship (but is traveling in a 2D world)!
The second part of the assignment is much the same as the second part of Assignment 2: make a version of your program that outputs a PostScript program that draws the tour. This change is worth 2 points this time, so it probably is worth your while to figure it out. The following PostScript program draws a tour connecting 5 points in the plane:
%! 50 50 translate 0 0 moveto 0 512 rlineto 512 0 rlineto 0 -512 rlineto closepath stroke 400 201 moveto 100 101 lineto 90 304 lineto 200 240 lineto 345 392 lineto closepath stroke showpage
Your program should produce a program like this one, but with the point coordinates on your tour as arguments to the moveto and lineto commands. Multiply the point coordinates by 500 to convert them to Postscript coordinates as in the above program. If you save the output in a file with a.out > tour.ps, then you can use gs tour.ps or lpr tour.ps to see the tour that your program produces.
You must submit a file tour.c which solves the first part of this assignment. If you succeed in getting the PostScript part working, name your source file tourps.c and submit it along with a file tour.ps, that draws your tour for the 1000-point test file. As usual, submit a readme file that gives the tour lengths that your program computed for the test data and describes how your code works.
Extra Credit: 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. Run experiments to assess the effectiveness of this change.
Challenge for the bored:
Experiment with other modifications to the heuristic, or with other heuristics.
Does the order in which you consider the points play an important role?
Any tour with paths that cross can be transformed into a shorter one with
no crossing paths: add that improvement to your program. There will be
a special prize for whoever finds the shortest tour around the 1000-point set.