子集动态规划

形式陈述 ​

状态空间 ​

给定有限全集公理库有限集Finite set与某个自然数初始段等势、因而能够在有限步内无遗漏编号的集合。 $U$，子集动态规划以子集公理库子集Subset · Set inclusionA 的每个元素都属于 B 时成立的包含关系；它在集合之间形成偏序。 $S\subseteq U$ 为状态，必要时再加终点、容量或边界摘要。它沿用动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。的重叠子问题原则，适合子问题只依赖更小子集、而不同排列能汇入同一摘要的精确指数算法。

状态数 $2^n$ 不等于运行时间。若每个 $S$ 只枚举其中的元素，总量为 $O(n{2}^n)$；若每个 $S$ 枚举全部 $T\subseteq S$，转移数会增长到 $3^n$。

Hamilton 路状态与证明 ​

令 $dp[S,v]$ 表示存在一条恰好访问 $S$、终点为 $v$ 的简单路径。基例为 $dp[\{v\},v]=\mathrm{true}$。当 $|S|>1$ 时，

$$dp[S,v]=\underset{\begin{array}{c}u\in S\setminus \{v\}\\ uv\in E\end{array}}{\bigvee }dp[S\setminus \{v\},u].$$

必要性来自删除目标路径的最后一条边：前驱必为某个相邻 $u$，余下路径恰访问 $S\setminus \{v\}$。充分性则把 $v$ 接到已有路径末端；由于 $v\notin S\setminus \{v\}$，不会重复顶点。按 $|S|$ 归纳便得到“当且仅当”不变量。

三点路径 $1-2-3$ 中，单点状态为真；$dp[\{1,2\},2]$ 由 1 转移，$dp[\{1,2,3\},3]$ 再由 2 转移。$dp[\{1,3\},3]$ 为假，因为缺少边 13。若要输出路径，父指针还需记录让状态成立的 $u$。

有效 $(S,v)$ 状态共有 $n{2}^{n-1}$ 个，每个最多枚举 $n$ 个前驱，所以直接时间为 $O(n^2{2}^n)$，空间为 $O(n{2}^n)$。按邻接 bitset 过滤前驱能改善常数或字操作数，却不改变这一指数状态规模。

直觉

子集状态记录已经使用哪些对象，附加端点或边界状态则保留下一步转移真正需要的历史。每次删除最后一个选择会落到更小子集，表可按 popcount 分层；指数成本来自必须区分 $2^n$ 种使用模式，而不是集合操作的语法。

例子与边界

枚举量推导 ​

子掩码循环

$$T=S,T=(T-1)\mathrm{\&}S$$

会枚举全部 $T\subseteq S$。对一对 $(T,S)$，每个元素恰有“不属于 $S$”“属于 $S\setminus T$”“属于 $T$”三种状态，因此

$$\sum _{S\subseteq U}{2}^{|S|}=3^n.$$

位技巧让一次得到下个子掩码很便宜，却不能把总转移数写成 $O(n{2}^n)$。

推论与应用

表示与恢复 ​

当 $n\le w$ 时，bitmask 可放入一个机器字；更大的宇宙需要多字位集，集合差、成员测试和哈希都要计入字操作成本。按 $|S|$ 分层可为只依赖上一层的 DP 滚动空间，但 Hamilton 路重构仍需父信息或第二次计算。

$n=50$ 时 $2^n$ 已远超常规内存，位运算常数不会改变可行性。Meet-in-the-middle 依赖两半之间可组合的摘要，subset DP 依赖重叠子集状态；Held–Karp TSP 则把布尔可达改为以终点为索引的最小费用。它们都是精确指数算法，不能因使用 bitmask 就称为伪多项式或固定参数可解。

参考资料

• Held, Karp, “A Dynamic Programming Approach to Sequencing Problems,” 1962.
• Björklund et al., “Fourier Meets Möbius,” STOC 2007.
• Cygan et al., Parameterized Algorithms, 2015.