4 ms·
What does the Traveling Salesman Problem have to do with typical GPS navigation? Typical use of a GPS device involves a start and an end point, and every once i
by wlievens 17y ago
What does the Traveling Salesman Problem have to do with typical GPS navigation? Typical use of a GPS device involves a start and an end point, and every once in a while a couple points in between, that ideally you may want in optimal order (though I doubt typical devices can do that for you). But there's nothing intractable about the scale of that.
- deleted 17y ago[deleted]
- deleted 17y ago[deleted]
- RiderOfGiraffes 17y agoSorry, you're right. My recent work has involved pathological cases of dynamic spanning trees, and I've recently proved that a sub-class is NPC, and I mis-spoke myself here. The SatNav problem is obviously easier. Given the power of the processor, limited memory, and complexity of streets (in the places I typically deal with) I still find it surprising. But you're right. Dijkstra's algorithm clearly solves this problem simply enough in O((|E|+|V|) log |V|) for the sparse case. Apologies.