动态规划进阶：状态压缩 DP（State Compression DP）与旅行商问题（TSP）位运算优化

动态规划进阶：状态压缩 DP（State Compression DP）与旅行商问题（TSP）位运算优化

在动态规划（Dynamic Programming）的高阶题型与运筹优化算法中，有一类极其特殊的 NP-Hard 组合优化问题：

• 旅行商问题（Traveling Salesperson Problem，TSP）：遍历 $N$ 个城市每个城市恰好一次并回到起点的最短总距离；
• LeetCode 847：访问所有节点的最短路径；
• 棋盘摆放问题（如经典的蒙德里安的梦想 / 互不攻击的国王与炮车）。

在这些问题中，数据规模通常极小（如 $N \\le 16 \\sim 20$），但每个元素拥有“被选中/未被选中”、“被访问/未被访问”等离散二元状态。如果用普通的数组来记录“当前哪些城市已经被访问过了”，状态维度将达到多维数组无法承受的复杂度。

状态压缩动态规划（State Compression DP，简称状压 DP） 凭借计算机底层的二进制位运算（Bitmasking）：将一个大小为 $N$ 的布尔状态集合，精确压缩进一个 32 位整型整数 int state 的各个二进制位中！通过极致的位移与位运算，将原本指数级暴搜的时间复杂度大幅优化，在毫秒级时间内征服原本不可解的组合难题。

今天我们把状压 DP 的二进制位运算心法、状态转移方程推导与 TSP 经典模板彻底讲透。

一、状态压缩核心位运算操作字典

设状态集合用整型变量 mask 表示（第 $i$ 位为 1 代表第 $i$ 个城市已被访问，为 0 代表未访问）：

graph TD
subgraph 二进制位运算核心操作 (0-indexed)
Op1["1. 检查第 i 个元素是否已被访问: (mask >> i) & 1 == 1"]
Op2["2. 将第 i 个元素标记为已访问: mask | (1 << i)"]
Op3["3. 将第 i 个元素从集合中移除: mask & ~(1 << i)"]
Op4["4. 将第 i 个元素的状态取反: mask ^ (1 << i)"]
Op5["5. 遍历全集状态空间: for mask = 0 to (1 << N) – 1"]
end

二、旅行商问题（TSP）状压 DP 状态定义与转移方程

给定 $N$ 个城市以及任意两个城市 $i$ 与 $j$ 之间的距离矩阵 dist[i][j]。求解从起点 0 出发，访问完所有城市恰好一次的最短路径总长度。

1. 状态定义：

$$\\mathbf{dp[\\text{mask}][u]}$$

• 物理含义：当前已经访问过的城市集合为 mask（二进制编码），且当前停留在城市 $u$ 时的【最小累计路径开销】！

2. 状态转移方程（自底向上向外递推）：

当前状态为 $(\\text{mask}, u)$，我们尝试从城市 $u$ 走向下一个尚未访问过的城市 $v$（即满足 (mask & (1 << v)) == 0）：

$$\\mathbf{dp[\\text{mask} \\mid (1 \\ll v)][v] = \\min \\left( dp[\\text{mask} \\mid (1 \\ll v)][v], \\ dp[\\text{mask}][u] + \\text{dist}[u][v] \\right)}$$

graph LR
S1["dp[mask][u]: 已经访问集合 mask, 停留在城市 u"] –>|走向未访问城市 v| S2["dp[mask | (1 << v)][v]: 访问集合扩充, 停留在城市 v"]
Note["转移开销: + dist[u][v]"]

3. 初始状态与最终答案：

• 初始化：所有 $dp$ 数组设为正无穷（INF）；
• 起点：$dp[1 \\ll 0][0] = dp[1][0] = 0$（集合中仅包含起点 0，停留在城市 0，耗时为 0）；
• 最终目标：$dp[(1 \\ll N) – 1][\\text{last_city}]$（所有二进制位全部为 1，代表全集覆盖）。

工业级 TSP 状压 DP Java 实现模板

import java.util.Arrays;

public class TspStateCompressionDp {

private static final int INF = 0x3f3f3f3f;

public int solveTsp(int n, int[][] dist) {
int totalStates = 1 << n; // 2^N 种状态集合
int[][] dp = new int[totalStates][n];

// 1. 初始化 dp 数组为无穷大
for (int i = 0; i < totalStates; i++) {
Arrays.fill(dp[i], INF);
}

// 2. 起点初始状态：从城市 0 出发
dp[1][0] = 0; // 1 的二进制为 00…001 (仅访问了城市 0)

// 3. 状态从小到大递推遍历 (保证子状态一定先于父状态计算完成!)
for (int mask = 1; mask < totalStates; mask++) {
for (int u = 0; u < n; u++) {
// 若当前集合 mask 中根本不包含城市 u，则该状态不可能存在，直接跳过
if ((mask & (1 << u)) == 0 || dp[mask][u] == INF) {
continue;
}

// 尝试从当前城市 u 走向下一个未访问城市 v
for (int v = 0; v < n; v++) {
// 若城市 v 尚未被访问
if ((mask & (1 << v)) == 0) {
int nextMask = mask | (1 << v);
dp[nextMask][v] = Math.min(dp[nextMask][v], dp[mask][u] + dist[u][v]);
}
}
}
}

// 4. 统计访问完全部城市（mask = (1 << n) – 1）并返回起点 0 的最短回路
int allVisitedMask = (1 << n) – 1;
int minTotalCost = INF;
for (int u = 0; u < n; u++) {
if (dp[allVisitedMask][u] != INF) {
// 加上从最后停留的城市 u 回到起点 0 的距离
minTotalCost = Math.min(minTotalCost, dp[allVisitedMask][u] + dist[u][0]);
}
}

return minTotalCost;
}
}

复杂度对比与时空分析

实习生的算法进阶总结

状压 DP 是位运算（Bitwise Manipulation）与动态规划（DP）最精妙的结合体：它利用二进制底层的位表示，将原本离散高维的集合状态优雅压缩进单个整型寄存器中，在保证状态无后效性的同时，将阶乘级的暴搜开销压缩为指数级多项式。牢记 “判断包含用 &、加入集合用 |、遍历状态从小到大保证拓扑有序” 三大心法，面对各类网格覆盖与旅行商难题，你都能写出闪电般迅捷的状压解法。