Held–Karp TSP 动态规划

状态 ​

固定起点 $r$。对 $S\subseteq V$ 且 $r,v\in S$，令

$$dp[S,v]=\text{从 }r\text{ 出发，恰访问 }S\text{ 并在 }v\text{ 结束的最小路径权}.$$

基例 $dp[\{r\},r]=0$，其他不可行状态为 $+\mathrm{\infty }$。

转移与恢复 ​

对 $v\ne r$，

$$dp[S,v]=\underset{u\in S\setminus \{v\}}{min}(dp[S\setminus \{v\},u]+w(u,v)).$$

最后答案为 $\underset{v\ne r}{min}dp[V,v]+w(v,r)$。为每个状态保存取得最小值的父终点 $u$，可逆向恢复 Hamilton 回路。共有 $O(n{2}^n)$ 状态，每次枚举 $O(n)$ 前驱，时间 $O(n^2{2}^n)$、空间 $O(n{2}^n)$；按子集大小滚动可省值空间但会影响路径恢复。

四点状态层图像 ​

四个城市中，先计算所有含 $r$ 的二点路径，再由二点状态扩到三点，最后扩到全体。仅记录集合 $S$ 不够：到达同一集合时停在不同 $v$，下一条边代价不同，终点是 Markov 状态的一部分。

边界与同名消歧 ​

一般图可把缺边设 $+\mathrm{\infty }$；有限 Hamilton cycle 上负边权不造成无限循环，因为每点只访问一次，但数值溢出要处理。这是 exact exponential DP，不是近似算法；Christofides公理库Christofides 算法Christofides algorithm用 MST、奇度点最小完美匹配和 Euler shortcut 构造 metric TSP 的 3/2 近似。以多项式时间换 3/2 比率。Held–Karp 还指 TSP 的 LP 下界，不能与本动态规划混同。

状态枚举与空间 ​

只枚举含 $r$ 且含终点 $v$ 的状态可减少常数；按 $|S|$ 从小到大处理，确保前驱层已完成。使用 bitmask 时 $n$ 需适合机器字，或用多字 bitset，不能把 $2^n$ 状态寻址视为无限可用。

若只求最优值，可保留相邻两个子集大小层，但每层仍有 $\mathrm{\Theta }((\genfrac{}{}{0ex}{}{n}{n/2})n)$ 峰值状态；简单滚动并不能降为多项式空间。恢复路径需要父表或再次计算选择。

表的计算与回溯顺序 ​

固定起点 0 后，按子集大小从小到大枚举 $S\subseteq V\setminus \{0\}$。只有 $j\in S$ 的状态 $DP[S][j]$ 有效；计算时遍历 $i\in S\setminus \{j\}$，并保存达到最小值的前驱 $parent[S][j]=i$。最终再加边 $j\to 0$ 取最小闭环。

恢复路线时从最佳终点 $j$ 和全集 $S$ 开始，反复读取前驱并清除当前 $j$ 的 bit，直到空集，再逆序并补起点。若只滚动保留相邻子集大小层，可降常数空间，却会丢失直接回溯信息；需要重算或另存选择。

状态数为 $(n-1)2^{n-2}$ 量级，每状态枚举至多 $n$ 个前驱，时间 $O(n^2{2}^n)$、空间 $O(n{2}^n)$。位掩码让集合操作常数化只在 $n$ 能装入机器字时成立，不会把指数状态数变成多项式。

参考资料

• Michael Held, Richard Karp, A Dynamic Programming Approach to Sequencing Problems, SIAM, 1962.
• Richard Bellman, Dynamic Programming Treatment of the Travelling Salesman Problem, JACM, 1962.