Slashdot Mirror
Where's the Traveling Salesman for Google Maps?
Komi writes "Has anyone tackled the Traveling Salesman Problem with Google Maps or any other online mapping tool? I've searched, but can't find anything. To me this seems like such an obviously cool function. I'm not up to date on algorithms, so perhaps this isn't really tractable for large values of n. But for small numbers (maybe up to 5), this could at least be brute-forced. I would love to use this when I have errands to run, and I want an overall optimal route. So if this hasn't been done, someone please do it!"
By "tackle the problem", do you mean "make it not NP-hard anymore"? If so then, no, it has not been "tackled". However, algorithms exist that approximate a solution to the problem, as is the case with many NP-hard/NP-complete problems.
-William Brendel
First of all TSP is not NP-Complete it is NP-hard. This means we couldn't find a polynomial algorithm that reduces TSP to a NP-Complete problem: it either exists, but it wasn't found, or it doesn't exist and then it's even harder than NP-Complete. Second, intractable means "unsolvable by a Turing Machine in a finite time", which is not true, since you can find a naive algorithm that takes a lot of time, but finishes. The algorithm is like this: generate all possible paths in the graph and test if it's a minimal solution. The number of paths is less than |E|!, where E is the set of edges. The solution space is finite so the problem is solvable in finite time.
The traveling salesman problem wasn't meant to be tested in real life.
;) )
Actually, travelling salesman solvers are used in all kinds of real world applications.
Some examples can be found here: http://www.tsp.gatech.edu/apps/index.html
A TSP solver on google maps would be useful to some people (such as travelling salesmen
I could imagine tourists using such a function to plan a route around all the sights they want to see
It could also be used by anyone who needs to make several deliveries
However, in graphs upholding the triangle inequality (that is, if the distance A->C is d then the distance A->B plus B->C is at least d) there are algorithms that do give guaranteed good approximations. So in the real world you are correct.
As an example of how approximations tend to fail we can look at a case where the greedy inversions of pairs you suggest breaks down (the lameness filter screws up my fine ASCII art. The numbers now signify nodes and the initial path runs in number order):
Now, this is not a good path through all the points on this map, but flipping the order of any pair will only make the path worse. The correct solution would be much shorter, just going straight through the top and bottom rows. But that path cannot be reached by greedingly inverting the order of pairs.Okay, fine:
http://gebweb.net/optimap/
to clarify: what's called the travelling salesman problem is not the travelling salesman's problem. math should call the former the visiters' problem (or something), though this is your problem as well (with errands). there's no efficient algorithm for it.
real travelling salesman have a solved problem: walking along each road once, selling to each house along the way.
Need to type accents and special characters in Windows? Use FrKeys
The submitter obviously understands Google... first link if you search Google for "map 'traveling salesman'" gives you http://gebweb.net/optimap/ ... is that what you mean?
Support NYCountryLawyer RIAA vs People
"Sure I could just google it myself, but if I post to Slashdot I waste *everyone's* time!"
http://gebweb.net/optimap
1. Type this into Google: travelling salesman google maps
2. Click "Search"
3. Click the first result: "TSP Solver for Google Maps"
4. Practice searching for things more