TSP: битовое DP (Held-Karp)

1function tspHeldKarp(dist: number[][]): number {
2  const n = dist.length
3  const FULL = 1 << n
4 
5  // d[mask][i] = минимальный путь из 0, обошли mask, стоим в i
6  const d: number[][] = Array.from({ length: FULL }, () =>
7    new Array(n).fill(Infinity))
8  d[1][0] = 0 // только старт, mask = {0}
9 
10  for (let mask = 1; mask < FULL; mask++) {
11    if (!(mask & 1)) continue
12    for (let last = 0; last < n; last++) {
13      if (!(mask & (1 << last))) continue
14      const cur = d[mask][last]!
15      if (cur === Infinity) continue
16      for (let next = 0; next < n; next++) {
17        if (mask & (1 << next)) continue
18        const nm = mask | (1 << next)
19        const cost = cur + dist[last]![next]!
20        if (cost < d[nm][next]!) d[nm][next]! = cost
21      }
22    }
23  }
24 
25  let best = Infinity
26  for (let last = 1; last < n; last++) {
27    best = Math.min(best, d[FULL - 1]![last]! + dist[last]![0]!)
28  }
29  return best // O(2ⁿ·n²) вместо n!
30}