01先把问题说具体
从城市 0 出发访问每个城市恰好一次并回到 0,求最短巡回。只知道访问了几个城市为什么不够?
02一步步得到方法
集合内容决定下一步还能去哪里
mask 的第 v 位为 1 表示城市 v 已访问;dp[mask][u] 表示从 0 出发、恰好访问 mask、最后停在 u 的最小代价。相同 mask 但不同终点仍有不同未来成本,所以终点也是必要维度。
转移到未访问 v 时,newmask=mask|(1<<v),更新 dp[newmask][v]。初值仅 dp[1][0]=0,其余无穷;所有城市访问后再加回 0 的边。
位运算只是集合编码
1<<v 对应单元素集合,mask&(1<<v) 检查成员,| 表示加入。它没有神奇地消除指数规模:n 个元素有 2^n 个子集,适用范围通常是十几到二十左右,具体还取决于语言和内存。
从小 mask 向大 mask 扫描可行,因为加入未置位位后数值严格增加。也可按集合大小分层,直接体现先少后多的依赖。
集合相同也可能还需要位置
位掩码编码已选或已访问集合,但旅行路径接下来能去哪里还依赖当前终点,所以状态是 dp[mask][last]。不要因集合可以压成一个整数就省掉其他必要信息。
遍历未访问元素时,可通过位运算检查与添加。状态数约 n2^n,转移再枚举下一点可能达到 n²2^n;压缩的是状态表示,不是把指数规模变成多项式。
03把一个小例子完全算清楚
距离矩阵 [[0,2,9],[1,0,6],[15,7,0]],有向成本。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 初始 | dp[001][0]=0 | 只访问城市 0 |
| 访问一座新城 | dp[011][1]=2,dp[101][2]=9 | 两种首步 |
| 访问全部 | 经 1 再 2 成本 8;经 2 再 1 成本 16 | 终点不同 |
| 回到 0 | 8+15=23;16+1=17 | 取 17 |
窄屏可左右滑动表格,阅读完整计算与理由。
只有 visited 集合不足以确定路径成本,还必须知道当前位置。
04为什么这个方法成立
- 初态代表合法空行程。
- 每次只加未访问城市,保证恰好访问集合中的各点一次。
- 任一合法巡回删去最后一步都落入某个更小状态,因此转移覆盖全部候选,最终取最小正确。
05把推导翻译成代码
Python · 可独立运行的教学实现
def tsp(cost):
n = len(cost)
if n <= 1:
return 0
dp = [[float("inf")]*n for _ in range(1<<n)]
dp[1][0] = 0
for mask in range(1<<n):
for u in range(n):
if dp[mask][u] == float("inf"):
continue
for v in range(n):
if not mask & (1<<v):
nxt = mask | (1<<v)
dp[nxt][v] = min(dp[nxt][v],dp[mask][u]+cost[u][v])
return min(dp[-1][u]+cost[u][0] for u in range(1,n))逐个理解关键决定
dp[1][0] = 0- 二进制 001 表示起点已访问,不能从 mask=0 出发后重复访问起点。
mask | (1<<v)- 加入一个元素,其他访问记录保留。
06时间、空间与实现范围
O(n2^n) 个状态,每个枚举 n 个后继,时间 O(n²2^n),空间 O(n2^n)。
Python 的嵌套列表和对象开销很大,n=25 也可能远超可用内存;先估状态数再分配。
07改变条件,检查哪里会出错
状态只记录已访问数量
不同城市集合允许的后续完全不同,会错误合并子问题。
把位压缩理解为指数复杂度消失
整数位运算方便枚举,但可能集合数仍是2^n,适用规模需要估算。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
mask=101₂ 表示哪些城市?
需要一点提示
从最低位编号 0。
查看解析与答案
城市 0 与 2。
n=20 有多少子集?
需要一点提示
计算 2 的幂。
查看解析与答案
1,048,576 个,还需乘终点维度 20 才是状态槽位数量。
改成最少成本完成任务分配,位集合表示什么?
需要一点提示
哪些任务已经分配。
查看解析与答案
mask 可记录已分配任务,当前人员数由 popcount(mask) 推出,此时可能省掉独立位置维度。