the Held-Karp TSP algorithm
/ held karp /
The travelling salesman problem (TSP) asks for the shortest tour that starts at a home city, visits every other city exactly once, and returns home. The brute-force approach tries all (n-1)! orderings of the cities, which is astronomically slow even for 15 cities. The Held-Karp algorithm is the classic dynamic-programming attack: it still takes exponential time, but it replaces factorial growth with the much smaller 2^n growth, turning a hopeless 15-city problem into an easy one and a 20-city problem into something a laptop can do.
The key realisation is that to extend a partial tour, you do not need to remember the whole order you visited cities in — you only need two things: which cities you have already visited (a subset, stored as a bitmask) and which city you are currently sitting in. Everything about how you will finish the tour depends only on those two facts, so many different visit-orders collapse into one state. Define dp[mask][i] as the length of the shortest path that starts at the home city, visits exactly the set of cities in mask, and ends at city i (with i in mask). The base case is dp[{home, j}][j] = dist(home, j). The transition: to reach dp[mask][i], you arrived from some previous city j in mask (j not equal to i), so dp[mask][i] = min over j of dp[mask without i][j] + dist(j, i). The final tour length is min over i of dp[full set][i] + dist(i, home).
There are 2^n subsets times n end-cities, so O(2^n times n) states, and each takes O(n) work to consider all predecessors, giving O(2^n times n^2) time and O(2^n times n) space. This is exponential — TSP is NP-hard and no polynomial algorithm is known — but it is dramatically better than O(n!) and is provably exact, not an approximation. The space, not the time, is usually what stops you: storing 2^n times n numbers is fine around n = 20 but hopeless by n = 30. For larger instances people switch to approximation algorithms (like Christofides for the metric case) or branch-and-bound; Held-Karp is the gold standard for getting the exact optimum on small inputs.
Four cities, home = 0. To compute dp[{0,1,2}][2] (visited 0,1,2, now at 2), you could have come from 1: dp[{0,1}][1] + dist(1,2). dp[{0,1}][1] = dist(0,1). So dp[{0,1,2}][2] = dist(0,1) + dist(1,2). The full-set entries dp[{0,1,2,3}][i] + dist(i,0) are compared to find the best closed tour.
State = (set of visited cities, current city); the path order beyond that is irrelevant.
Held-Karp is exact and exponential, not a loophole around NP-hardness: it merely beats O(n!) down to O(2^n times n^2). Its memory wall (2^n entries) usually bites before its time, capping practical use near n = 20.