旅行商问题（TSP）

问题

最短哈密顿回路给定  个城市（编号 ）和任意两城市间的距离矩阵 dist[i][j]（可能不对称），从城市  出发，恰好经过每个城市一次，最后返回城市 ，求总路径的最小可能长度。

输入规模：状态DP解复杂度为 ， 尚可接受

状态压缩 DP 思想

状态压缩

用一个二进制整数来表示一个集合，该整数的第  位为 1 表示元素  在集合中，为 0 表示不在。例如 mask = 5 二进制为 101，表示集合 。

在 TSP 中，要记录已经访问过的城市集合，这是大小为  的集合的子集，有  种可能，用整数 mask 可表示。

DP 状态设计

设 dp[mask][i] 表示已经访问过的城市集合为 mask，且当前位于城市 i 时的最短路径长度。其中：

• mask 是一个二进制数，第 j 位为 1 表示城市 j 已经访问过。
• （当前所在城市必须是已访问过的城市之一）。

目标状态：访问了所有城市（mask = (1<<n)-1），且最后还要回到城市 0，整理为

状态转移

初始状态：从城市 0 出发，只访问了城市 0，路径长度为 0。dp[1<<0][0] = dp[1][0] = 0。

对于当前状态 (mask, u)，尝试前往一个尚未访问的城市 v, mask 的第 v 位为 0。新状态为 new_mask = mask | (1<<v)，新路径长度为 dp[mask][u] + dist[u][v]。转移方程：

按 mask 从小到大的顺序遍历所有子集，能保证计算 new_mask 时所需的 mask 已经求出。

实现

deftsp(n, dist):    INF = float('inf')# dp[mask][i]：已访问集合 mask，当前在城市 i 的最短长度    dp = [[INF] * n for _ in range(1 << n)]# 初始状态：从城市 0 出发，只访问了城市 0    dp[1][0] = 0# mask = 1 = 2^0# 枚举所有 mask（按数值递增自动对应城市数量递增）for mask in range(1 << n):for u in range(n):ifnot (mask & (1 << u)):   # u 不在 mask 中，跳过continue# 尝试前往未访问的城市 vfor v in range(n):if mask & (1 << v):     # v 已经访问过，跳过continue                new_mask = mask | (1 << v)                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])# 最后回到起点 0    full = (1 << n) - 1    ans = min(dp[full][u] + dist[u][0] for u in range(n))return ans

复杂度：

• 状态数：
• 每个状态枚举下一个城市 
• 总时间复杂度：
• 空间复杂度：，

例题

题目描述（经典 TSP）

某推销员需要拜访 4 个城市，距离矩阵如下：

求从城市 0 出发，经过所有城市后回到 0 的最短回路长度。

推导：因为只有 4 个城市，可以枚举所有可能的回路，最优回路为 0 → 1 → 3 → 2 → 0，总长度 = 10 + 25 + 30 + 15 = 80。

调用

if __name__ == "__main__":    n = int(input())    dist = [list(map(int, input().split())) for _ in range(n)]    print(tsp(n, dist))

1. 对称性优化：如果距离矩阵对称（dist[i][j] == dist[j][i]），可令 mask 只包含 0 在第一位，减少一半状态。
2. 剪枝：在转移中若 dp[mask][u] 已经是 INF，则跳过。
3. 路径恢复：通过记录前驱节点，在 DP 结束后回溯出具体路线。
4. 其他状态压缩问题：
• 铺砖问题（用多米诺骨牌覆盖棋盘）
• 集合划分问题（如最小权顶点覆盖）
• 子集 DP（如枚举子集的子集）