COS 126 Assignment 4 Checklist

Goals

Learn about the notorious traveling salesperson problem.
Learn to use linked lists.
Get more practice with ADT's.
Learn about computational complexity and the difference between polynomial and exponential algorithms.

Checklist

Use the submit command: "/u/cs126/bin/submit 4 readme tour-nearest.c tour-smallest.c tour1000.ps". Do not use different file names, except possibly for the optional extra credit.

readme

Name, precept number

Give high level description of code and list any problems encountered. Indicate whatever outside help (if any) you received.

Explain why you use a circular linked list instead of some other data structure.

Give the tour and total distance obtained for tsp10.txt, but only the total distance for the larger data files tsp100.txt and tsp1000.txt.

Determine 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.

Determine how long it takes the brute force program (that examines all N! permutations) to finish the 10 point file. Estimate how long it would take to solve a 1,000 point problem.

Please, no PostScript output in readme file.

tsp-brute.c

Here's the tsp-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.

POINT.h, point.c

Use interface POINT.h and implementation point.c to represent points in the plane. Do not change.

tsp.c

Use tsp.c as client program. Do not change.

TOUR.h

Use the interface TOUR.h for tour operations. Do not change.

tour-nearest.c, tour-smallest.c

Write two implementations for the tour interface functions, one for each of the proposed heuristics.

Here is the file /u/cs126/code/tour.c described in the assignment.

First add implementations for TOURshow and TOURdist, using the point data type to compute distances and display points. Consider using a do-while loop, as this is useful for circular linked lists.

Next, replace TOURinsert to do the nearest neighbor heuristic. Save this file as tour-nearest.c

Then, replace TOURinsert to do the smallest increase heuristic. Save as tour-smallest.c

compiling

Jointly compile your files with "lcc tsp.c tour-nearest.c point.c" and "lcc tsp.c tour-smallest.c point.c".

Execute with a.out, then enter points from the keyboard, typing Ctrl-d after entering the last point. Or type "a.out < tsp10.txt" to read points from file tsp10.txt.

debugging

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 two heuristics should take at most a couple of seconds on the 1000 point example - if your code takes much longer, try to discover why, and explain in your readme file.

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-smallest.c

Rewrite the TOURshow function so that it pritns the PostScript program - basically, just 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.

Save your PostScript program to a file by typing "a.out < tsp1000.txt > tour1000.ps". To view type "gs tour1000.ps".

If your picture has many crossing lines, this indicates you made an error writing the insertion heuristic

See the Frequently Asked Questions page for more info on PostScript.

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

Here's the source of our TSP test data. A 1,139 node TSP problem and a 3,795 node TSP problem that arise from circuit drilling have available in our input format.

Here's the biggest TSP problem that has been solved to date and its optimal solution. It contains each of the 13,509 cities in the continental US with population over 500. It was not solved until 1998! Here's the 13,509 city problem in our file format.

Here's a nice pictorial survey of the history of the TSP problem.

Kevin Wayne