3.9 Held-Karp 旅行商算法

第三卷的收尾篇，我们挑一个 DP 的极限挑战——旅行商问题（Traveling Salesman Problem，TSP）的 Held-Karp 算法。前面几篇 DP 都是多项式时间，这一篇的 DP 是指数时间——但这个指数，已经比朴素枚举好了一个 $n$ 的因子。它是"DP 能把暴力搜索优化到什么程度"的标杆，也是通往第八卷 NP 完全性和第九卷近似算法的桥梁。

1.问题：走遍所有城市，回到起点，总路程最短

一个推销员要从某城市出发，访问每个城市恰好一次，最后回到起点，想让总路程最短。形式化：给完全图 $G=(V,E)$ （任意两城有边），找一个经过所有顶点恰好一次的哈密顿回路，使边权和最小。

朴素做法：枚举所有排列（城市访问顺序）。固定起点后共 $(n-1)!$ 种排列， $n=20$ 时约 $10^{17}$ ，彻底爆炸。这就是为什么 TSP 是经典的"难"问题——没有已知的多项式时间算法（第八卷会证明它是 NP 难）。

2.Held-Karp 的洞见：用子集记忆，省掉重复

朴素枚举为什么慢？因为它把"经过同一批城市、以不同顺序到达某城市"的路径当成完全不同的情况，重复计算了大量子结构。Held-Karp 的洞见：真正重要的不是"到达顺序"，而是"已经访问过哪些城市 + 当前在哪个城市"——这两件事决定了后续该怎么走。

于是状态定义为： $f(S, j)$ = 从起点出发，访问过集合 $S$ 里的城市、当前停在 $j$ 时，所走过的最短路程。 $S$ 是已访问城市子集（含起点和 $j$ ）， $j$ 是当前所在城市。

这里 $S$ 是一个子集，需要某种紧凑表示——这就是状态压缩（ bitmask，用一个二进制位串表示子集，第 $i$ 位为 1 表示城市 $i$ 在 $S$ 中）。所以 Held-Karp 常被叫做"状压 DP"。

3.状态转移

f(S, j)=\min_{i\in S\setminus\{j\}}\Big(f(S\setminus\{j\},\ i)+d(i,j)\Big)

意思是：当前停在 $j$ 、已访问 $S$ ，那"上一步"一定是从 $S$ 里某个其他城市 $i$ 走过来的——遍历所有可能的"上一站" $i$ ，取 $\min$ 。 $S\setminus\{j\}$ 表示"还没到 $j$ 时"访问过的城市集（比 $S$ 少一个 $j$ ）。

基底： $f(\{0\}, 0)=0$ （只访问了起点 0，停在 0，路程 0）。

答案：访问完所有城市后要回起点，所以

\min_{j\ne 0}\Big(f(V, j)+d(j,0)\Big)

遍历所有"最后一站 $j$ "，加上回起点的边 $d(j,0)$ ，取最小。

4.复杂度： $O(n^2 2^n)$

状态数：子集 $S$ 有 $2^n$ 种，每种子集里当前城市 $j$ 至多 $n$ 种，共 $O(n\cdot 2^n)$ 个状态。每个状态转移遍历 $O(n)$ 个"上一站"。总共 $O(n^2\cdot 2^n)$ ，空间 $O(n\cdot 2^n)$ 。

和朴素 $(n-1)!$ 比省了多少？ $n=20$ 时， $(n-1)!≈1.2\times10^{17}$ ，而 $n^2\cdot2^n≈4\times10^8$ ——从"宇宙寿命都算不完"压到"几秒能跑完"。DP 用"记忆子集"消掉了排列里的重复，把阶乘级压成指数级。这是状压 DP 的威力。

但注意——它仍然是指数的。 $2^n$ 在 $n$ 大时仍爆炸（ $n=30$ 已 $10^9$ ， $n=40$ 已 $10^{12}$ ）。所以 Held-Karp 只能解中小规模 TSP（ $n\le 20\sim25$ ）。大规模 TSP 得靠启发式或近似算法（第九卷）。

5.为什么这是"DP 的极限"

Held-Karp 揭示了 DP 的一个深刻事实：DP 不是万能的。 它能把指数级的重复子问题压成多项式倍（如背包的 $O(nW)$ 、LCS 的 $O(mn)$ ），但当问题本身的状态空间就是指数的（TSP 的子集数 $2^n$ ），DP 也只能做到指数。

这正好引出第三卷的统一图景：

