数据结构与算法 / 系统课时
用子集状态求旅行商最短路
用子集状态求旅行商最短路
旅行商问题要求从起点出发访问所有城市一次后回到起点。直接枚举访问顺序有 种可能,本节把“已经访问哪些城市”和“当前停在哪个城市”压进 DP 状态,用 的时间完成精确求解。
学习目标
- 用位掩码表示已访问城市集合,并定义
dp[mask][u]。 - 从较小访问集合推导到较大集合的状态转移。
- 计算状态压缩旅行商 DP 的时间与空间复杂度,并判断适用规模。
把路径历史压缩成两个维度
设城市编号为 0..n-1,固定从城市 0 出发。位掩码 mask 的第 i 位为 1,表示城市 i 已经访问。状态定义为:
dp[mask][u]:从城市 0 出发,恰好访问 mask 中的城市,当前停在城市 u 时的最短路径长度。
这个定义只保留后续决策真正关心的信息。至于此前以什么顺序走到 u,只要访问集合和当前位置相同,未来可选城市就完全一致,因此可以只留下其中代价最小的方案。
初始状态只有起点被访问:dp[1 << 0][0] = 0。其余状态初始化为无穷大。合法状态还要求 u 必须属于 mask,否则“已经访问的集合”与“当前位置”互相矛盾。

从未访问城市扩展状态
如果当前处于 dp[mask][u],选择一个尚未访问的城市 v,就会得到新集合 next_mask = mask | (1 << v)。转移可以写成 dp[next_mask][v] = min(dp[next_mask][v], dp[mask][u] + dist[u][v])。
因为每次只新增一个城市,转移天然从较小集合流向较大集合。按 mask 从小到大遍历时,加入新位后的掩码一定更大,因此当前状态的有效前驱已经被处理。
当全部城市都访问后,还要从最后停留的城市 u 回到起点 0。答案因此是所有 dp[all_mask][u] + dist[u][0] 的最小值,而不是直接取 dp[all_mask][0]。
用完整程序计算最短回路
下面用四个城市验证状态定义与转移。距离矩阵是对称的,但算法本身并不依赖对称性,因此同样能处理有向代价。
from math import inf
def tsp(dist):
n = len(dist)
size = 1 << n
dp = [[inf] * n for _ in range(size)]
# 起点固定为城市 0,只访问起点时成本为 0。
dp[1][0] = 0
for mask in range(size):
if (mask & 1) == 0:
continue
for u in range(n):
if (mask & (1 << u)) == 0 or dp[mask][u] == inf:
continue
# 每次只把一个未访问城市加入集合。
for v in range(n):
if mask & (1 << v):
continue
next_mask = mask | (1 << v)
candidate = dp[mask][u] + dist[u][v]
if candidate < dp[next_mask][v]:
dp[next_mask][v] = candidate
all_mask = size - 1
return min(dp[all_mask][u] + dist[u][0] for u in range(n))
dist = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0],
]
print(tsp(dist))预期输出
80最短回路可以是 0 -> 1 -> 3 -> 2 -> 0,总代价为 10 + 25 + 30 + 15 = 80。如果题目还要求输出具体路线,需要额外记录每个最优状态的前驱城市,但这不会改变核心状态数量与渐进复杂度。
复杂度来自状态数乘转移数
访问集合共有 种,每个集合最多搭配 n 个当前位置,因此状态量级是 。每个状态又可能尝试最多 n 个下一城市,所以时间复杂度为 ,空间复杂度为 。
它相较 的全排列已经大幅降低,但仍然是指数算法。实际使用时应重点看 n:当城市数只有十几到二十左右时,状态压缩 DP 往往可行;继续增大后,内存和转移次数会迅速成为瓶颈。
旅行商状态压缩的关键不是位运算本身,而是识别出“访问集合 + 当前位置”已经足够描述未来。只要一个路径问题满足历史可以被集合状态压缩、后续代价只依赖当前状态,就可以尝试用同样方式把阶乘枚举降成子集 DP。