1. The tools
   
2. Your job
   
3. Your output
   
4. About the TSP

Tools:

Read the whole desription below, download the files, try the Netlogo program before pondering how to solve these kinds of problems.

You will be given several sets of points (points.csv) to try your algorithms on -- there will be a set with just 4 points in a square arrangement, and other sets with more points randomly placed.The largest set will have 13 points, and so there are 239,500,800 distinct paths through those 13 points starting from the first.  It takes my 6 year-old laptop 55 seconds to do the brute-force search (written in C) to find the shortest path.  Therefore it should take my laptop about 442 years to solve a 20-point path.  You'll be given many sets from 8 points to 13 points.

 points.csv -- (download and look at this file with a text editor) has several different named sets of points, each set consisting of a 4-line group:
- the 1st line contains the name of the set (e.g. "A8") followed by the length of the shortest path through it
- the 2nd line contains the list of the x-coordinates of the points
- the 3rd line has the y-coordinates. 
- the 4th line has the shortest path sequence found by brute-force search.

The coordinates are always non-negative integers.  For instance, the set "A4" consists of the 4 corners of a square with side-length 4 and whose lower-left corner is the origin.

You'll also be given a Netlogo program (yes, Netlogo. Really.) called ShowPath.nlogo (download this, and put it in the same folder as the points.csv file) which will allow you to visualize the sets of points, the best path through them and your own calculated solutions.

Your Job:

Your job in this assignnment is to come up with an algorithm to try to find a short path going through all the points in a given set and returning to the first point. 

Do not resort to brute-force exhaustive search. 

Write a program (yes, it's come to this)... that will take the coordinates of a set of points (like "A4" or "A8" or any of the others) and finds the shortest path from the first point and then back to it after passing through all the others, within a reasonable time of your choosing.  And write the sequence of points into a CSV file along with the name of the set (e.g. "A8"). StudentPaths.csv (download and put into the same folder) is a sample of such an answer file.

ShowPath will allow you to see your path and calculate its ratio with the best path.  I have disabled the display of the shortest path for all sets except the easiest ones ("A4" and "A8") because I don't suggest looking at the answers before trying your own ideas.  However, you can remove that obstacle by commenting-out the first 4 lines in the Netlogo code procesure "best-path".  I suggest doing so only after you've worked on this problem for a while.

Once you have an algorithm running, you can try it on all of the sets and publish your results (ratios relative to the best paths) into the Google sheets page for that purpose.

Your Output:

Post your ratio results on the TSP Results page.  That page will display your best ratios for the datasets that you've tried - the ratio is your-distance divided by the best-distance and should be no more than 2.5.

See last semester's TSP Results page.

Write a a paragraph or two in a Google Doc.  In it, describe the adventures you had in solving TSP approximately.  What technique(s) did you use.  Failures?  Successes?  Then go to the TSP Results page and attach a link to this document to your name in the left column, so that pressing Alt-Enter on that link goes to your paper.

About TSP:

There are many algorithms for attempting to solve the TSP.  It has a rich history and literature because it is simple to explain to people without reference to any math, and the estimates of work for small numbers of cities are mind-boggling.  Applications include the usual routing problems for school buses, and postal deliveries, warehouse product-picking, etc. But problems in other areas can also be mapped onto it -- mapping genomes, scanning circuit boards for manufacturing problems, guiding lasers to produce crystal art, aiming telescopes for star and galaxy surveys...

The Genetic Algorithm video that we saw in class shows just one of the algorithms (and there are many more video tutorials describing this type of algorithm).  Another optimization algorithm is called "simulated annealing".  And there are graph algorithms that might be useful for small sets of points, like "convex hull", though they tend to be irrelevant for larger sets with many more points in the middle.