Traveling Salesman Problem Explained With an Example
Quick answer: The traveling salesman problem (TSP) asks for the shortest route that visits each city in a list exactly once and returns to the start. With n cities there are (n − 1)!/2 possible tours, so brute force fails quickly: 20 cities already give about 60 quadrillion tours. The problem is NP-hard, and no fast algorithm is known for all cases, yet clever methods solve real instances with tens of thousands of stops exactly, and good approximations are fast.
A delivery driver must visit 20 addresses and return to the depot. What is the shortest route? This sounds like a simple puzzle, but it is one of the most famous hard problems in mathematics and computer science: the traveling salesman problem.
The Problem
Given \(n\) cities and the distance between every pair, find the shortest round trip that visits each city exactly once. Each such route is called a tour.
A Four-City Example
Take four cities A, B, C and D with these distances (in km):
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 2 | 9 | 10 |
| B | 2 | 0 | 6 | 4 |
| C | 9 | 6 | 0 | 3 |
| D | 10 | 4 | 3 | 0 |
Starting from A, there are only \(\frac{3!}{2} = 3\) different tours:
| Tour | Length |
|---|---|
| A → B → C → D → A | 2 + 6 + 3 + 10 = 21 |
| A → B → D → C → A | 2 + 4 + 3 + 9 = 18 (shortest) |
| A → C → B → D → A | 9 + 6 + 4 + 10 = 29 |
With four cities you can check every tour by hand. The trouble starts as the list grows.
Why Brute Force Fails
For the usual symmetric TSP (where A to B costs the same as B to A) with \(n \ge 3\) cities, fix the starting city. The remaining \(n – 1\) cities can be visited in \((n-1)!\) orders, and each tour is counted twice (forward and backward), so there are
\[ \frac{(n-1)!}{2} \text{ tours}. \]
| Cities | Possible tours |
|---|---|
| 5 | 12 |
| 10 | 181,440 |
| 15 | about 43.6 billion |
| 20 | about \(6.1 \times 10^{16}\) |
| 30 | about \(4.4 \times 10^{30}\) |
Checking every tour for 30 cities would take longer than the age of the universe, even at a trillion tours per second.
Is There a Fast Method?
The number of tours alone does not prove the problem is hard, because clever algorithms avoid checking tours one by one. The Held–Karp dynamic programming algorithm (1962) solves any instance in about \(n^2 2^n\) steps, far fewer than \((n-1)!/2\), but still exponential, and it remains the best known worst-case bound for exact solutions in general.
Finding the shortest tour is NP-hard, and the decision version (“is there a tour of length at most \(B\)?”) is NP-complete. An exact polynomial-time algorithm that solves every TSP instance would imply \(P = NP\), settling the famous P vs NP problem.
How Real Instances Get Solved Anyway
- Exact methods: linear programming with “cutting planes” and branch-and-bound, used by the Concorde solver, prove optimality without checking every tour. A team led by William Cook found and proved an optimal tour for an 85,900-point circuit-board instance (pla85900) in 2005 to 2006, and in 2024 to 2025 proved an optimal 81,998-stop walking tour of bars across South Korea, using estimated walking times from a routing engine.
- Approximations: for the symmetric metric TSP, where distances obey the triangle inequality (going directly is never longer than going via a third city), Christofides’ algorithm (1976) always finds a tour at most 1.5 times the optimum. In 2020, Anna Karlin, Nathan Klein and Shayan Oveis Gharan improved this worst-case guarantee, by a tiny amount, for the first time in over 40 years. Without the triangle inequality, no such guarantee is possible unless P = NP.
- Heuristics: methods like 2-opt and Lin–Kernighan quickly find tours that are often within a few percent of the best in practice, though without a proven worst-case bound.
Where It Is Used
Delivery routing, drilling holes in circuit boards, scheduling telescope observations, DNA sequencing and manufacturing all involve TSP-like problems. Its cousin, crossing every edge once, is the easy problem Euler solved for the bridges of Königsberg.
Common Misconceptions
“Always go to the nearest city next.” That greedy rule is fast but can produce tours much longer than the best one.
“NP-hard means unsolvable.” No. It means no fast method is known for every case; many practical instances are solved exactly or very nearly.
Watch: The Traveling Salesman Problem in Video
If you learn better by watching, these videos are worth your time.
Check Your Understanding
Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.
Answer each question and press Submit to see your result right away.
Frequently Asked Questions
What is the traveling salesman problem?
Finding the shortest round trip that visits each of a set of cities exactly once and returns to the start.
Why is the traveling salesman problem hard?
The number of possible tours grows like a factorial, and even the best known exact algorithms take exponential time in the worst case. Finding the shortest tour is NP-hard.
Is the traveling salesman problem NP-complete?
The decision version, asking whether a tour of length at most B exists, is NP-complete. The optimization version, finding the shortest tour, is NP-hard.
Has the traveling salesman problem been solved?
Not in general, but specific instances with tens of thousands of cities have been solved exactly with advanced methods.
Where is the traveling salesman problem used?
In delivery routing, logistics, circuit board manufacturing, scheduling and genome sequencing.
Keep Exploring
- Seven Bridges of Königsberg: Euler’s Proof Explained
- P vs NP Explained Simply: Is It Solved in 2026?
- Ramsey Numbers Explained: The Party Problem and R(5,5)
Sources and Further Reading
Related to This Article
More math articles
- Economic Incentives: Choices, Constraints and Evidence
- Correlation Is Not Causation
- Counterclaims and Rebuttals
- How to Find Adjacent Angles
- New Immigration, Ellis Island, and Angel Island
- How to Find Measures of Variability? (+FREE Worksheet!)
- 5th Grade SBAC Math Practice Test Questions
- Properties of Absolute Value: A Deep Dive
- The Ultimate 6th Grade Scantron Performance Math Course (+FREE Worksheets)
- DNA, Genes, and Chromosomes


What people say about "Traveling Salesman Problem Explained With an Example - Effortless Math"?
No one replied yet.