Goals

  • Learn about the notorious traveling salesperson problem.

  • Learn to use linked lists.

  • Get more practice with data types.

  • Testing and Hints

  • There are many sample data files (with extension .txt) available in /u/cs126/files/tsp/. Even more are available in the tsplib subdirectory.

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

    Submission and readme  
  • Do not submit TOUR.h, POINT.h, point.c, or tsp.c: we will use the copies provided. Do not use different file names, except possibly for the optional extra credit.

  • The readme.txt 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 your heuristics, give the distance obtained for tsp10.txt, tsp100.txt, tsp1000.txt, and tsp13509.txt.

  • For each of your heuristics, indicate how long it takes on tsp100.txt, tsp1000.txt, tsp5000.txt and tsp10000.txt. Timing with a stopwatch is sufficient. Give your answer to the nearest second. (For very short or very long times, answers like less than one second or more than 5 minutes are also acceptable.)
  • Check that your turtle graphics output is valid and stays within the 512 x 512 box.

  • Extra Credit

  • Possibilities for improvement are endless. Here are some ideas. If you are shooting for an A+, 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 3,795 node TSP problem that arises from circuit drilling is 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 linear and integer programming. 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.

  • Some folks even use the TSP to create and sell art. Check out Julian Lethbridge's page. Feel free to go crazy with PostScript (use fill instead of stroke) and make your own art.



  • Kevin Wayne