I've wondered about this ever since I bought a satellite navigation system for my car 4 years ago but had no one to ask. If the travelling salesman problem is NP-Hard (which to my non-mathematical mind simply means a problem that will take a very long time to compute) then why is it that my satellite navigation system doesn't find it hard to do a subset of this problem, i.e. calculate a route from A to B? Surely, if it can calculate the shortest route from A to B then the algorithm for calculating the TSP is simply calculating the shortest route of each pair of points and then finding the shortest sum. Where is my thinking wrong is this?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
The travelling salesman problem is completely different from the shortest path from A to B. A difficult travelling salesman problem is one that has thousands of different sites to visit and one must find the best order in which to visit all them. The number of possible orderings is far greater than the number of atoms in the universe; but the problem of navigating from A to B has only two places to visit, and in only one order.
As a secondary point, just because finding the single best solution is very hard, doesn't mean that one cannot get close to optimal in practice (a GPS only needs to provide a good approximation, after all). There is an easy way (Christofides heuristic) to obtain a route that is guaranteed to be at most 50% longer than the best route, even in the worst case (assuming the triangle inequality). Usually it does much better than 50% and simple adjustments can close the gap even further.