
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 yearold laptop 55 seconds to do the bruteforce search (written in C) to find the shortest path. Therefore it should take my laptop about 442 years to solve a 20point 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 4line group: The coordinates are always nonnegative integers. For instance, the set "A4" consists of the 4 corners of a square with sidelength 4 and whose lowerleft 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 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 bruteforce 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 commentingout the first 4 lines in the Netlogo code procesure "bestpath". 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. 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 yourdistance divided by the bestdistance 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 AltEnter on that link goes to your
paper. 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 mindboggling. Applications include the usual routing problems for school buses, and postal deliveries, warehouse productpicking, 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. 