Chapter 56: DSA The Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is one of the most famous, most studied, and most frustrating problems in all of computer science and mathematics.
It is very simple to state, but extremely difficult to solve — and that contrast is exactly what makes it so interesting.
Let me explain it to you like we are sitting together over coffee, with a piece of paper where I draw cities and roads, and we think through it slowly and honestly.
1. What is the Traveling Salesman Problem? (very clear definition)
Imagine a salesman who has to visit n different cities exactly once each.
He starts from his home city, visits every other city exactly once, and finally returns back home.
He wants to do this tour in such a way that the total distance travelled is as small as possible.
That’s the entire problem.
In mathematical terms:
Given a complete graph with n vertices (cities) and edge weights (distances between cities), find the shortest possible Hamiltonian cycle (a cycle that visits every vertex exactly once and returns to the starting vertex).
2. Very simple real-life example (so you can feel it)
Suppose there are only 4 cities: A (home), B, C, D.
Distances (in km):
| From \ To | A | B | C | D |
|---|---|---|---|---|
| A | — | 10 | 15 | 20 |
| B | 10 | — | 35 | 25 |
| C | 15 | 35 | — | 30 |
| D | 20 | 25 | 30 | — |
Now the salesman starts at A and must visit B, C, D exactly once and return to A.
Possible tours:
- A → B → C → D → A Distance = 10 + 35 + 30 + 20 = 95
- A → B → D → C → A = 10 + 25 + 30 + 15 = 80
- A → C → B → D → A = 15 + 35 + 25 + 20 = 95
- A → C → D → B → A = 15 + 30 + 25 + 10 = 80
- A → D → B → C → A = 20 + 25 + 35 + 15 = 95
- A → D → C → B → A = 20 + 30 + 35 + 10 = 95
So the shortest tours are 80 km long (two of them are equally good).
The problem is: find this minimum length systematically when there are dozens or hundreds of cities.
3. Why TSP is extremely hard
The number of possible tours grows factorially:
Number of different possible tours = (n−1)! / 2 (for undirected graph, because direction doesn’t matter and starting point is fixed)
Examples:
n = 5 cities → (5−1)! / 2 = 12 possible tours n = 10 cities → 1,814,400 tours n = 15 cities → 43,243,200,000 ≈ 43 billion n = 20 cities → 1.2 × 10¹⁷ (120 quadrillion) n = 50 cities → ≈ 10⁶⁴ (more than number of atoms in the universe)
This is why brute-force (trying all tours) is impossible even for n = 25–30.
4. TSP is NP-hard
TSP is NP-hard — one of the most famous NP-complete problems.
That means:
- We do not know any polynomial-time algorithm that always finds the optimal solution
- But if someone finds one → every NP problem can be solved in polynomial time (P = NP)
- Most experts believe P ≠ NP → no efficient exact algorithm exists
So in practice we have two main families of solutions:
- Exact algorithms (always give optimal answer, but very slow)
- Approximation / heuristic algorithms (give very good — but not always optimal — answers very fast)
5. Exact algorithms for TSP (what people use when n is small)
| Algorithm | Time Complexity (worst case) | Practical limit (approx) |
|---|---|---|
| Brute force (all permutations) | O(n!) | n ≤ 10–12 |
| Dynamic Programming (Held–Karp) | O(n² × 2ⁿ) | n ≤ 20–25 (very optimized) |
| Branch-and-bound + cutting planes | Very hard to say exactly | n ≤ 40–60 (with heavy optimization) |
Held-Karp dynamic programming is the most famous exact algorithm still used in practice.
6. Approximation & heuristic algorithms (what is used in real life)
For real-world problems (n = 100–10,000 cities):
| Algorithm / Method | Approximation ratio / Quality | Time complexity | Used in practice? |
|---|---|---|---|
| Christofides algorithm | 1.5× optimal guarantee | O(n³) | Yes (theoretical best) |
| Lin–Kernighan heuristic | Very close to optimal | O(n²) or better | Yes (very strong) |
| LKH-3 / Concorde | Often finds optimal solution | Practical | Yes (state-of-the-art) |
| Genetic algorithms, Ant colony, Simulated annealing | Good solutions | Variable | Yes (for very large n) |
7. Summary – TSP in one line each
- Find the shortest possible tour that visits every city exactly once and returns to the starting city
- NP-hard problem — no known polynomial-time exact algorithm
- Number of possible tours grows factorially → brute force impossible even for n ≈ 20
- Exact solution possible up to n ≈ 20–60 with heavy optimization (Held-Karp, Concorde)
- For larger n → use heuristics (Lin-Kernighan, LKH, genetic algorithms)
- One of the most studied, most famous, and most practically important problems in computer science
- Appears in almost every serious algorithms interview and every competitive programming contest at some level
Would you like to continue deeper into TSP?
Very common next topics people ask:
- Held-Karp dynamic programming explanation (with small example)
- Christofides algorithm – the famous 1.5-approximation
- How TSP solvers really work in practice (Concorde, LKH-3)
- TSP on grid / Euclidean TSP — special cases
- Approximation vs exact — when to choose which
- How interviewers ask TSP (common variations)
Just tell me which direction you want to go next — I’ll explain it in the same detailed, friendly, teacher style with lots of drawings and examples 😊
