Held–Karp 算法：1962 年提出的旅行商问题精确求解动态规划方法

Held–Karp 算法，又称 Bellman–Held–Karp 算法，是一种动态规划算法，由 Bellman[1] 以及 Held 和 Karp[2] 于 1962 年各自独立提出，用于求解旅行商问题（TSP）。在 TSP 中，输入是一组城市之间的距离矩阵，目标是找到一条长度最短的巡回路线，使得从起点出发、恰好访问每个城市一次后返回起点。该算法能在指数时间内求出该问题以及若干相关问题（包括哈密顿回路问题）的精确解。

将城市编号为 1,2,…,n，任意指定 1 为“起点”城市（由于 TSP 的解是一个哈密顿回路，起点的选择无关紧要）。Held–Karp 算法首先对每个城市集合 S⊆{2,…,n} 以及每个不在 S 中的城市 e≠1，计算从 1 到 e、按某种顺序经过 S 中每个城市（且不经过其他城市）的最短单向路径。将该距离记为 g(S,e)，并用 d(u,v) 表示从 u 到 v 的直接边长度。我们从最小的集合 S 开始、到最大的集合 S 结束，依次计算 g(S,e) 的值。

当 S 含有两个或更少的元素时，计算 g(S,e) 只需考察一两条可能的最短路径。例如，g(∅︀,e) 就是 d(1,e)，而 g({2},3) 就是 1→2→3 的长度。同样，g({2,3},4) 是 1→2→3→4 或 1→3→2→4 中较短者的长度。

一旦 S 包含三个或更多城市，经过 S 的路径数量会迅速增长，但只需考察其中少数几条即可找到最短路径。例如，若 1→2→3→4 比 1→3→2→4 短，那么 1→2→3→4→5 必定比 1→3→2→4→5 短，因此 1→3→2→4→5 的长度不可能是 g({2,3,4},5) 的取值。类似地，若从 1 经过 {2,3,4} 到 5 的最短路径是 1→4→3→2→5，且从 1 经过 {2,3,4,5} 到 6 的最短路径以边 5→6 结尾，那么从 1 到 6 的整条路径必定是 1→4→3→2→5→6，而不可能是以其他顺序访问 {2,3,4} 所产生的另外五条路径中的任何一条。

更一般地，设 S={s1,…,sk} 是含 k 个城市的集合。对每个整数 1≤i≤k，记 Si=S∖{si}={s1,…,si−1,si+1,…,sk} 为从 S 中删去 si 后得到的集合。那么，若从 1 经过 S 到 e 的最短路径以 si 作为倒数第二个城市，则从该路径中去掉最后一条边必定得到从 1 经过 Si 到 si 的最短路径。这意味着从 1 经过 S 到 e 的最短路径只有 k 条候选，分别对应每个可能的倒数第二个城市 si，其长度为 g(Si,si)+d(si,e)，因此 g(S,e)=min1≤i≤kg(Si,si)+d(si,e)。

当对每个整数 2≤i≤n 都求出 g({2,…,i−1,i+1,…,n},i) 时，该阶段结束，由此得到从城市 1 出发、经过其他所有城市到达城市 i 的最短距离。接下来短得多的第二阶段将这些距离与边长度 d(i,1) 相加，得到 n−1 条可能的巡回路线，然后从中找出最短的一条。

最后，最短路径本身（而不仅是其长度）可以通过在存储 g(S,e) 的同时记录从 1 经过 S 到 e 的路径上倒数第二个城市的标号来重建，这只使空间需求增加一个常数因子。

Held–Karp 算法的时间复杂度为指数级 Θ(2nn2)，明显优于暴力算法的超指数级性能 Θ(n!)。然而，Held–Karp 需要 Θ(n2n) 的空间来保存函数 g(S,e) 的所有计算值，而暴力算法只需 Θ(n2) 的空间来存储图本身。

对于 {2,…,n} 的 k 元子集 S，计算一个 g(S,e) 值需要找出 k 条可能路径中最短的一条，每条路径通过将一个已知的 g 值与原始图中的一条边长度相加得到；也就是说，所需时间与 k 成正比。{2,…,n} 共有 (n−1k) 个 k 元子集，每个子集给出 n−k−1 个可能的 e 值。因此，计算所有 |S|=k 的 g(S,e) 值所需时间为 k(n−k−1)(n−1k)=(n−1)(n−2)(n−3k−1)，对所有子集大小求和的总时间为 (n−1)(n−2)∑k=1n−2(n−3k−1)=(n−1)(n−2)2n−3=Θ(n22n)。算法的第二阶段从 n−1 个候选中找出一条完整回路，耗时 Θ(n)，不影响渐近性能。

对于无向图，算法可以在 k=⌊n−12⌋ 步之后提前终止，并对每个 {(S,e):|S|=⌊n−12⌋,e∈Sc∖{1}} 求出 g(S,e)+g(Sc∖{1,e},e) 的最小值，其中 Sc 是 S 的补集。这类似于从 1 出发、在中点 e 相遇的双向搜索。然而，这只是常数因子的改进，不影响渐近性能。

存储大小为 k 的子集的所有 g(S,e) 值需要保留 (n−k−1)(n−1k)=(n−1)(n−2k) 个值。因此，完整的 g(S,e) 值表所需空间为 ∑k=0n−2(n−1)(n−2k)=(n−1)2n=Θ(n2n)。这里假定 n 足够小，使得 S 可以存储为常数倍机器字长的位掩码，而不是显式的 k 元组。

如果只需要最短回路的长度而不需要回路本身，那么可以通过注意到计算大小为 k 的 S 的 g(S,e) 只需要大小为 k−1 的子集的 g 值，来在一定程度上改进空间复杂度。只保留 S 大小为 k−1 或 k 的那些 g(S,e) 值，即 (n−1)[(n−2k−1)+(n−2k)] 个值，可将算法的最大空间需求（在 k=⌊n2⌋ 时达到）降至 Θ(n2n)。