3 ms·

Google Maps doesn’t need to solve the traveling salesman problem (shortest route between all nodes in a network). To find a route between two points on a graph

Google Maps doesn’t need to solve the traveling salesman problem (shortest route between all nodes in a network). To find a route between two points on a graph is just a shortest path problem, solvable by Dijkstra's algorithm and very much in P. (They almost certainly use heuristic algorithms that are more efficient than Disjkstra’s of course, since the size of the graph of all roads is such that a V^2 algorithm is still fairly expensive to run)

eru 4y ago
> Google Maps doesn’t need to solve the traveling salesman problem (shortest route between all nodes in a network). To be more precise, the traveling saleman problem asks for the shortest tour that visits all nodes in a directed, weighted graph. That's a general graph. If you do this on a map, your travel times have a lot of structure already. See https://en.wikipedia.org/wiki/Travelling_salesman_problem#Special_cases https://en.wikipedia.org/wiki/Travelling_salesman_problem#Sp... especially 'Metric' and 'Euclidean'. And, of course, when asked for directions Google Maps gives you just the shortest path between two nodes; or perhaps the shortest path that visits a given sequence of nodes in a fixed order. Google Maps doesn't (yet?) re-shuffle your stops for you. If it did that in general, it would indeed have to solve something at least as hard as the (metric) TSP. (Of course, they could also only support that feature for eg up to five stops. That would be comfortably in P.)
boloust 4y ago
> They almost certainly use heuristic algorithms that are more efficient than Disjkstra’s of course There are techniques like contraction hierarchies[1] that can efficiently compute exact shortest paths on extremely large road network graphs. [1]: https://en.m.wikipedia.org/wiki/Contraction_hierarchies https://en.m.wikipedia.org/wiki/Contraction_hierarchies

eru 4y ago

> Google Maps doesn’t need to solve the traveling salesman problem (shortest route between all nodes in a network). To be more precise, the traveling saleman problem asks for the shortest tour that visits all nodes in a directed, weighted graph. That's a general graph. If you do this on a map, your travel times have a lot of structure already. See https://en.wikipedia.org/wiki/Travelling_salesman_problem#Special_cases https://en.wikipedia.org/wiki/Travelling_salesman_problem#Sp... especially 'Metric' and 'Euclidean'. And, of course, when asked for directions Google Maps gives you just the shortest path between two nodes; or perhaps the shortest path that visits a given sequence of nodes in a fixed order. Google Maps doesn't (yet?) re-shuffle your stops for you. If it did that in general, it would indeed have to solve something at least as hard as the (metric) TSP. (Of course, they could also only support that feature for eg up to five stops. That would be comfortably in P.)

boloust 4y ago

> They almost certainly use heuristic algorithms that are more efficient than Disjkstra’s of course There are techniques like contraction hierarchies[1] that can efficiently compute exact shortest paths on extremely large road network graphs. [1]: https://en.m.wikipedia.org/wiki/Contraction_hierarchies https://en.m.wikipedia.org/wiki/Contraction_hierarchies