Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 11 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 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.

share|cite|improve this answer

Your Answer


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.