Part 0: preparation
(0 points)
|
Part 1: TOURshow() and TOURdist()
|
The client program tsp.c uses the interface
TOUR.h to derive an approximate solution to the
traveling salesperson problem. Your task is to
write different implementations for the interface functions
defined in TOUR.h. You will use the data type
for Euclidean points defined in POINT.h and
implemented in point.c.
Part 2: nearest insertion
|
For this part, your only task is to modify the
TOURinsert() to perform the nearest insertion
heuristic.
Copy the file tour.c from Part 2 to a new file
tour-nearest.c.
For each point in the tour, you need to compute the Euclidean
distance between that point and p.
Thus, you will need to traverse the circular linked list.
As you proceed, you should store the closest point and
its distance to p. After you have found the nearest point in
the tour, say z, insert p
after z. Think about why don't you insert it
before point z.
Compile your program with:
gcc126 tsp.c tour-nearest.c point.c
For the small files, execute with:
a.out < tsp10.txt
For the large files, send the output to a file to avoid
a large amount of data from scrolling down your screen:
a.out < tsp1000.txt > tsp1000.ans
As a check, the answer for the 10 city problem is
tsp10-nearest.ans.
Once your code is working, determine how long it takes
to process the 10,000 point file. Use the Unix time
command as above, but this time send the output to a file.
(Otherwise the printing to the screen will bias the answer.)
time126 a.out < tsp10000.txt > out
Estimate how long it would take to solve a 100,000 point problem.
You should be able to get a pretty accurate estimate by comparing
the solution times for the 5,000 and 10,000 point problems. What
effect does doubling the problem size have on the running time?
Some debugging ideas
A good debugging strategy for most programs is to test
your code on inputs that you can easily solve by hand.
Start with 1 and 2 city problems. Then, do the 4 city problem.
Choose the data so that it is easy to work through
the code by hand. Draw pictures.
If your code does not do exactly what your hand calculations
indicate, determine where they differ.
Use the printf() method.
Pointer bugs are notoriously difficult to find. A common
error is to dereference null pointers, e.g., using an expression like
x->next when x = NULL. This causes a
segmentation fault when you run the program.
The -n flag of the lcc compiler can help
find some of these:
lcc -n tsp.c tour-nearest.c point.c
a.out < tsp10.txt
Part 3: smallest insertion
|
After doing Part 2, you should be able to do this part by yourself,
without any hints. Again, you only need to modify the
TOURinsert() function. Now, you want to
insert point p where it will result
in the least possible increase in the total tour length.
This smallest insertion heuristic should take at most a
couple of seconds on the 1,000 point example - if your code takes
much longer, try to discover why, and explain in your readme file.
As a check, the answer for the 10 city problem is
tsp10-smallest.ans.
Note that the heuristic doesn't even obtain the best possible
solution on the 10 node example: a
better
tour
can be obtained by permuting the last 3 cities.
Part 4: PostScript output
|
For this part, you will modify the TOURshow()
function so that it outputs a PostScript program that will plot
the tour graphically.
First, make a copy of your tour-smallest.c program
and call it tourps-smallest.c.
Basically, just regurgitate the sample PostScript code from
the assignment, filling in the "x y lineto"
commands with the x and y coordinates of each successive point
in the tour. Use the POINTprintps() interface function
to print points scaled up by a factor of 512.
This function also removes the parentheses and comma when printing
out the coordinates.
In case you're worried, the
"total distance = " line in tsp.c will be
ignored by the PostScript viewer as long as it occurs
after the final stroke showpage is printed.
So, you should not modify the client program at all.
Save your PostScript program to a file by typing
a.out < tsp1000.txt > tour1000.ps
To view type
gs tour1000.ps
Here is the
correct output for the 1,000 city problem.
See the
Frequently Asked Questions
page for more info on PostScript.
Written by
Lisa
Worthington
and
Kevin Wayne