Travelling Salesman (Held-Karp)

The travelling salesman problem (TSP) asks for the cheapest tour: start at home, visit every city exactly once, and return. Checking all orderings means (n-1)! tours — astronomical past a dozen cities. Held-Karp is a dynamic-programming attack that cuts this to about 2ⁿ·n²: still exponential, but it solves n ≈ 20 cities where brute force dies around n ≈ 12.

The key observation

Two partial routes that have visited the same set of cities and currently sit at the same city have identical futures — whatever you do next is the same for both, so only the cheaper one can matter. That collapses the explosion: instead of remembering full orderings, remember just *(which cities are visited, where you are now)*.

The DP

Let dp[S][j] = the cost of the cheapest path that starts at city 0, visits exactly the cities in set `S`, and ends at city `j` (with j in S). Build it from smaller sets: to end at j, you arrived from some other city k in S whose own subproblem dp[S minus j][k] is already solved.

1. 1Base case: dp[{0}][0] = 0 — sitting at home, nothing else visited.
2. 2Transition: dp[S][j] = min over k in S (excluding j) of ( dp[S without j][k] + dist[k][j] ).
3. 3Process sets in increasing size (or increasing mask value) so each smaller set is ready first.
4. 4Answer: min over j of ( dp[FULL][j] + dist[j][0] ) — visit everything, then return home.

function heldKarp(dist) {
  const n = dist.length, FULL = (1 << n) - 1;
  const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
  dp[1][0] = 0;                                   // start at city 0
  for (let S = 1; S <= FULL; S++) {
    if (!(S & 1)) continue;                       // tours must include city 0
    for (let j = 0; j < n; j++) {
      if (!(S & (1 << j)) || dp[S][j] === Infinity) continue;
      for (let k = 0; k < n; k++) {               // extend to an unvisited k
        if (S & (1 << k)) continue;
        const next = S | (1 << k);
        const cand = dp[S][j] + dist[j][k];
        if (cand < dp[next][k]) dp[next][k] = cand;
      }
    }
  }
  let best = Infinity;
  for (let j = 1; j < n; j++) best = Math.min(best, dp[FULL][j] + dist[j][0]);
  return best;
}