旅行商 TSP（状压 DP）

动态规划 · 集合当下标 · Held-Karp

n! 条路线，怎么剪

推销员要走遍 n 座城市各一次、回到起点，求最短回路——旅行商问题。暴力枚举全排列 O(n!)：20 城就是 2.4×10¹⁸ 条路线。可仔细想：走到半路时，决定未来的只有两件事——去过哪些城（不在乎顺序！）和现在人在哪。不同顺序、同一批城、同一个落脚点的路线，只需要留最短的那条。

把集合压进一个整数

「去过哪些城」是个集合——用二进制 mask 压缩：第 i 位为 1 表示城 i 已访问。状态 dp[mask][i] = 已访问 mask、现在在城 i 的最短路程，转移时枚举上一站 j：dp[mask][i] = min (dp[mask∖{i}][j] + d[j][i])。下表 8 行就是含起点的全部 mask（二进制行标），逐格点亮、黄格 = 胜出的前置状态；填到全集行后，补上回起点的边取 min。右侧代码随每一步同步高亮。

	0	1	2	3
0001	0
0011
0101
0111
1001
1011
1101
1111

4 座城市各访问一次回到起点 0，求最短回路。全排列是 O(n!)；状压 DP 的洞察：走到半路，重要的只有「去过哪些城」和「现在在哪」——把集合压成二进制 mask 当行下标：dp[mask][i]。起点 dp[0001][0] = 0

1function tsp(d: number[][]): number {
const n = d.length, FULL = (1 << n) - 1;
const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
dp[1][0] = 0;                                // 从城 0 出发
for (let mask = 3; mask <= FULL; mask++) {
  if (!(mask & 1)) continue;                 // 必含起点
  for (let i = 1; i < n; i++) {
    if (!(mask & (1 << i))) continue;
    const prev = mask ^ (1 << i);            // 去掉 i 的前置集合
    for (let j = 0; j < n; j++)              // 上一站 j
      if (prev & (1 << j))
        dp[mask][i] = Math.min(dp[mask][i], dp[prev][j] + d[j][i]);
  }
}
let best = Infinity;
for (let i = 1; i < n; i++)                  // 回到起点收尾
  best = Math.min(best, dp[FULL][i] + d[i][0]);
return best;
19}

距离: 4 城对称矩阵（见代码）
状态数: 2ⁿ·n = 64

状压 DP 的边界与家族

复杂度：状态 2ⁿ·n 个、每个转移 O(n) → O(2ⁿ·n²)——从 n! 到指数，是巨大的降维。
实用上限：n ≈ 20（约 4 亿次运算）；再大交给近似/启发式（最近邻、2-opt、LKH）。
填表序：mask 从小到大天然满足拓扑序——子集永远先于超集就绪。
家族：子集枚举 DP（3ⁿ）、轮廓线 DP（棋盘覆盖）、集合划分——「集合当下标」一脉相承。

至此 DP 大类八页集齐三种状态设计：序列前缀（LIS/LCS）、区间（石子合并）、集合（本页）——动态规划的想象力，全在「状态怎么定义」这一步。