状态压缩动态规划：旅行商问题的高效求解

核心逻辑与数学原理

状态压缩动态规划（State Compression DP，简称状压 DP）的核心本质是将一维具有强离散特征的组合集合，通过数制转换（通常为二进制）无损映射为一个低维的整数标量。这种降维映射能够让我们在 $O(1)$ 的时间内通过位运算进行状态的物理转移与冲突校验。

旅行商问题（TSP, Travelling Salesman Problem）是状压 DP 的教科书级模型：给定一个图及两两节点之间的距离，求一条经过所有顶点恰好一次且总权值最小的回路（本节讨论其变型：求从起点 0 触发，经过所有顶点恰好一次到达终点 $N-1$ 的最小权值路径）。

1. 状态空间的离散映射

在 TSP 问题中，我们不仅需要知道当前身处哪一个城市，更需要知道已经访问过了哪些城市，还剩下哪些城市没有访问。

• 指数级空间的坍塌：若用传统集合存储访问过的城市，状态判定极其低效。由于每个城市只有“访问过”与“未访问”两种互斥的边际状态，我们可以用一个长度为 $N$ 的二进制串来精确复现这个状态。
  例如：$N=5$ 时，二进制状态 $S = (10110)_2$：
• 从右往左数（第 0 位到第 4 位），第 1、2、4 位为 1，第 0、3 位为 0。
• 这代表城市 1、2、4 已经被访问过，城市 0、3 尚未访问。
  此时，这个集合状态被完美压缩为了一个十进制整数：$S = 2^1 + 2^2 + 2^4 = 2 + 4 + 16 = 22$。

2. 位运算控制矩阵与状态转移的算子化

借助计算机底层的位运算，集合的交、并、补、属于等操作可以高度抽象为以下算子：

状态设计与算法推导

1. 状态空间定义

设状态 $f[S][i]$ 表示：当前已经访问的城市集合为 $S$（其二进制掩码对应的十进制整数），且当前正站在城市 $i$ 上时，所花费的最小总距离。

• 合法性限制：状态 $f[S][i]$ 存在物理意义的先决条件是：城市 $i$ 必须已经包含在集合 $S$ 中，即满足 (S >> i) & 1 == 1。

2. 状态转移方程推导

我们通过逆向寻找当前状态的前驱来实施决策。在当前身处城市 $i$、集合为 $S$ 之前，上一步我们一定身处另一个不同的城市 $j$。
由于从 $j$ 跨步到了 $i$，那么在上一步时，城市 $i$ 一定处于未访问的状态。因此，前驱状态的城市集合必然是 $S - \{i\}$，在位运算中表达为 S ^ (1 << i)。

$$\forall j \in S \setminus \{i\}, \quad f[S][i] = \min \left( f[S][i], f[S \setminus \{i\}][j] + \text{weight}(j, i) \right)$$

代入位运算算子：

f[S][i] = min(f[S][i], f[S ^ (1 << i)][j] + weight[j][i]);

3. 拓扑序的控制控制

由于大集合的状态总是由小集合（少一个元素的集合）状态推导而来，在底层的双重循环中，外层循环必须严格从小到大枚举状态数 $S$（从 1 到 $(1<

NOIP 实战避坑指南

1. 位运算优先级混乱导致逻辑瘫痪

• 现象：写出类似 if (s >> i & 1 == 1) 这样的判定。在 C++ 运算符优先级中，算术运算符与关系运算符（如 ==）的优先级严格高于移位运算符（>>）和按位与（&）。上面这行代码在编译时会被等价解读为 if (s >> (i & (1 == 1)))，直接导致状态校验产生荒谬的越界或恒为假。
• 规避手段：在考场上编写任何位运算表达式时，无条件对位运算核心单元加独立外括弧。例如强制写为：if (((s >> i) & 1) == 1)。

2. 空间维度开辟错误引发内存爆表（MLE）

• 现象：误将状态压缩数组定义为 f[MAXN][1 << MAXN]。在进行状态访问时，由于把第一维和第二维写反，导致在处理 $N=20$ 的数据时，内存申请并没有问题，但在跑表 f[s][i] 时，由于 $s$ 达到了 $10^6$，直接引发段错误（数组越界内存非法读取）。或者错将维度开成 f[1<<25][25]，直接导致编译期 内存超限（Memory Limit Exceeded）。
• 规避手段：一般状压 DP 限制 $N \le 20$。定义空间时，务必将代表 $2^N$ 的大维度放在数组第一维，即 f[1 << 20][20]，以保证内存局部性与读写速度。

经典 NOIP/洛谷 真题

1. 洛谷 P1433 吃奶酪

• 题意描述：房间里放着 $N$ 块奶酪。一只小老鼠从坐标 $(0,0)$ 出发，要吃光所有的奶酪。每次可以任意两块奶酪之间直线移动。求吃完所有奶酪移动的最短总距离。$N \le 15$。
• 问题本质与解题思路：带有几何欧几里得距离特化的标准 TSP 问题。
  • 核心思路：由于 $N \le 15$，$2^{15} = 32768$，状压空间极小。首先预处理出两两奶酪点之间的两点距离 dist[i][j]。状态设计为 f[S][i] 表示已吃掉的奶酪集合为 $S$，当前停留在第 $i$ 块奶酪上的最短距离。完全套用 TSP 递推模版，最后全局扫描 $\min_{1 \le i \le N} \{ f[(1<

2. 洛谷 P1879 [USACO06NOV] Corn Fields G

• 题意描述：农夫有一块 $M \times N$ 的土地，某些格子由于贫瘠不能放牧。现在要选出一些格子放牧，要求任意两个放牧的格子不能有公共边（即不能相邻）。求一共有多少种合法的放牧方案。$M, N \le 12$。
• 问题本质与解题思路：基于行扫描的棋盘式状态压缩 DP。与点集状压不同，这里是对“一整行”的放牧形态进行二进制压缩。
  • 状态设计：设 f[i][S] 表示已经决策完前 $i$ 行，且第 $i$ 行的放牧状态对应的二进制掩码为 $S$ 时的总方案数。
  • 核心剪枝与冲突校验：
    1. 行内冲突：状态 $S$ 不能包含连续的 1，即满足 (S & (S << 1)) == 0。
    2. 地形冲突：状态 $S$ 不能在贫瘠的格子上放牧，通过与当前行的地形掩码进行按位与校验。
    3. 行间冲突：第 $i$ 行的状态 $S$ 与第 $i-1$ 行的状态 $S_{pre}$ 不能在同列相邻，即满足 (S & S_pre) == 0。 通过行与行之间的动态滚动交织，将指数级的棋盘组合数优化到线性递推。