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.

    • Unix Tip of the Week

    Symbolic algebra packages like Maple and Mathematical can be extremely useful in your coursework, and they are easy to use Maple is installed on the arizona machines (maple and the X-Windows version xmaple). Here's a session to compute 50! exactly and in scientific notation. 

    tucson.Princeon.EDU% maple
> 50!;
       30414093201713378043612608166064768844377641568960512000000000000

> 1.0 * 50!;
                                             65
                               .3041409320 10
> quit;
tucson.Princeon.EDU%
    Maple can do much more than arbitrary precision arithmetic. Here's a session to compute the integral of x/(x^3 -1), and then evaluate it from 2 to infinity. 
    tucson.Princeon.EDU% maple
> int( x/(x^3-1), x );
                             2                 1/2                       1/2
     1/3 ln(x - 1) - 1/6 ln(x  + x + 1) + 1/3 3    arctan(1/3 (2 x + 1) 3   )

> int( x/(x^3-1), x = 2 .. infinity);

          1/2                       1/2             1/2
     1/6 3    Pi + 1/6 ln(7) - 1/3 3    arctan(5/3 3   )

> quit;

    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. To compute N! for large N, you can use one of the following two methods.

  • If you're mathematically inclined, 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.

  • Use Maple as described above.

    • Submission and readme  
  • Use the following submit command: 
    submit126 6 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 a 13,509 city problem that contains each of the 13,509 cities in the continental US with population over 500. The optimal solution was discovered in 1998 by Applegate, Bixby, Chvatal and Cook. using theoretical ideas from "polyhedral combinatorics." The following 15,112 city problem was solved to optimality in April, 2001, and is the current world record. It took 585,936,700 CPU seconds (along with alot of cleverness) to find the optimal tour through 15,112 cities in Germany.

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


    • Kevin Wayne