Held–Karp: Dynamic Programming for the Travelling Salesman

The idea: remember sets, not orders

The travelling salesman problem asks for the shortest closed tour that visits every city once. Trying every order means (n−1)!/2 tours. Held–Karp (1962) notices that a half-finished tour only matters through two things: which cities it has visited and where it stands now. The order inside does not matter for the rest of the trip, so only the shortest path for each (set, end city) pair needs to be kept.

The table dp[S][j]

Fix the start city A. For a set S of the other cities and a city j in S, dp[S][j] is the length of the shortest path that starts at A, visits exactly the cities of S, and ends at j. S is stored as a bitmask: bit 0 is B, bit 1 is C, and so on, so mask 0101 is {B, D}. Each cell on the page shows the length and the city just before j, for example 127 ← C.

dp[{j}][j] = d(A, j)                                   one city: go straight there
dp[S][j]   = min over k in S∖{j} of dp[S∖{j}][k] + d(k, j)

for size = 2 … n−1:                       # smaller sets first
    for each mask S with size bits:
        for each j in S:
            P = S & ~(1 << j)                # S without j
            dp[S][j] = min(dp[P][k] + d[k][j] for k in P)

The last city before j is some k in the rest of the set, and the path up to k must itself be the shortest one through S∖{j} ending at k. That is the whole recurrence. On the canvas the cell being filled is orange, the cells it reads are blue, the winning one is green, and the map draws the winning path with its last edge in orange. Cells where j is not in S are grey: those states do not exist. (Demo 1: 4 cities, fill the table, trace the tour.)

Closing the tour and tracing back

When the full set is done, each dp[all][j] is a path through every city ending at j. Adding the edge home gives a tour: the answer is the smallest dp[all][j] + d(j, A). Two cells always tie, because a tour and the same tour walked backwards have the same length; the page keeps the first.

The table stores the length, not the tour. To read the tour, start at the winning cell and follow the stored predecessor: remove j from the set, move to that city's cell, and repeat until the set has one city, whose predecessor is A. On the 5-city map the close picks B (156 + 35 = 191); then dp[{B,C,D,E}][B] ← E, dp[{C,D,E}][E] ← D, dp[{C,D}][D] ← C and dp[{C}][C] ← A give, read backwards, the tour A → C → D → E → B → A = 45 + 34 + 45 + 32 + 35 = 191 (Demo 2: 5 cities, all 32 states).

How much work

There are (n−1)·2ⁿ⁻² states, and each takes at most n−2 additions, so the time is O(n²·2ⁿ) and the memory O(n·2ⁿ). Brute force checks (n−1)!/2 tours with n additions each. At 5 cities the two are close: 32 states and 52 additions against 12 tours and 60 additions (Demo 4: brute force, all 12 tours of 5 cities). The factorial wins very soon after that.

cities n	tours (n−1)!/2	states (n−1)·2n−2	Held–Karp additions
4	3	12	15
5	12	32	52
10	181,440	2,304	9,225
15	43,589,145,600	114,688	745,486
20	6.1 × 10¹⁶	4,980,736	44,826,643

It is still exponential: every extra city doubles the table. Around 25–30 cities the memory runs out, which is why large instances use heuristics or branch and cut instead. No algorithm with a better worst-case bound than O(n²·2ⁿ) is known for the general problem.

Why not just go to the nearest city?

Nearest neighbour builds a tour by always going to the closest unvisited city. It is fast but it never looks ahead. On the trap map it goes A → C (22) → B (54) → E (27) and is then left with D, far away: D costs 81 to reach and 74 to leave, for 258 in total. Held–Karp finds A → E → B → D → C → A = 205; nearest neighbour is 25.9% longer (Demo 3: nearest neighbour 258 vs optimal 205). On the other two maps it happens to find the optimum.

See also Travelling Salesman Heuristics, where nearest neighbour and 2-opt work on 12 cities and Held–Karp supplies the optimum to compare with, and 0/1 Knapsack and Matrix Chain Multiplication for the same fill-then-trace-back pattern on smaller tables.

The same idea without the end city is Bitmask DP over Subsets, on the assignment problem, where the mask alone is the state.

What the page leaves out

Asymmetric distances (one-way streets), where the same table works but a tour and its reverse no longer tie; saving memory by keeping only two set sizes at a time, which loses the trace back; the path version (no return to the start) and the bottleneck version; branch and bound, cutting planes and the Concorde solver; and approximation algorithms such as Christofides' 1.5-approximation for metric distances.

References

Wikipedia: Held–Karp algorithm

Held and Karp (1962): A Dynamic Programming Approach to Sequencing Problems, SIAM Journal

William Cook: The Traveling Salesman Problem (University of Waterloo)