4 ms·

"I’ve got to do a letter drop across 30+ local addresses. Is there an app that can plan the optimal route?" well,we still need a bit of research for this...

• scrollaway 6y ago
  Getting XKCD/1425 vibes off this one :)
  • qorrect 6y ago
    Same! :)
• bigiain 6y ago
  30+(a number smaller than, say, a hundred or two) is totally brute forcable. I have a python script that plans walking routes between attractions at a large-ish festival that pre-calculates shortest paths by brute forcing dijkstra's algorithm between every pair of ~200 "intersections" in a minute or two on my laptop. (The app can then just look up the route by start/end location and draw it on a map) Travelling salesman is hard, but even O(n!) is trivial on machines today where n is small. And there are simplifications and approximations that get something like within 1% of the theoretical shortest path in something like O(n log(n)) time (with significant startup/preprocessing time, but where N is between a few thousand and a few million these work).
• oliv__ 6y ago
  Really? This is not a solved problem?
  • lucasfdacunha 6y ago
    It's a very well known issue and it has been studied for a long time. https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Travelling_salesman_problem It's a classic NP-Hard problem. And depending on the size of the sample we can have pretty much the best route available, but we still don't have a way to solve this 100% accurately (particularly for large sample size)