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!"
Given a reasonable number of points, say, 300, You can't easily find the best solution, but you can find a "good enough" solution that'll be little worse than the best possible solution. One way to do so is to keep a list of the points in any order, calculate the length of visiting them in that order, and choose random portions of the list to try in inverse order and see if you're saving distance. After many iterations of trying that without getting an improvement, you consider the solution good enough.
I was about to say 13256278887989457651018865901401704640, but it appears this number is private property.
When I went to see Yosemite, and had just a day(half actually), I could not figure out in what sequence to follow so that I see most of the spots. such a application for google maps will be just great!
My Aurora : http://www.youtube.com/watch?v=o91ZsGwJYyg
FB : https://www.facebook.com/TanveersPhotography
As the saying goes artificial intelligence is no replacement for natural stupidity.
My old Advanced CS professor in high school gave an even better explanation to one geek who was trying to use a similar approach to minimise his search field in a classic travelling salesman problem: "Dear, you cannot have your dick in both hands or your soul in paradise, you have to chose: it is either a full enumeration or you can express it as a sorting problem".
If you deal with the original travelling salesman problem, neural net will not help you by any means. If you modify the problem so it can be solved by means different from brute force you might as well solve it properly. In that case it is no longer the classic "travelling salesman" though.
Baker's Law: Misery no longer loves company. Nowadays it insists on it
http://www.sigsegv.cx/
Maybe it wasn't but it definitely happens.
My previous job, working with a CNC engraving machine. If you want for example engrave letters (outlines), the tool runs over enclosed paths so the start and end of each path is at the same point. Each line is a single path associated with a single point. The tool needs to be moved between these points above the surface of the material. The ordering which path goes first is of little significance, but travel above the material takes time - so picking paths that are near results in a shorter time of the production. So you order the paths so that the total distance between start/end points is shortest. This is about 99% of the salesman problem - only exception is that you don't return to the first point after you finish your work. (also, "cities" are non-zero size and you may enter any at any given "city limit" point, but exit in the same place - any point of the path is good for the start/end point)
45 5F E1 04 22 CA 29 C4 93 3F 95 05 2B 79 2A B2
Agreed about approximation methods only being necessary for large values of n. I took it for granted that n was large, as it's not very interesting for n=5, for example. Furthermore, I think the summary was poorly phrased. I interpreted it as primarily asking, "Can the TSP (general form) be solved with the help of Google Maps?", not "Why isn't feature in Google Maps?". I suppose the latter is what the original submitter was really asking, but in that case, it really should not have been on /. to begin with. I chose the more interesting of the two questions :-)
-William Brendel
I remember that they had heuristics to give very close to the best path with a lot less computation for figuring out the actual correct solution. They used it for figuring out paths for things such as machines assembling circuit boards. Following the shortest path means they can produce them faster.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
I think they should fix the map data first. If I plan any route from home using Google Maps it starts by telling my to drive east through a neighbour's house and garden to get to a minor road instead of driving west to get to the main road. The lane which links my house and several others to the main road is clearly visible on the satellite image.
This seems to be caused by Google's use of the crappy Teleatlas map data.
It's never too late to have a happy childhood.