贪心：多项式（ $O(n\log n)$ ），但要求贪心选择性质，适用面窄。
多项式 DP：当状态空间是多项式规模（如背包的 $(n,W)$ 、LCS 的 $(m,n)$ ），DP 多项式时间。
指数 DP（状压）：当状态空间含指数成分（如子集 $2^n$ ），DP 也指数，但比朴素好一个因子（ $n^2 2^n$ vs $n!$ ）。
彻底无多项式算法（NP 难）：连状压 DP 都不够，第八卷的 NP 完全性、第九卷的近似算法登场。

TSP 恰好站在这条光谱的"指数 DP"位置——它是 DP 能触及的极限，再往上就只能近似了。这就是为什么把它放在第三卷结尾：它既是 DP 的顶峰，又是 NP 理论的起点。

6.状压 DP 这个模式的普适性

Held-Karp 确立了状压 DP（bitmask DP）这个模式：状态里有一个"子集"维度，用位掩码表示。它在很多问题里复现：

哈密顿路径计数：经过所有点恰好一次的路径数。
最小顶点覆盖/集合覆盖的小规模精确解： $n$ 小时用状压枚举子集。
棋盘/网格上的状态压缩：如"铺砖问题"，每行的状态用位串表示。

识别信号是" $n$ 较小（通常 $\le 20$ ）+ 问题涉及'选了哪些元素'的子集"。遇到这种规模和结构，状压 DP 是第一选择。

7.练习

Q1. Held-Karp 的状态 $f(S,j)$ 是什么？ $S$ 和 $j$ 各代表什么？为什么用位掩码表示 $S$ ？

$f(S,j)$ = 从起点出发、已访问城市集 $S$ 、当前停在 $j$ 的最短路程。 $S$ 是已访问子集， $j$ 是当前所在城市。 $S$ 用位掩码（ $n$ 位二进制，第 $i$ 位 1 表示城市 $i$ 在 $S$ ）紧凑表示，便于用位运算增删元素（ $S\setminus\{j\}$ 就是把第 $j$ 位清零）。位掩码让 $2^n$ 个子集能高效索引和转移。

Q2. Held-Karp 是 $O(n^2 2^n)$ ，朴素枚举是 $(n-1)!$ 。 $n=20$ 时两者差多少？为什么 DP 仍算"快"？

$n=20$ ： $(n-1)!≈1.2\times10^{17}$ （宇宙级不可行）， $n^2 2^n≈4\times10^8$ （几秒可跑完）。DP 把阶乘级压成指数级，靠的是"记忆已访问子集 $S$ "消掉排列里的重复——不同到达顺序但相同 $(S,j)$ 的情况只算一次。但 $2^n$ 仍指数， $n=40$ 就 $10^{12}$ 不可行，所以只适合 $n\le 20\sim25$ 。

Q3.（思考题） TSP 是 NP 难（没有已知多项式算法），Held-Karp 又是指数的。那 DP 在这里的意义是什么？它和第九卷的近似算法是什么关系？

Held-Karp 的意义是精确解的极限：虽然指数，但把阶乘级压成指数级（ $n^2 2^n$ vs $n!$ ），让 $n\le 20\sim25$ 的中小规模 TSP 可精确求解。对大规模 TSP，精确 DP 算不动，才退而求其次用第九卷的近似算法（如 Christofides 1.5 近似）或启发式（模拟退火、遗传算法）。关系是：DP 管小规模精确解，近似/启发式管大规模可行解——这是"发现 NP 难后该怎么办"的两条互补路径。

8.小结

Held-Karp 用状压 DP， $O(n^2 2^n)$ 求解 TSP 的精确最优，比朴素 $(n-1)!$ 省了一个因子。它站在 DP 能力的极限——状态空间含指数成分（子集 $2^n$ ），DP 也只能指数。它确立了状压 DP 这个模式，又是连接第八卷 NP 完全性、第九卷近似算法的桥梁。第三卷到此结束，第二学习阶段（设计算法）的贪心与动态规划部分完成。

9.第三卷总结：贪心与动态规划的边界

回看第三卷九篇，最想让你带走的是这条判据：

一个最优化问题，先问"能不能当下就定一个最优选择"。能——贪心；不能——动态规划。

贪心（3.1–3.4：区间调度、Huffman、Kruskal、Dijkstra）快、简洁、 $O(n\log n)$ 居多，但要求贪心选择性质，凭直觉定准则容易错，必须用交换论证证明。动态规划（3.5–3.9：加权区间、矩阵链、背包、LCS、TSP）普适（只要最优子结构 + 重叠子问题），能解贪心解不了的问题，但代价是更高的复杂度（多项式甚至指数）。

两者都要最优子结构，分水岭只在贪心选择性质。遇到最优化问题，先用这条判据分流，再选范式。 下一篇卷我们进入第四卷——算法证明与性能分析，把这一卷里反复用到的"交换论证""剪切粘贴"等证明工具，连同递归树、主定理、摊还分析，系统讲透。