Just had fun for my project in data Structure and Algorithm class, building Traveling Salesman Problem on a real data about crime records happened in Pittsburgh, USA in 1990. The data consists the location of the crime happened.
The task is building a minimum TSP path and a optimum path using brute force, then implement it into Google Earth by making a KML file.
Here is the data CrimeLatLonXY1990
I tried to run the code for data record 12 to 18.
Beware, since in this task I am comparing Minimum TSP Path (Blue Line) to Optimum Brute Force path (Red Line), the brute force would be running in N! times to compute the minimum path.
So if I choose record 12 to 18, there will be 7 records: 12,13,14,15,16,17,18.
Brute force will test the path for all of the possibilities, which means in this case, there will be 7! possibilities.
I tried to run it for 10 nodes, and it goes crazily slow. So don’t try it for more than 9 nodes.
Final result on Google Earth.