Part 5.6：状态压缩 DP

引言：最短的送货路线

想象一下，你是一名快递员，需要从仓库出发，依次访问 n 个不同的客户，最后再回到仓库。你手上有一张地图，记录了任意两个地点之间的距离。你的目标是：找到一条访问所有客户恰好一次并返回仓库的最短路线。

这个问题，就是计算机科学领域最著名、最经典的 NP-Hard 问题之一——**旅行商问题 (Traveling Salesperson Problem, TSP)**。

对于 n 个客户，总共有 (n-1)! 种可能的路线。当 n 稍微大一点（比如 20），这个数字就会变成天文数字，暴力枚举所有路线是绝对不可行的。

那么，动态规划能解决吗？我们之前的 DP 问题，状态通常是 dp[i] 或 dp[i][j]，这里的 i 和 j 代表了位置或数量。但在 TSP 中，我们的状态不仅与当前在哪一个城市有关，还与已经访问了哪些城市有关。这个“已访问城市集合”的状态，用传统 DP 数组很难表示。

这时，状态压缩动态规划 (State Compression DP) 闪亮登场。它用一种极其巧妙的方式——二进制位——来“压缩”集合状态，从而让 DP 成为可能。

为什么状态压缩 DP 如此重要？

面试价值：状态压缩 DP 是 DP 中的进阶内容，是区分顶尖候选人的“分水岭”。它不仅考察 DP 思维，还考察对位运算的熟练掌握。能解决这类问题，意味着你具备了处理复杂组合优化问题的能力。
工程价值：虽然纯粹的 TSP 问题在实际工程中不常直接求解，但其“访问集合”的模型可以应用于任务分配（将 n 个任务分配给 n 个工人）、电路板布线、基因测序等多种场景。

本文将以 TSP 为例，带你一步步揭开状态压缩 DP 的神秘面纱。

背景知识：位运算与集合

状态压缩 DP 的基石是位运算。一个 n 位的二进制数，可以天然地表示一个大小为 n 的集合的子集。

假设我们有 4 个城市，编号为 0, 1, 2, 3。

二进制数 1011 (十进制 11) 可以表示一个集合 {0, 1, 3}。因为第 0, 1, 3 位是 1。
二进制数 0101 (十进制 5) 可以表示一个集合 {0, 2}。

我们可以用位运算来高效地操作这些集合：

判断元素 i 是否在集合 mask 中：(mask >> i) & 1
**将元素 i 加入集合 mask**：mask | (1 << i)
**从集合 mask 中移除元素 i**：mask & ~(1 << i)

掌握这些位运算技巧，是理解状态压缩 DP 的前提。

详细算法原理 (TSP)

1. 算法的“直觉”：记录路径的“足迹”

我们尝试用 DP 的思想来构建最短路径。假设我们从城市 0 出发。

dp[...][i] 表示…到达城市 i 的最短路径。

但这个状态定义是不完整的。因为我们还需要知道在到达城市 i 之前，我们已经访问了哪些城市。例如，0 -> 1 -> 2 和 0 -> 3 -> 2 是两条都到达了城市 2 的路径，但它们的前置“足迹”不同，后续的决策也会完全不同。

所以，我们的状态必须包含这个“足迹”信息。这个“足迹”就是一个已访问城市的集合。我们用一个二进制数 mask 来表示它。

2. 严谨原理：状态定义与状态转移方程

状态定义：dp[mask][i] 表示在访问了 mask 所代表的城市集合后，当前停在城市 i 的最短路径总长度。其中，mask 的第 i 位必须为 1。
状态转移方程：
我们如何计算 dp[mask][i]？这条路径必然是从另一个城市 j 走过来的。这个城市 j 必须满足：
1. j 也在 mask 集合中。
2. j 不是 i。
这条路径的前一个状态是：访问了 mask 中除了 i 之外的所有城市，并且停在了城市 j。这个状态可以表示为 dp[mask_without_i][j]，其中 mask_without_i 就是将 mask 的第 i 位设为 0 的结果。
因此，从 j 转移到 i 的总路径长度就是 dp[mask_without_i][j] + dist(j, i)。
我们需要遍历所有可能的上一个城市 j，并找到其中的最小值。
dp[mask][i] = min(dp[mask ^ (1 << i)][j] + dist[j][i])
其中 j 是 mask 中除了 i 之外的任意一个城市。
**初始化 (Base Case)**：
我们从城市 0 出发。所以，只访问了城市 0 并且停在城市 0 的路径长度为 0。
dp[1][0] = 0 (二进制 1 表示集合 {0})
dp 表的其他所有值初始化为一个极大值。
最终结果：
当我们访问了所有城市（mask = (1<<n) - 1）并停在某个城市 i 时，我们得到了 dp[(1<<n)-1][i]。最后，我们还需要从这个城市 i 返回起点城市 0。
所以，最终答案是 min(dp[(1<<n)-1][i] + dist[i][0]) for i from 1 to n-1。

步骤分解 (Step-by-step)

创建 DP 表：创建一个 (1<<n) x n 的二维数组 dp，初始化为极大值。
初始化：dp[1][0] = 0。
外层循环：遍历所有可能的集合状态 mask，从 1 到 (1<<n) - 1。
中层循环：遍历当前终点城市 i，从 0 到 n-1。
检查 i 是否在 mask 中：如果 (mask >> i) & 1 为真，则继续。
内层循环：遍历上一个城市 j，从 0 到 n-1。
**检查 j 是否在 mask 中且不等于 i**：如果 j != i 且 (mask >> j) & 1 为真，则进行状态转移。
状态转移：dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i])。
计算最终结果：遍历 i 从 1 到 n-1，计算 dp[(1<<n)-1][i] + dist[i][0] 的最小值。

