Attached is my alternative program. Like the posted code above, it doesn’t necessarily provide the optimum (or shortest) tour through all points. As I stated above, as the number of points grow, the possible number of tours increases as a factor (n!). Therefore, the code can't search every possible path, but uses an approximating algorithm that in most cases finds a tour that is short, but not guaranteed to be the shortest. But it’s very fast. The program is a Windows executable which uses the
Chrisofides algorithm with
2-opt optimization. Feed it a csv file consisting of pairs of lat/long points, and it outputs a kml file.
Here are a few examples of output displayed in Google Earth:
48 US state capitols
Sweden Cities (on my laptop, an 1.6GHz i5, it runs in approx. 2 seconds)
It took me longer to accomplish this because I don’t live in my parent’s basement. Due to size, the C++ source code is available via pm.