Held–Karp TSP 动态规划

形式陈述

状态

把旅行商问题视为优化问题：输入是一张带权完全图，目标是寻找最小权 Hamilton 回路。固定起点 $r$ 。对 $S\subseteq V$ 且 $r,v\in S$ ，令

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

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

转移与恢复

对 $v\ne r$ ，

dp[S,v]=\min_{u\in S\setminus\{v\}} \bigl(dp[S\setminus\{v\},u]+w(u,v)\bigr).

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

直觉

访问集合记录已经履行的“每城一次”约束，当前终点记录下一步成本所需的全部历史。删除最后一个顶点便得到更小子问题，因此状态按集合大小分层；指数复杂度来自必须区分不同已访问集合，而不是路径长度本身。

Held–Karp 的子集端点状态逐层扩展并闭合回路 — Held–Karp 的子集端点状态与闭合边

例子与边界

四点状态层图像

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

边界与同名消歧

一般图可把缺边设 $+\infty$ ；有限 Hamilton cycle 上负边权不造成无限循环，因为每点只访问一次，但数值溢出要处理。这是 exact exponential DP，不是近似算法；Christofides以多项式时间换 3/2 比率。Held–Karp 还指 TSP 的 LP 下界，不能与本动态规划混同。

状态枚举与空间

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

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

推论与应用

Held–Karp 是子集动态规划：状态 (S,v) 记录从起点访问恰好 S 并停在 v 的最短路，转移枚举最后一个前驱。指数来自 2^n 个子集，而非排列的 n! 条完整路线。

表的计算与回溯顺序

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

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

状态数为 $(n-1)2^{n-2}$ 量级，每状态枚举至多 $n$ 个前驱，时间 $O(n^22^n)$ 、空间 $O(n2^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.

形式陈述 ​

状态 ​

转移与恢复 ​

四点状态层图像 ​

边界与同名消歧 ​

状态枚举与空间 ​