Goals

  • Learn about the notorious traveling salesperson problem.

  • Learn to use linked lists.

  • Get more practice with ADT's.

  • Learn about measuring the running time of a program.

    • Testing and Hints

  • There are many sample data files (with extension .txt) available in /u/cs126/files/tsp/.

  • You may compare your results to our reference solutions by running the programs tsp-nearest126 and tsp-smallest126.

  • Additional hints are available here.

    • Timing a Program

  • Solve the 4 and 10 city problem using the brute force algorithm from Lecture P5. This is the program tsp-brute.c. To compile, use the following command: 
    gcc126 point.c tsp-brute.c
    The following command solves the 4 city example: 
    a.out < tsp4.txt
    Do not attempt to run on large inputs. It checks all N! permutations of cities. Instead, estimate (in years of CPU time) how long it would take for this algorithm to solve the 1,000 city problem. First, determine how long it takes to solve the 10 city example using the Unix /usr/bin/time command: 
    time126 a.out < tsp10.txt
    The "user time" reported is the number of CPU seconds used.

  • Use this, and the fact that the algorithm performs roughly N! steps, to estimate how long the 1,000 city problem will take. You may use Stirling formula for approximating factorials:
    n! ~ !=(n/e)^n sqrt(2 pi n)
    To avoid overflowing a calculator, take the (base 10) logarithm of the right hand side, do the arithmetic, and call the result x. Now, n! is roughly 10x.

    • Submission and readme  
  • Use the following submit command: 
    submit126 7 readme tour-nearest.c tour-smallest.c tourps-smallest.c
    Do not use different file names, except possibly for the optional extra credit.

  • The readme file should contain the following information. Here is a template readme file. Warning: you will lose points if you don't address these questions.

  • Name, precept number, high level description of code, any problems encountered, any help (if any) that you received, and any classmates with whom you collaborated.

  • Explain why you used a circular linked list instead of a regular linked list or array. Give specific reasons for each.

  • For each of the two heuristics, give the distance obtained for tsp10.txt, tsp100.txt, tsp1000.txt, and tsp13509.txt.

  • How long it takes the brute force program to solve the 10 city problem. Estimate how long it would take to solve a 1,000 city problem.

  • How long it takes your smallest insertion and nearest insertion heuristics to finish the 10,000 point file. Estimate how long they would take to finish a 100,000 point problem.

    • Extra Credit

  • Possibilities for improvement are endless. Here are some ideas. If you are shooting for an A+ and/or have previous programming experience, you should definitely attempt the extra credit.

  • For the extra credit, you are permitted to change any of the files (including tsp.c and TOUR.h) to suit your needs. Some of the suggested heuristics do not insert points in the same order as the input, so you will need a preprocessing step to determine the order. Other heuristics do a postprocessing step after all the points are inserted.

  • Be sure to include compilation instructions for your extra credit solution.

    • 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 are 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. This remarkable computational feat relied on theoretical ideas from "polyhedral combinatorics", and was not solved until 1998 by Applegate, Bixby, Chvatal and Cook.

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


    • Kevin Wayne