Python 实现

import math

def traveling_salesperson(dist):
    """
    使用状态压缩 DP 解决 TSP 问题。
    :param dist: 邻接矩阵，dist[i][j] 是城市 i 到 j 的距离。
    :return: 最短路径长度。
    """
    n = len(dist)
    if n == 0:
        return 0

    # 1. DP 表初始化
    # dp[mask][i]: 访问状态为 mask，当前在城市 i 的最短距离
    dp = [[math.inf] * n for _ in range(1 << n)]

    # 2. Base Case
    # 从城市 0 出发，所以只访问了 {0} 且停在 0 的距离是 0
    dp[1][0] = 0

    # 3. 遍历所有状态
    for mask in range(1, 1 << n):
        # 4. 遍历当前终点城市 i
        for i in range(n):
            # 5. 确保 i 在 mask 集合中
            if (mask >> i) & 1:
                # 6. 遍历上一个城市 j
                for j in range(n):
                    # 7. 确保 j 在 mask 集合中且不等于 i
                    if j != i and (mask >> j) & 1:
                        # 8. 状态转移
                        prev_mask = mask ^ (1 << i)
                        dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + dist[j][i])

    # 9. 计算最终结果
    final_mask = (1 << n) - 1
    min_path = math.inf
    for i in range(1, n):
        # 从终点 i 返回起点 0
        path = dp[final_mask][i] + dist[i][0]
        min_path = min(min_path, path)

    return min_path if min_path != math.inf else 0

# --- 案例测试 ---
# 4个城市的距离矩阵
dist_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

shortest_path = traveling_salesperson(dist_matrix)
# 预期路径: 0 -> 1 -> 3 -> 2 -> 0 (10 + 25 + 30 + 15 = 80)
# 或 0 -> 2 -> 3 -> 1 -> 0 (15 + 30 + 25 + 10 = 80)
print(f"最短送货路线长度是: {shortest_path}") # 输出: 80

复杂度推导过程

时间复杂度: O(n² * 2ⁿ)。
- 状态总数是 2ⁿ * n。
- 对于每个状态 dp[mask][i]，我们需要遍历 n 个可能的上一个城市 j 来进行转移。
- 总的计算量是 2ⁿ * n * n。
空间复杂度: O(n * 2ⁿ)。
- 我们需要一个 (2ⁿ) x n 的 dp 表。

虽然这个复杂度是指数级的，但相比于 O(n!) 的暴力枚举，它已经是一个巨大的进步，可以在 n 约为 20 时求解问题。

优势 / 劣势 / 易错点

优势

解决组合优化：能够解决一类与子集、排列相关的组合优化问题。
思路巧妙：用位运算来表示状态，大大扩展了 DP 的应用范围。

劣势

指数级复杂度：只能处理 n 规模很小（通常 n <= 20）的问题。
不易理解：状态定义和位运算转移都比较抽象，需要扎实的位运算基础。

易错点

循环顺序：必须先循环 mask，再循环 i 和 j。因为计算 dp[mask] 依赖于 dp[prev_mask]，而 prev_mask 总比 mask 小，所以按 mask 从小到大遍历是正确的。
位运算错误：在状态转移时，prev_mask 的计算 mask ^ (1 << i) 很容易写错。
最终结果计算：忘记了从最后一个城市返回起点的距离。

适用场景

状态压缩 DP 适用于那些 DP 状态中包含一个“集合”维度，且集合大小 n 不超过 20 左右的问题。

**旅行商问题 (TSP)**：本文案例。
哈密顿路径问题：找到一条经过所有顶点恰好一次的路径。
任务分配问题：将 n 个任务分配给 n 个人，每个人完成不同任务有不同成本，求最小总成本。
棋盘覆盖问题：在棋盘上放置棋子，要求互相不能攻击，求最多能放多少个（如 N 皇后问题的变种）。

总结

状态压缩 DP 是动态规划中的“屠龙技”，它将 DP 的维度从简单的数字扩展到了“集合”，并通过位运算这一精巧的工具实现了状态的表示和转移。

本文核心要点

✅ 核心思想：使用一个整数（位掩码 bitmask）来表示一个集合的状态。
✅ 状态定义：dp[mask][i] 通常表示在状态 mask 下，以 i 结尾的最优解。
✅ 状态转移：利用位运算（&, |, ^, <<）来从子集状态转移到当前集合状态。
✅ 复杂度：时间 O(n² * 2ⁿ)，空间 O(n * 2ⁿ)。
✅ 适用范围：n 很小（<= 20）的组合优化问题。

掌握了状态压缩 DP，你对动态规划的理解将提升到一个新的高度。在下一篇文章中，我们将对整个动态规划系列进行总结，并探讨学习 DP 的通用方法论。

大学算法全体系 > Part 5：动态规划

#动态规划 #DP #状态压缩DP #位运算 #旅行商问题 #TSP

Part 5.6：状态压缩 DP

https://hjjjkh.github.io/posts/f4a573d

作者

李国强

发布于

2025年11月15日

许可协议

Part 3.2：快速排序：分治思想的经典应用上一篇

Part 3.1：基础排序算法：冒泡、选择与插入下一篇