I want to describe this as one of the most famous problems I’ve encountered in all of computer science and operations research: given a list of cities and the distances between each pair of them, find the shortest possible route that visits every city exactly once and returns to the starting point. This is the Traveling Salesperson Problem (TSP), and I find it fascinating precisely because it’s so easy to state yet computationally so hard to solve exactly for large inputs — it’s a canonical NP-hard problem that has driven decades of algorithmic research.
History and Background
The mathematical roots of the problem trace back to the 1800s, with William Rowan Hamilton’s icosian game (1857) touching on the idea of visiting every vertex of a graph exactly once. The problem in its modern “traveling salesman” framing was studied more formally starting in the 1930s, notably by Karl Menger in Vienna. It gained major research traction in the 1950s and 1960s, when Dantzig, Fulkerson, and Johnson (1954) solved a 49-city instance using linear programming and cutting planes — a landmark achievement that essentially founded the field of combinatorial optimization. The problem was later shown to be NP-hard, cementing its central role in complexity theory.
Problem Statement
I define it as: given a complete weighted graph $G = (V, E)$ where $V$ represents cities and edge weights represent distances (or travel costs) between them, find a Hamiltonian cycle (a cycle visiting every vertex exactly once and returning to the start) with the minimum possible total edge weight.
Core Concepts
- Hamiltonian cycle: a cycle in a graph that visits every vertex exactly once before returning to the origin.
- Symmetric vs. asymmetric TSP: in the symmetric case, distance from $A$ to $B$ equals distance from $B$ to $A$; in the asymmetric case, they may differ (e.g., one-way streets).
- NP-hardness: the property that no known algorithm can solve all instances of the problem in polynomial time, meaning exact solutions become computationally infeasible as the number of cities grows.
- Exact vs. heuristic/approximation algorithms: exact methods (like dynamic programming or branch-and-bound) guarantee optimality but scale poorly; heuristic methods (like nearest neighbor or 2-opt) find good but not guaranteed-optimal solutions quickly.
- Held–Karp dynamic programming: the classic exact algorithm using bitmask state representation, solving TSP in $O(n^2 2^n)$ time — far better than brute-force $O(n!)$, though still exponential.
How It Works
I’ll describe the Held–Karp dynamic programming approach, which is the standard exact method:
- I fix a starting city, say city 0.
- I define a state $(S, j)$ representing the minimum cost of a path that starts at city 0, visits exactly the set of cities $S$ (which includes $j$), and ends at city $j$.
- Base case: $C({0}, 0) = 0$.
- For each subset $S$ containing city 0 and each city $j \in S$ (other than 0), I compute $C(S, j)$ by considering every possible previous city $k \in S \setminus {j}$: $C(S, j) = \min_{k}\big(C(S \setminus {j}, k) + d(k, j)\big)$.
- I build up these values for increasing subset sizes, from small subsets to the full set of all cities.
- The final answer is $\min_j \big(C(V, j) + d(j, 0)\big)$ — the minimum cost of a path visiting all cities, closed back to the start.
Working Principle
The logic here is dynamic programming over subsets, exploiting the principle of optimality: the best way to visit a specific set of cities and end at a particular city can be built from the best way to visit a slightly smaller set and end at some other city, plus one more edge. By using a bitmask to represent which cities have been visited, I can systematically enumerate all $2^n$ subsets without redundant recomputation, which is what brings the complexity down from factorial ($n!$, brute-force permutations) to exponential-but-much-smaller ($n^2 2^n$).
Mathematical Foundation
The Held–Karp recurrence is:
$$ C(S, j) = \min_{k \in S \setminus {j}} \big[ C(S \setminus {j}, k) + d(k,j) \big] $$
with base case:
$$ C({1}, 1) = 0 $$
(using city 1 as the fixed start, 0-indexed or 1-indexed depending on convention), and final answer:
$$ \text{Optimal Tour Cost} = \min_{j \neq 1} \big[ C(V, j) + d(j,1) \big] $$
For heuristic methods, the 2-opt local search improvement swaps two edges whenever:
$$ d(a,b) + d(c,d) > d(a,c) + d(b,d) $$
for edges $(a,b)$ and $(c,d)$ in the current tour, replacing them to strictly reduce total tour length.
Diagrams
flowchart TD
Start([Start: n cities, distance matrix]) --> Base["C({start}, start) = 0"]
Base --> Loop["For each subset size, for each subset S containing start"]
Loop --> Inner["For each city j in S: compute C(S,j) via min over previous city k"]
Inner --> Grow{All subset sizes processed?}
Grow -- No --> Loop
Grow -- Yes --> Close["Compute min over j of C(V,j) + d(j,start)"]
Close --> End([Return optimal tour cost and path])
Pseudocode
function HeldKarp(dist[1..n][1..n]):
// dp[S][j] = min cost path visiting set S, ending at city j, starting at city 1
dp[{1}][1] = 0
for subsetSize from 2 to n:
for each subset S of {1,...,n} containing city 1, with |S| = subsetSize:
for each j in S, j != 1:
dp[S][j] = infinity
for each k in S, k != j:
candidate = dp[S - {j}][k] + dist[k][j]
if candidate < dp[S][j]:
dp[S][j] = candidate
fullSet = {1, ..., n}
best = infinity
for j from 2 to n:
candidate = dp[fullSet][j] + dist[j][1]
if candidate < best:
best = candidate
return best
Step-by-Step Example
I’ll use a small 4-city example (A, B, C, D) with distances: A-B=10, A-C=35, A-D=25, B-C=15, B-D=30, C-D=20, starting from A.
For 4 cities, the Held–Karp table has states for subsets of {B,C,D} paired with an ending city. Rather than enumerating the full table, I’ll trace the resulting optimal tour directly, since with only 4 cities I can also reason via the 3 distinct Hamiltonian cycles (accounting for direction and reflection symmetry):
- A→B→C→D→A: 10+15+20+25 = 70
- A→B→D→C→A: 10+30+20+35 = 95
- A→C→B→D→A: 35+15+30+25 = 105
The minimum is A→B→C→D→A with total cost 70. Held–Karp’s dynamic programming table, built up subset by subset, arrives at this same value of 70 as the optimal tour cost.
Time Complexity
- Brute-force (try every permutation): $O(n!)$ — infeasible beyond roughly 12–15 cities.
- Held–Karp dynamic programming: $O(n^2 \cdot 2^n)$ — exact, but still only practical up to roughly 20–25 cities.
- Heuristic methods (nearest neighbor): $O(n^2)$ per construction, but no optimality guarantee.
- 2-opt local search improvement: $O(n^2)$ per pass, run iteratively until no improving swap is found.
- Christofides’ approximation algorithm (for metric TSP): $O(n^3)$, guaranteeing a solution within 1.5x of optimal.
Space Complexity
Held–Karp requires $O(n \cdot 2^n)$ space to store the DP table indexed by subset and ending city, which is the main practical bottleneck limiting it to smaller instances even though its time complexity alone might seem tractable for slightly larger $n$. Heuristic methods like nearest neighbor or 2-opt require only $O(n^2)$ space for the distance matrix and $O(n)$ for the current tour.
Correctness Analysis
Held–Karp’s correctness follows directly from the principle of optimality applied over subsets: $C(S, j)$ represents the true minimum cost of visiting exactly the cities in $S$ ending at $j$, and by induction on subset size, this is correctly built from smaller, already-optimal subset solutions — because any optimal path visiting $S$ and ending at $j$ must have arrived from some specific previous city $k \in S \setminus {j}$, and the sub-path up to $k$ must itself be optimal for the set $S \setminus {j}$ (otherwise I could substitute in a cheaper sub-path and improve the whole tour, a contradiction). Since I enumerate all valid predecessors $k$, the recurrence is guaranteed to find the true minimum. Heuristic methods like 2-opt, by contrast, only guarantee convergence to a local optimum, not global optimality — correctness there is about monotonic improvement, not about reaching the true minimum.
Advantages
- Held–Karp guarantees the exact optimal tour, useful when correctness matters more than raw scale.
- Heuristic and metaheuristic methods (nearest neighbor, 2-opt, simulated annealing, genetic algorithms) scale to thousands of cities with good (though not guaranteed-optimal) results.
- The rich body of research around TSP means many well-tested solvers and libraries already exist (e.g., Concorde TSP solver).
- Christofides’ algorithm gives a provable approximation bound for metric instances, offering a middle ground between speed and guaranteed quality.
Disadvantages
- Exact algorithms (brute force, Held–Karp) become computationally infeasible well before reaching real-world problem sizes (hundreds or thousands of cities).
- Heuristic methods offer no guarantee of finding the true optimal tour, only a “good enough” one.
- The problem’s NP-hardness means no known algorithm solves all instances efficiently, and this is unlikely to change without a breakthrough resolving P vs. NP.
- Real-world routing often has additional constraints (time windows, vehicle capacity, multiple vehicles) that turn plain TSP into the substantially harder Vehicle Routing Problem.
Applications
- Delivery and logistics route planning for couriers and last-mile delivery.
- PCB (printed circuit board) drilling path optimization to minimize drill-head travel.
- DNA sequencing and genome assembly, where fragment ordering can be modeled as a TSP-like problem.
- Astronomical telescope scheduling, minimizing time spent repositioning between observation targets.
- Circuit design and chip layout wiring optimization.
Implementation in C
#include <stdio.h>
#include <limits.h>
#define N 4 // number of cities
#define INF INT_MAX
int dist[N][N] = {
{0, 10, 35, 25},
{10, 0, 15, 30},
{35, 15, 0, 20},
{25, 30, 20, 0}
};
int dp[1 << N][N]; // dp[subset][j]
int heldKarp() {
for (int i = 0; i < (1 << N); i++)
for (int j = 0; j < N; j++)
dp[i][j] = INF;
dp[1][0] = 0; // start at city 0, subset {0}
for (int subset = 1; subset < (1 << N); subset++) {
if (!(subset & 1)) continue; // must include city 0
for (int j = 0; j < N; j++) {
if (!(subset & (1 << j)) || dp[subset][j] == INF) continue;
for (int k = 0; k < N; k++) {
if (subset & (1 << k)) continue; // k already visited
int nextSubset = subset | (1 << k);
int newCost = dp[subset][j] + dist[j][k];
if (newCost < dp[nextSubset][k])
dp[nextSubset][k] = newCost;
}
}
}
int fullSet = (1 << N) - 1;
int best = INF;
for (int j = 1; j < N; j++) {
if (dp[fullSet][j] != INF) {
int total = dp[fullSet][j] + dist[j][0];
if (total < best) best = total;
}
}
return best;
}
int main() {
int result = heldKarp();
printf("Optimal TSP tour cost: %d\n", result);
return 0;
}
Sample Input and Output
Input: 4-city distance matrix as defined above (A=0, B=1, C=2, D=3).
Output:
Optimal TSP tour cost: 70
This matches my manual enumeration of A→B→C→D→A as the optimal tour.
Optimization Techniques
- Use branch-and-bound with strong lower bounds (e.g., minimum spanning tree bound) to prune the search space in exact solvers for moderately larger instances.
- Apply the Lin–Kernighan heuristic, widely regarded as one of the most effective local search methods for large TSP instances.
- Use nearest-neighbor or greedy-edge construction to get a reasonable starting tour before refining it with 2-opt or 3-opt local search.
- For very large instances, use specialized solvers like Concorde, which combine cutting-plane methods with branch-and-cut to solve instances with tens of thousands of cities to provable optimality.
- Exploit problem structure (e.g., Euclidean/metric TSP) to apply approximation algorithms like Christofides’ with guaranteed bounds.
Common Mistakes
- Attempting brute-force enumeration on more than about 10–12 cities, which becomes computationally infeasible due to factorial growth.
- Forgetting to close the tour (returning to the starting city) when computing total tour cost.
- Confusing the Traveling Salesperson Problem with simpler problems like Minimum Spanning Tree or shortest path — TSP requires visiting every vertex exactly once in a cycle, a fundamentally different (and harder) constraint.
- Using a heuristic method’s result as if it were provably optimal, without acknowledging the approximation gap.
- Not accounting for asymmetric distances (one-way constraints) when the real-world scenario requires it, silently applying a symmetric-TSP algorithm to asymmetric data.
Further Reading
- Dantzig, G., Fulkerson, R., & Johnson, S. (1954). “Solution of a Large-Scale Traveling-Salesman Problem.” Journal of the Operations Research Society of America, 2(4), 393–410.
- Held, M., & Karp, R. M. (1962). “A Dynamic Programming Approach to Sequencing Problems.” Journal of the Society for Industrial and Applied Mathematics, 10(1), 196–210.
- Christofides, N. (1976). “Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem.” CMU Report.
- Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. The Traveling Salesman Problem: A Computational Study, Princeton University Press.
- Concorde TSP Solver: https://www.math.uwaterloo.ca/tsp/concorde.html
