Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 9 down vote accepted

The travelling salesman problem is completely different from the shortest path from A to B. A difficult travelling salesman problem is one where there are 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 more than the number of atoms in the universe; but navigation from A to B has only two places to visit 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 get a route which is guaranteed to be at most 50% longer than the best route, even in the worst case. Usually it does much better than 50% and simple adjustments can close the gap even further.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.