数据结构与算法 / 系统课时

用子集状态求旅行商最短路

用子集状态求旅行商最短路

旅行商问题要求从起点出发访问所有城市一次后回到起点。直接枚举访问顺序有 n!n! 种可能,本节把“已经访问哪些城市”和“当前停在哪个城市”压进 DP 状态,用 O(n22n)O(n^2 2^n) 的时间完成精确求解。

学习目标

  • 用位掩码表示已访问城市集合,并定义 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 从小集合扩展到大集合

从未访问城市扩展状态

如果当前处于 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]。

用完整程序计算最短回路

下面用四个城市验证状态定义与转移。距离矩阵是对称的,但算法本身并不依赖对称性,因此同样能处理有向代价。

python
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))

预期输出

text
80

最短回路可以是 0 -> 1 -> 3 -> 2 -> 0,总代价为 10 + 25 + 30 + 15 = 80。如果题目还要求输出具体路线,需要额外记录每个最优状态的前驱城市,但这不会改变核心状态数量与渐进复杂度。

复杂度来自状态数乘转移数

访问集合共有 2n2^n 种,每个集合最多搭配 n 个当前位置,因此状态量级是 n2nn2^n。每个状态又可能尝试最多 n 个下一城市,所以时间复杂度为 O(n22n)O(n^2 2^n),空间复杂度为 O(n2n)O(n2^n)。

它相较 O(n!)O(n!) 的全排列已经大幅降低,但仍然是指数算法。实际使用时应重点看 n:当城市数只有十几到二十左右时,状态压缩 DP 往往可行;继续增大后,内存和转移次数会迅速成为瓶颈。

旅行商状态压缩的关键不是位运算本身,而是识别出“访问集合 + 当前位置”已经足够描述未来。只要一个路径问题满足历史可以被集合状态压缩、后续代价只依赖当前状态,就可以尝试用同样方式把阶乘枚举降成子集 DP。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用子集状态求旅行商最短路

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通