3 ms·
> 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 p
by 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.)