Slashdot Mirror

← Back to Stories (view on slashdot.org)

Where's the Traveling Salesman for Google Maps?

Posted by samzenpus on from the waffle-house-mod-soon-to-come dept.

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!"

6 of 125 comments (clear)

  1. Re:Just prove that P=NP by sigmoid_balance · · Score: 3, Informative

    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.

  2. Re:Google Maps is not required nor desired by actiondan · · Score: 4, Informative

    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

  3. Re:Acceptable solutions by jiushao · · Score: 4, Informative
    Interestingly this is not really the case in the general problem. Notably the travelling salesman problem is not in APX unless the hamiltonian path problem is in P. That is, unless P=NP, there exists no algorithm which can give an approximation of the solution to the travelling salesman problem which is guaranteed to be within a constant factor c of the correct answer.

    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):

    | 0 3 4 7 8
    |
    |
    |
    |
    | 1 2 5 6 9
    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.
  4. Re:"tackel the problem" == "make it not NP-hard"? by dintech · · Score: 3, Informative

    He's clearly aware of the intractability. From the summary, "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."

    And he's right. If you remember your computability and intractability lessons at Uni then you'll rember that TSP is quickly solvable for small values of n. Just like the summary states. Approximations are only required for larger values of n where the solution takes much longer to arrive at.

  5. J.F.G.I. by portnoy · · Score: 3, Informative

    "Sure I could just google it myself, but if I post to Slashdot I waste *everyone's* time!"

    http://gebweb.net/optimap

  6. Re:He is out, travelling? by KillerCow · · Score: 5, Informative

    Has anyone tackled the Traveling Salesman Problem with Google Maps or any other online mapping tool? I've searched, but can't find anything.


    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