要构造一条恰好访问每个地点一次的路线,通常不能每次都选当前最便宜的出边。这样做可能使某个未访问地点无法到达,也可能使最终返回起点的代价很高。枚举所有访问顺序确实能解决问题,但会重复处理许多子问题:不同的前缀可能为之后的行程留下完全相同的选择。
当我们能准确说明哪些前缀可以相互替代时,动态规划就有了用武之地。这里决定后续选择的是已访问顶点集合和当前终点。前缀内部的访问顺序会影响其代价,却不再影响哪些顶点尚可访问,或下一步可以走哪条边。对于每个这样的状态,我们只需保留代价最低的前缀。
这个方法给出精确解,但复杂度仍是指数级的。它利用的是顶点数较小时重复出现的状态,并不能让任意大规模的回路问题变得容易计算。
定义状态前先明确路线要求
顶点集合为 ,其中 。对不同的顶点 ,有向边 或者存在且具有整数代价 ,或者不存在。代价可以为零或负数。我们不假设代价对称,也不假设三角不等式成立。
从 0 出发的简单路径列出互不相同的顶点,以 0 开头,并且相邻顶点间都有对应的有向边。当 时,哈密顿(Hamilton)回路由一条访问全部 个顶点的这类路径,加上一条返回 0 的现有边组成。因此 0 在开头和结尾各出现一次,其他每个顶点恰好出现一次。我们的目标是最小化走过的全部 条边的代价之和。固定从顶点 0 出发不会遗漏任何回路:每个这样的回路都可以改写成以 0 开始的形式。
当 时,我们明确约定:不走任何边的回路代价为零,路径为 [0]。无需自环,也不计入自环,即使矩阵的对角线元素为负也一样。其他情况下,对角线元素同样无关,因为路径内部不允许重复访问顶点。
定义 14.1.1
(精确的已访问集合与终点状态)
对包含 0 的 和 ,令 为从 0 到 、已访问顶点集合恰好为 的简单路径的最小代价。如果不存在这样的路径,记 。
只含一个顶点的路径给出 。当 时,所有以 0 为终点的状态都不可达:从 0 开始的简单路径不能在内部返回 0。 或 的状态无效,也永远不需要使用。
“恰好”一词防止我们把经过额外顶点的低代价路径误当作尚未访问这些顶点的路径。终点也必不可少:访问同一集合的两条路径可能结束于不同顶点,因而接下来可用的边和边的代价也可能不同。
通过去掉最后一条边推导递推式
定理 14.1.2
(最后一条边递推式)
设 包含 0,且 、。符合 的路径在到达 之前,必然位于某个 ,并沿存在的边 到达 ,而且
这里没有候选值时,最小值为 。
证明
(去掉最后一条边,再把它接回去)
任取一条符合 要求的路径,去掉最后一条边 。由于列出的顶点互不相同,剩余路径恰好访问 ,并以 为终点。其代价至少为 ,所以完整路径的代价至少等于某个递推候选值。取代价最低的符合条件路径,就得到右侧最小值是所求值的下界。
反过来,取右侧一个可达候选值及实现它的最优前缀。顶点 不在该前缀的已访问集合中,故添加存在的边 后,得到一条已访问集合恰好符合要求的简单路径,且代价等于该候选值。最小候选值可以实现,于是得到反向不等式。若没有候选值,任何符合条件的路径也就不可能有最后一条边,因此该状态不可达。
证明透视
互不相同与“恰好”在哪里起作用
两个不等式都依赖简单路径的同一个性质:顶点互不相同。在下界部分,它保证去掉最后一条边后,剩余路径的已访问集合恰好是 。在上界部分,它提供 不在前缀的已访问集合中,所以添加 得到已访问集合恰好为 的简单路径。非常规之处在于两个不等式用的前缀不同:一个方向取 的最优路径,另一个方向则对每个候选 分别取最优前缀。证明从未用到代价的正负,只用到代价沿路径相加。论证对 归纳收尾:右侧每一项都对应少一个顶点的集合,基底是 。若没有互不相同这个条件,去掉最后一条边后前缀可能仍含 ,递推式就不再描述已访问集合。
不可达的前缀不提供候选值;没有候选值时,最小值为 。每个依赖状态的集合都少一个顶点,所以按集合大小计算是一种无环顺序。
有限图中只有有限条简单路径,所以即使某些代价为负,每个可达状态的最小值仍能取到。我们不会反复沿环松弛:每次转移都加入一个此前未访问的顶点。负权环不会使这个有限的简单路线优化问题无下界。
等价地,正向实现从一个可达状态 出发,选择任意 且边 存在的顶点,用 改进 。这与上述递推使用的是同一组转移,只是说明的方向相反。
为什么可以舍弃其他前缀
引理 14.1.3
(等价的前缀可以互换)
设两条从 0 出发的简单路径恰好访问同一集合 ,并以同一顶点 结束。若由 以外的一串顶点,再加上返回 0,能把第一条路径补全为哈密顿回路,则同一串顶点也能补全第二条路径,且两条回路的代价之差恰好等于两个前缀的代价之差。
证明
(后续行程只看集合和终点)
完成其中一个前缀的任何后续序列,都必须先使用 以外的顶点,再返回 0。另一个前缀具有相同的未访问顶点,且下一步的出发点同为 ,所以相同的后续序列对它也合法,增加的代价也相同。
因此,用最便宜的前缀替换更贵的前缀,既不会破坏后续行程的可行性,也不会增加总成本。这个论证不要求代价非负。但它要求后续行程的可行性与代价只依赖于已访问集合、当前终点和未来使用的边。如果额外约束依赖于此前的访问顺序,就可能需要更丰富的状态。
反例模式
到达某个终点的最便宜路径可能访问了错误的集合
考虑三个顶点,其中边 的代价为 1,边 、、、 的代价均为零。没有边 ,也没有其他边。唯一的哈密顿回路是 ,代价为 1。
然而,从 0 到终点 1 的最便宜简单路径是 ,代价为零。如果把它误当成只访问了 的前缀继续使用,就会得到错误路线 ,代价为零却重复访问了顶点 2。每个终点只保留一个最小值会丢失关键信息;必须区分 和 。
闭合路径是另一项要求
定理 14.1.4
(由全集状态得出最优回路)
设 。哈密顿回路存在,当且仅当有某个 使 有限,并且存在边 。这时最小回路代价为
证明
(回路就是全集路径加一条返回边)
每条哈密顿回路,都是一条从 0 出发、恰好访问 并以某个 结束的简单路径,再接上一条存在的边 ;反过来,每个这样的组合都是回路。其代价是路径代价加 。对固定的 ,后一项是常数,所以以 为最后顶点的最便宜回路,使用代价为 的路径。对 取最小值就得到公式;若没有符合条件的 ,就没有回路。
有限只能保证存在一条哈密顿路径,并不能保证存在回路:返回起点的边可能不存在。如果没有候选值,应报告不存在回路,而不是返回任意一个很大的数。
例题 14.1.5
(加上返回代价之后再比较完整路径)
考虑下面的有向代价矩阵,破折号表示不存在的边或不使用的对角线元素:
| 从 / 到 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | — | 2 | 9 | 8 |
| 1 | 6 | — | 3 | 7 |
| 2 | 4 | 5 | — | -2 |
| 3 | 1 | 6 | 4 | — |
对于 ,以 2 结束的路径是 ,代价为 ;以 1 结束的路径是 ,代价为 。继续到终点 3 时,比较 与 ,所以 。
| 全集状态的终点 | 返回代价 | 回路候选代价 | |
|---|---|---|---|
| 1 | 13 | 6 | 19 |
| 2 | 13 | 4 | 17 |
| 3 | 3 | 1 | 4 |
最优回路是 ,代价为 。例如,代价为 13、以 1 结束的全集路径是 ;它不是代价为 13 的回路,因为返回 0 还需加上 6。
常见错误
(只最小化路径代价,而不是回路代价)
取边 、、、 的代价都为 , 的代价为 , 的代价为 。最便宜的全集路径是 ,代价为 ,但返回要 ,这条回路代价是 。路径 的代价为 ,返回只要 ,回路代价为 。只按 选终点会返回 ,而不是最优的 ;比较终点之前,必须先加上返回代价。
编码集合,而不是编码访问顺序
使用整数掩码表示集合:当且仅当 时,第 位为 1。于是用 mask & (1 << i) 检查成员关系,用 mask | (1 << i) 加入此前不存在的顶点;全集的掩码是 (1 << n) - 1。位的位置代表顶点,写出的二进制数字不记录访问顺序。
每次正向转移都把一个零位设为一,因此新掩码的数值比旧掩码大。按掩码数值递增遍历因而是有效的拓扑顺序,尽管同一大小的集合在这个顺序中并不连续。一个状态用于扩展之前,会先收到所有可能的改进。
当某次转移严格改进一个状态时,为该精确状态在父指针表中保存前一个终点。去掉新终点就能确定前一个掩码。还原时必须同时保留当前掩码和终点:同一终点在不同子集状态下可能有不同的前驱。保留任意一个达到最小代价的前驱即可;输出要求并不规定回路必须按字典序最小。
可执行实现及其约定
输入是非空方阵,元素为整数或 None,其中 None 表示边不存在。整数零是真正的零代价边。忽略对角线元素。函数对最优回路返回 (cost, witness),不存在回路则返回 None。顶点数大于一时,路径末尾再次写出 0;单顶点约定返回 (0, [0])。函数只读取矩阵,不修改它。
def minimum_hamiltonian_tour(weights):
n = len(weights)
if n == 0 or any(len(row) != n for row in weights):
raise ValueError("a nonempty square matrix is required")
if n == 1:
return 0, [0]
limit = 1 << n
dp = [[None] * n for _ in range(limit)]
parent = [[None] * n for _ in range(limit)]
dp[1][0] = 0
for mask in range(1, limit):
if not mask & 1:
continue
for last in range(n):
cost = dp[mask][last]
if cost is None:
continue
for nxt in range(1, n):
if mask & (1 << nxt):
continue
edge = weights[last][nxt]
if edge is None:
continue
new_mask = mask | (1 << nxt)
candidate = cost + edge
old = dp[new_mask][nxt]
if old is None or candidate < old:
dp[new_mask][nxt] = candidate
parent[new_mask][nxt] = last
full = limit - 1
best = None
endpoint = None
for last in range(1, n):
cost = dp[full][last]
closing = weights[last][0]
if cost is None or closing is None:
continue
candidate = cost + closing
if best is None or candidate < best:
best = candidate
endpoint = last
if endpoint is None:
return None
path = []
mask = full
last = endpoint
while mask != 1:
path.append(last)
previous = parent[mask][last]
mask ^= 1 << last
last = previous
path.append(0)
path.reverse()
path.append(0)
return best, path
代码假定元素满足整数或 None 的约定,并检查矩阵形状。它用 is None 判断边是否缺失,因此零和负代价都有效。每个掩码都分配独立的表行。每条记录的父指针都来自较小掩码的一次可达转移;因此还原时每一步都会移除一个已访问的非零顶点,最终到达初始状态。初始状态不需要父指针。
例题 14.1.6
(父指针链也记录每个前驱所用的集合)
对四顶点的最优解,将掩码写成第 0 位在右侧的形式,父指针链为
还原时先逆向收集 ,反转得到 ,再附上返回顶点 0,得到 。每次移除一位都表明恰有一个顶点从已访问集合中移除。核对代价时,应使用原图中的有向边,包括最后返回的边。
例题 14.1.7
(最小的回路:两个顶点与一个顶点)
取 ,、。代码设 dp[1][0]=0。从掩码 扩展到顶点 ,得 dp[3][1]=0+5=5、parent[3][1]=0。全集掩码 只有终点 ,返回代价为 ,所以 best 。还原时先加入 ,移到父指针 ,在掩码 停止;加入 、反转、再附上返回的 ,得到路径 。若边 不存在,返回代价是 None,没有终点符合条件,函数返回 None:全集路径存在,回路却不存在。当 ,函数不使用对角线元素,直接返回 。
常见错误
(用真值判断边是否缺失)
写成 if not edge: continue,会把代价 当作缺失的边。对两个顶点,、,边 会被跳过,找不到回路,函数返回 None,但代价为 的回路 其实存在。缺失的边必须用 is None 判断,零和负代价才保持有效。
计算状态数量并认清问题边界
命题 14.1.8
(子集动态规划的成本)
对 个顶点,该实现执行 次算术运算,存储 个表格单元,并在 时间内还原路径。
证明
(先数状态,再数转移)
共有 个掩码,每个掩码有 个终点,所以每张表最多有 个位置,其中包括这个简单实现所分配的无效或不可达位置。每个可达状态最多考虑 个下一个顶点,每次只做常数次操作,得 。对终点取最小值的最后一步花 。还原每步移除一位,所以最多 步。
两张表都是指数大小,所以即使 只是适度增加,这种方法也可能变得不切实际。
这些界把掩码运算和整数代价运算当作单位操作。对任意大的 或代价,它们不是位复杂度界:掩码需要 位,精确的累积代价也需要足够多的位。Python 整数避免了定宽溢出,但大整数运算并非没有成本。
反例模式
用最短路径距离替换缺失边会改变问题
假设仅有 、、、 四条弧,每条代价均为 1。原图中不存在哈密顿回路:从 0 出发的回路必须先访问 1,再访问 2,但没有边 。
如果把每一对顶点之间的值替换成最短路径距离,就会得到完整的距离矩阵。该矩阵中的回路 代价为 ,但最后一段距离展开后是 。得到的原图闭合游走 重复访问了顶点 1。至少访问每个顶点一次的闭合游走,与给定图上的哈密顿回路,是不同的优化问题。
子集动态规划的价值不止于这个特定目标。可复用的推理方法是:找出决定所有后续选择的信息,证明较便宜的等价前缀可以替换较贵的前缀,并按严格增大的量安排转移顺序。仅有已访问集合、仅有终点,或仅写出未经解释的位掩码,都不构成正确性证明。
练习与完整解答
快速检查
(四个顶点中,若第 0 位写在右侧,把 编码成掩码。掩码能告诉我们路径先访问 还是先访问 吗?终点 对这个状态有效吗?)
把成员对应的二的幂相加。
解答 · 答案
掩码为 ,写作 1101。两种访问顺序得到相同的掩码,因此它不编码顺序。终点 1 无效,因为 。可达状态还需要实际存在一条使用可用边的路径;掩码和终点在形式上有效,并不保证状态可达。
快速检查
(在四顶点矩阵中,计算 与 ,再利用两个候选值计算 。)
把顶点 接在两条路径之后。
解答 · 答案
两个较小状态对应的路径分别是 ,代价为 ;以及 ,代价为 。添加顶点 3 得到候选值 和 ,最小值为 。再加上最后一条边 ,便得到代价为 的回路。
快速检查
(对两个顶点,唯一的非对角线代价为 和 。函数返回什么?如果返回边不存在,结果有何变化?对一个顶点,若对角线元素为 又如何?)
缺失的边是 None,不是零。
解答 · 答案
两条弧都存在时,答案的代价为 ,路径为 。不能把零代价边误认为不存在。移除 后,虽然存在全集路径,但不存在回路,因此函数返回 None。对单顶点,明确给出的零边约定返回 ,忽略对角线上的 。
快速检查
(在三顶点终点反例中,为什么 不是允许的零代价答案?哪个状态保留了真正最优解所需的前缀?)
看路线重复访问了哪个顶点。
解答 · 答案
该路线在返回 0 之前两次访问顶点 2,因此不是哈密顿回路。所需前缀是 ,由 表示。它可以合法地添加尚未访问的顶点 2,再返回 0,总代价为 1。另一个以 1 为终点的较便宜状态的已访问集合是 ,故不能再次添加 2,且它没有返回 0 的边。
快速检查
(根据父状态 、、、 还原回路。为什么父指针要按掩码与终点共同存储,而不能只按终点存储?)
从后向前读出终点,再反转。
解答 · 答案
逆向读取终点得到 ,反转并附加最后的 0,得到 。每一步移除当前终点对应的位。同一个终点在不同已访问集合中,最优前驱可能不同;每个终点只存一个父指针,可能把互不相关的状态拼接起来,造成顶点重复或遗漏。为每个状态对保存父指针,才能保留产生该代价的递推关系。
快速检查
(为什么 不是多项式界?即使某些贪心最短路径算法要求边权非负,为什么这里允许负权边?)
先数状态,再想每次转移对已访问集合做了什么。
解答 · 答案
最多有 个子集,每个子集最多有 个终点,每个状态最多有 种扩展,因此算术运算次数为 。指数因子仍然存在,所以这不是多项式时间保证。负权边不会破坏递推,因为每次转移都严格扩大已访问集合。依赖图无环,有限条简单路径中也能取到最小值。正确性来自精确的状态分解,而不是贪心地确定当前距离最小的状态。