Goals

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.