Goals
Design a heuristic to "solve" the traveling salesman problem.
Learn to use linked lists.
Learn about computational complexity and the difference between polynomial and exponential algorithms.
Checklist
Use the submit command:
/u/cs126/bin/submit 4 readme tour.c tourps.c tour.ps Point.h point.c extra.c
. Do not use different file names, except possibly for the optional extra credit.
In precept we will discuss the traveling salesperson problem (TSP) and the greedy insertion heuristic. Also writing linked list code.
readme
Name, precept number
Description of problems encountered and high level description of code
Explain why you use a circular linked list instead of some other data structure.
The tour and total distance obtained for
tsp10.txt
, the total distance for the larger data files
tsp100.txt
and
tsp1000.txt
(do
not
include the other output from these large files).
Indicate how long it takes for your program to finish the 1,000 point file - use the Unix
/usr/bin/time
command, e.g.,
/usr/bin/time a.out < tsp1000.txt > out
. Estimate how long it would take to solve a 100,000 point problem.
Indicate how long it takes the brute force program to finish the 10 point file. Estimate how long it would take to solve a 1,000 point problem using the N! algorithm.
indicate any help (if any) you received
please, no PostScript output in readme file
executing
Type
a.out
and enter the points from the keyboard, type
Ctrl-d
when done.
Type
a.out < tsp10.txt
to use the file
tsp10.txt
as standard input instead of reading in from the keyboard.
tour-brute.c
Here's the
tour-brute.c
code from Lecture 9.6, along with
Point.h
and
point.c
It checks all N! permutations of cities - for a 100 city problem, this would require
100!
operations; this far exceeds the number of atoms in the universe. Click here to see what
1000!
looks like.
Run this file on
tsp4.txt
and then
tsp10.txt
. Do
not
attempt to run on large inputs.
tour.c
Can use
tour.c
as starting point - it reads in points (from standard input) and inserts them in order into a circular linked list (be sure to completely understand all code provided)
Use interface
Point.h
and implementation
point.c
to represent points in the plane.
Get the
tourdist
and
showtour
functions working first, consider using a
do-while
loop, as these are often useful for circular linked lists.
Then get the insertion heuristic going.
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. lcc's -n option can help; the -n flag causes lcc to automatically generate code to checks for such errors, and issue an error message.
Make sure that your code does not inadvertently prevent a new point from being inserted either immediately after (or before)
tour
.
The greedy insertion heuristic should take at most a second on the 1000 point example (it's an O(N^2) algorithm) - if your code takes a while, try to determine what is the cause (it's probably an O(N^3) algorithm).
As a check, the answer you should get using the greedy insertion heuristic on the
tsp10.txt
problem is
tsp10.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.
tourps.c
your C program should use
printf
statements to output the PostScript program to the screen - you really just need to regurgitate the sample PostScript code, filling in the
x y lineto
commands with the x and y coordinates of each successive point in the tour (it is easier than you might think)
save your PostScript program to a file by typing
a.out < star1000.txt > tour.ps
; to view type
gs tour.ps
if your picture has many crossing lines, this indicates you made an error writing the insertion heuristic
see the PostScript section of the
Frequently Asked Questions
page for more info
extra.c
Possibilities for improvement are endless. Here are some
ideas
. If you have previous programming experience, you should definitely attempt the extra credit.
Enrichment Links
More test data is available from
TSPLIB
. Here's a
13,509
node problem in our format and in
PDF
. It contains every city in the continental US with population over 500. Here's the
optimal solution
to the 13,509 node example. It was not solved until 1998! Here are
1,139
and
3,795
node problems arising from a circuit drilling problem.
Here's a
link
to a nice pictorial survey of the history of the TSP problem.