COS 126 TSP Assignment Checklist

Part 0: preparation (0 points)

Copy the following files from /u/cs126/files/tsp to an empty directory:

POINT.h   point.c    TOUR.h     tour.c      tsp-brute.c  tsp.c
tsp4.txt  tsp10.txt  tsp100.txt tsp1000.txt tsp10000.txt tsp13509.txt

You may do this with the following command:

cp /u/cs126/files/tsp/* .

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.

First, compile the program with the command:

gcc126 tsp.c point.c tour.c

You can execute the code with the command:

a.out < tsp10.txt

If you do this, you will get the following output:

in TOURshow()
in TOURdist()
total distance = 0.000000

Second, write code for TOURshow(). It should traverse the circular linked list and print the x-y coordinates of each city in the list.

The "global" variable tour points to the first node on the tour.

Use the interface function POINTprint() to print each point. See point.c for what the function does.

To get started, print out only the first node in the tour, and test your code.

To print out the whole tour, you will need to use some kind of loop. Recall from the Sedgewick readings that with ordinary linked-lists, the last node on the list points to NULL; with circular linked-lists the last node on the list points to the first node.

If your function is working properly, you will get the following output for the 10 city problem.

(0.1791, 0.7507)
(0.7327, 0.8574)
(0.8127, 0.6145)
. . .
(0.4106, 0.8469)
in TOURdist()
total distance = 0.000000

Note that the points seem to be out of order. That's because TOURinsert() inserts each new point between the first and second points on the current tour. So if the order of the original points is ABCDEF, then the tour will be AFEDCB.

Third, write code for TOURdist(). It should traverse the circular linked list and return the total distance traveled. The code will be similar to that of TOURshow(), so you should be able to do this without any help.

Use the interface function POINTdist() to compute the Euclidean distance between a pair of points.

You should get the following output:

(0.1791, 0.7507)
(0.7327, 0.8574)
(0.8127, 0.6145)
. . .
(0.4106, 0.8469)
total distance = 3.264113

If you've gotten to this point, you should feel a sense of accomplishment, as working with linked list is quite difficult at first!

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 is a PostScript comment since it beging with a '%' symbol. So, you should not modify the client program at all. All other lines will be interpreted as PostScript, so be sure to remove any debugging printf statements.

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