Held–Karp TSP 动态规划

形式陈述

输入、路线与状态

把旅行商问题视为优化问题：给定 $n\ge1$ 个顶点的带实数边权完全图，固定起点 $r$ ，求访问每个其他顶点恰一次、最后返回 $r$ 的最小权路线。 $n\ge3$ 时这就是 Hamilton 回路； $n=2$ 时约定路线沿唯一边往返，它不是简单图中的环； $n=1$ 时直接返回费用为零的空路线。空图没有可选起点，本页不把它作为输入。

以下设 $n\ge2$ 。对 $S\subseteq V$ 、 $r,v\in S$ ，定义

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

基例是 $dp[\{r\},r]=0$ ；其他终点为 $r$ 的状态均不可行，值为 $+\infty$ 。

转移与恢复

对 $v\ne r$ ，按 $|S|$ 递增计算

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

任意目标路径删去最后一条边后，都落入某个前驱状态；反过来，把 $v$ 接到该状态的路径末端，不会重复顶点。这两向构造按集合大小归纳，证明递推恰给最小费用。最后补回起点的边，得到

\min_{v\ne r}\{dp[V,v]+w(v,r)\}.

为每个有限状态保存达到最小值的前驱 $u$ ，从最佳终点逆向清除当前顶点，直到 $\{r\}$ ，再逆序并补回起点，即可恢复路线。平局按固定顶点顺序处理。

这是子集动态规划。包含起点且终点不为起点的状态共有 $(n-1)2^{n-2}$ 个，另有一个起点基例。每状态至多检查 $n-1$ 个前驱，故时间为 $O(n^22^n)$ ，完整值表和父表各占 $O(n2^n)$ 个单元。这里把精确权重加法、比较和状态寻址计作单位操作；较长整数或多字掩码要另计位成本。

直觉

访问集合记录已经履行的“每城一次”约束，当前终点记录下一条边所需的历史。到达同一集合时，终点不同就可能有不同的后续成本；到达同一集合、同一终点的路径则可以只保留最便宜者。这样把约 $n!$ 条访问次序合并为子集与终点的状态表。

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

例子与边界

四个城市的完整末层

取城市 $r,a,b,c$ ，六条无向边权为

w(r,a)=10,\quad w(r,b)=15,\quad w(r,c)=20,\qquad w(a,b)=35,\quad w(a,c)=25,\quad w(b,c)=30.

二点状态分别为 $10,15,20$ 。例如三点集合 $\{r,a,c\}$ 中，终点为 $a$ 的费用是 $20+25=45$ ，终点为 $c$ 的费用是 $10+25=35$ 。全体顶点的三个末状态为

dp[V,a]=70,\qquad dp[V,b]=65,\qquad dp[V,c]=75.

加回闭合边后依次得到 $80,80,95$ 。一条最优路线是 $r,a,c,b,r$ ，费用 $10+25+30+15=80$ ；逆向路线也同费。这个例子同时说明，不能在每个集合上过早丢掉所有非最小终点状态。

缺边、负权与两种 Held–Karp

一般简单图可把缺边标为 $+\infty$ ，转移时跳过不可行前驱与缺边。最终值仍为 $+\infty$ 时报告没有路线，而不是读取不存在的父指针。负边权也可处理：合法路线的访问次数固定，不允许反复绕负环，因此不会因负权产生无界目标。

本算法精确求解，代价是指数时间。Christofides 算法针对非负、对称且满足三角不等式的度量 TSP，取得多项式时间的 $3/2$ 近似保证。另一个常被称为 Held–Karp bound 的对象是 TSP 的线性规划松弛下界，与这里的状态递推不同。

推论与应用

分层存储与回溯

第 $k$ 层只存 $|S|=k$ 的有效状态，数量为 $(k-1)\binom{n-1}{k-1}$ 。只求数值时，保留前后两层的峰值空间为 $\Theta(n\binom{n}{\lfloor n/2\rfloor})$ ，比完整值表少一个多项式因子，但仍是指数空间。分层集合需要紧凑索引；若仍分配整个掩码表，只覆盖旧值并不会减少已分配空间。

直接恢复路线需要所有选中状态的父信息。只保留相邻两层会丢失早期选择，可另存父表，或通过再次计算恢复；时间与空间应按采用的方案分别核算。整个算法统一使用含起点的集合 $S$ ，回溯在 $S=\{r\}$ 停止。

表示成本

当顶点数能装入机器字、状态地址也能被寻址时，增删一个顶点可用常数次位操作。多字位集和任意精度权重则按实际表示收费。无论表示多紧凑， $2^n$ 个不同访问集合仍须在最坏情形中加以区分。

参考资料

Michael Held and Richard M. Karp, “A Dynamic Programming Approach to Sequencing Problems”, Journal of the Society for Industrial and Applied Mathematics 10(1), 1962, pp. 196–210.
Richard Bellman, “Dynamic Programming Treatment of the Travelling Salesman Problem”, Journal of the ACM 9(1), 1962, pp. 61–63.

形式陈述 ​

输入、路线与状态 ​

转移与恢复 ​

四个城市的完整末层 ​

缺边、负权与两种 Held–Karp ​

分层存储与回溯 ​