Step 0:   preparation
  • Copy the tsp directory from the 126 ftp site.

    • Step 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 tour-inorder tsp.c point.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

  • 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 first 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. 
    (179140.0, 750703.0)
(410640.0, 846947.0)
(138430.0, 562658.0)
(394470.0, 679221.0)
(607060.0, 453077.0)
(374170.0, 695851.0)
(268540.0, 609753.0)
(425890.0, 376154.0)
(812660.0, 614479.0)
(732680.0, 857362.0)
In TOURdist()
Total distance = 0

  • 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: 
    (179140.0, 750703.0)
(410640.0, 846947.0)
(138430.0, 562658.0)
(394470.0, 679221.0)
(607060.0, 453077.0)
(374170.0, 695851.0)
(268540.0, 609753.0)
(425890.0, 376154.0)
(812660.0, 614479.0)
(732680.0, 857362.0)
Total distance = 3264089

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

    • Step 2:    nearest insertion

    For this step, your only task is to modify the TOURinsert() to perform the nearest insertion heuristic.

  • Copy the file tour-inorder.c from Step 1 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 tour-nearest.c tsp.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.

  • 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 you need to use a large value like infinity, consider using the macro INT_MAX defined in limits.h.

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

    • Step 3:    smallest insertion

    After doing Step 2, you should be able to do this step 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.

    • Step 4:   Turtle graphics output  

    For this step, you will modify the TOURshow() function so that it outputs a turtle graphics program that will plot the tour graphically.

  • Download and compile the latest version of turtle.c so that you can use the G command.

  • First, make a copy of your tour-smallest.c program and call it tour-turtle.c.

  • Basically, just regurgitate the sample turtle graphics code from the assignment, filling in the "G x y" commands with the x and y coordinates of each successive point in the tour. Use the POINTprintScaled() interface function to print points scaled to the 512 x 512 box. This function also removes the parentheses and comma when printing out the coordinates.

  • Do not print out the total distance at the end of TOURshow(); otherwise this line will produce an error with the turtle graphics parser. Also, be sure to remove any debugging printf statements.

  • Here is the correct output for the 1,000 city problem.


    • Written by Lisa Worthington and Kevin Wayne