4 ms·
"What's the shortest route that connects all 5162 locations" AKA Traveling salesman problem? Even with a few hundred cities that would be difficult to find the
by jffry 13y ago
"What's the shortest route that connects all 5162 locations"
AKA Traveling salesman problem? Even with a few hundred cities that would be difficult to find the optimal solution, let alone thousands. You could find a decent to even good solution with other algorithms, though
- Derander 13y agoOne thing to note about this specific problem: this is an example of the traveling salesman problem with a metric. This makes efficient (good) approximation algorithms a possibility. Many NP-hard approximation algorithms classes teach a 1.5 approx known as the Christofides algorithm. This algorithm is guaranteed to provide an approximate solution that is no worse than 1.5 times the optimal total distance, and often much better.
- pyk 13y agoFor the ambitious, some of the leading code for solving the TSP to optimality is Concorde (at best it has optimally solved an 85,900 "city" instance): http://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm http://www.math.uwaterloo.ca/tsp/concorde/downloads/download... or solve/run Concorde on Argonne National Laboratory's server here: http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html Disclaimer: free for academic use
- jffry 13y agoAh, cool. So I guess I was wrong that a 5k-city solution was infeasible.