COS 126Star Tours |
Programming Assignment 4Due: 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.

Your first task is to implement the functions#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)); }

Make sure that your0.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.