THE FOLD / BOSS / THE GAUNTLET / THE HELD-KARP
THE HELD-KARP
exact TSP by bitmask DP — n! tours in 2^n states
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Held–Karp algorithm solves the travelling salesman problem exactly by dynamic programming. Instead of trying all n! tours, it fills a table dp[set][city] = the cheapest way to start at the origin, visit exactly that set of cities, and end at that city. Because the future depends only on which cities remain and where you are — not the order you got there — subproblems are shared, and 2n·n states replace n! permutations.
It is the founding example of dynamic programming (1962).
LIT verified live: over 80 random graphs (n=3…7) the Held–Karp optimal tour length equals the brute-force minimum over all permutations (window.__heldkarp). FIG no framing; exact optimum.
It is the founding example of dynamic programming (1962).
LIT verified live: over 80 random graphs (n=3…7) the Held–Karp optimal tour length equals the brute-force minimum over all permutations (window.__heldkarp). FIG no framing; exact optimum.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-gauntlet — visit every station and return, at the least total cost, the whole run optimised. Held–Karp is that gauntlet solved exactly. AVAN (AI) built the instrument: the bitmask DP over subsets, the tour reconstruction, the brute cross-check.
Credit as content: Michael Held & Richard Karp (1962), independently Bellman. The weave: David names the gauntlet; I memoise by (visited-set, current-city) and confirm the DP optimum matches an exhaustive search over tours.
Credit as content: Michael Held & Richard Karp (1962), independently Bellman. The weave: David names the gauntlet; I memoise by (visited-set, current-city) and confirm the DP optimum matches an exhaustive search over tours.
3 ONE DIMENSION
A state is (which cities visited, where you are now). Two different visiting orders that reach the same set at the same city are the same subproblem — so they merge, collapsing n! orderings into 2n·n states.
4 TWO DIMENSIONS · INTERACTIVE
Cities on a plane; Held–Karp finds the shortest closed tour, checked against the brute-force minimum.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the optimal closed tour through every city.
AVAN’s addition (the inverse-companion): the exponential collapses because the future depends only on which cities remain and where you are, not the order you visited them. So subsets share subproblems and 2n·n states replace n! permutations. The inverse of ‘enumerate every ordering’ is ‘memoise by (visited-set, current-city) — the path’s history compresses to a bitmask.’ Magenta is the n! tours never enumerated; green is the 2n·n states that suffice. Still exponential, but the gap between 15! and 215 is dynamic programming’s whole point.
LIT Genuine Held-Karp algorithm (Held & Karp 1962; Bellman). Verified live: the bitmask DP over subsets returns an optimal closed-tour length equal to the brute-force minimum over all permutations for 80 random distance matrices (n=3..7) (window.__heldkarp.matchesBrute).
FIG No framing: the subset DP, the tour reconstruction, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — the future depends only on (visited-set, current-city), so orderings that reach the same state merge and 2^n*n states replace n! permutations; magenta is the n! tours never enumerated, green the 2^n*n states. Still exponential, but the gap between 15! and 2^15 is dynamic programming's point.
FIG No framing: the subset DP, the tour reconstruction, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — the future depends only on (visited-set, current-city), so orderings that reach the same state merge and 2^n*n states replace n! permutations; magenta is the n! tours never enumerated, green the 2^n*n states. Still exponential, but the gap between 15! and 2^15 is dynamic programming's point.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GAUNTLET · David Lee Wise (ROOT0), with AVAN