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?
2026-03-28 03:34:51.1774668891
Travelling salesman and NP Hard
498 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
There are 1 best solutions below
Related Questions in GRAPH-THEORY
- characterisation of $2$-connected graphs with no even cycles
- Explanation for the static degree sort algorithm of Deo et al.
- A certain partition of 28
- decomposing a graph in connected components
- Is it true that if a graph is bipartite iff it is class 1 (edge-coloring)?
- Fake induction, can't find flaw, every graph with zero edges is connected
- Triangle-free graph where every pair of nonadjacent vertices has exactly two common neighbors
- Inequality on degrees implies perfect matching
- Proving that no two teams in a tournament win same number of games
- Proving that we can divide a graph to two graphs which induced subgraph is connected on vertices of each one
Related Questions in NP-COMPLETE
- Divide set into two subsets of equal sum and maximum this sum
- Linear Programming Primal-Dual tough question
- Bipartite Graph Partitioning (special case)
- Minimise the sum of pairwise distances between labelled points in a metric space subject to covering some set of labels
- How should a chain of proof be written?
- Show the NP completeness of Hamiltonian Path with the knowledge of an directed Euler graph
- Integer Programming (non $0-1$) Reduction to show $NP$ Completeness
- Categories with at most one arrow between any pair of objects. (appears in NPC)
- Find a generalized path cover of a square graph
- Generalize minimum path cover
Trending Questions
- Induction on the number of equations
- How to convince a math teacher of this simple and obvious fact?
- Find $E[XY|Y+Z=1 ]$
- Refuting the Anti-Cantor Cranks
- What are imaginary numbers?
- Determine the adjoint of $\tilde Q(x)$ for $\tilde Q(x)u:=(Qu)(x)$ where $Q:U→L^2(Ω,ℝ^d$ is a Hilbert-Schmidt operator and $U$ is a Hilbert space
- Why does this innovative method of subtraction from a third grader always work?
- How do we know that the number $1$ is not equal to the number $-1$?
- What are the Implications of having VΩ as a model for a theory?
- Defining a Galois Field based on primitive element versus polynomial?
- Can't find the relationship between two columns of numbers. Please Help
- Is computer science a branch of mathematics?
- Is there a bijection of $\mathbb{R}^n$ with itself such that the forward map is connected but the inverse is not?
- Identification of a quadrilateral as a trapezoid, rectangle, or square
- Generator of inertia group in function field extension
Popular # Hahtags
second-order-logic
numerical-methods
puzzle
logic
probability
number-theory
winding-number
real-analysis
integration
calculus
complex-analysis
sequences-and-series
proof-writing
set-theory
functions
homotopy-theory
elementary-number-theory
ordinary-differential-equations
circles
derivatives
game-theory
definite-integrals
elementary-set-theory
limits
multivariable-calculus
geometry
algebraic-number-theory
proof-verification
partial-derivative
algebra-precalculus
Popular Questions
- What is the integral of 1/x?
- How many squares actually ARE in this picture? Is this a trick question with no right answer?
- Is a matrix multiplied with its transpose something special?
- What is the difference between independent and mutually exclusive events?
- Visually stunning math concepts which are easy to explain
- taylor series of $\ln(1+x)$?
- How to tell if a set of vectors spans a space?
- Calculus question taking derivative to find horizontal tangent line
- How to determine if a function is one-to-one?
- Determine if vectors are linearly independent
- What does it mean to have a determinant equal to zero?
- Is this Batman equation for real?
- How to find perpendicular vector to another vector?
- How to find mean and median from histogram
- How many sides does a circle have?
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.