NP 完全问题与近似算法

遇到一个优化问题，证明了它是 NP 完全的（→ P、NP 与归约）——然后呢？实际业务不会因为你证明了 NP 难就消失。本章讲证明难之后的四条路：近似算法、参数化算法、启发式、精确求解器。

先确认真的难

动手之前先确认：这个问题真的是 NP 完全，还是"看起来像"？

找已知 NP 完全问题的子结构：SAT、3-SAT、团（Clique）、顶点覆盖、独立集、哈密顿回路、TSP、背包、图着色；
正确方向的归约：把已知的 NP 完全问题多项式归约到你的新问题（方向搞反只证明你的问题不比已知问题难，什么都得不到）；
注意伪多项式：背包是 NP 完全但 $O(nC)$ 可解（ $C$ 是数值）——数值小的时候"难"的问题实际能解（→ 动态规划）。

四条路

1. 近似算法：可证明的质量保证

多项式时间，答案与最优的比值有证明：

顶点覆盖 2-近似：反复取未覆盖边的两个端点——答案 $\le 2 \times$ 最优；
TSP 的 Christofides 算法：满足三角不等式时 $1.5$ -近似；
集合覆盖 $\ln n$ -近似。

近似比是可证明的质量保证——"答案不比最优差 50%"是能写进合同的承诺。并非所有问题有好近似：一般 TSP 没有常数近似（除非 P=NP），图着色难以 $n^{1-\varepsilon}$ 近似——可近似性本身是问题的性质。

2. 参数化算法：抓住小参数

$FPT$ （固定参数可解）：复杂度 $f(k) \cdot n^{O(1)}$ ， $k$ 是某个天然小参数（如"顶点覆盖大小"）。顶点覆盖是 $O(2^k \cdot n)$ ——k 小时（k ≤ 100）完全可解，尽管它对一般的 $n$ 是 NP 完全。参数化的视角转换：不是问"输入多大"，而是问"哪个部分小"。

3. 启发式与局部搜索：实践最优

没有保证，但实践有效：

局部搜索：从可行解出发，反复取邻域改进（2-opt for TSP）；
模拟退火、禁忌搜索、遗传算法：跳出局部最优；
贪心 + 随机化。

无数生产系统的调度、排班、路由靠它们——"NP 难不等于不能解，等于没有已知的通用多项式算法"：真实实例往往有结构。

4. 精确求解器：现代的奇迹

现代 SAT/ILP 求解器能解很多"理论上难"的实例：

SAT 求解器（CDCL：冲突驱动子句学习）：工业级芯片验证、约束求解，数百万变量的实例日常可解；
ILP/MIP 求解器（Gurobi、CPLEX）：调度、排班、网络设计；
SMT 求解器（Z3）：带理论的 SAT，程序验证的基础。

理论的最坏界没有变，但求解器的剪枝与学习让真实实例远快于最坏界。实践结论：先建模型喂求解器，再考虑自己写算法——这是工业界的默认顺序。

决策顺序

是 NP 完全吗？（归约确认，方向别搞反）
数值参数小？（伪多项式 DP）
天然参数小？（FPT）
可近似好？（近似比）
都不行 → 建模喂 SAT/ILP 求解器；
求解器也不行 → 启发式 + 局部搜索，接受无保证。

本章要点

归约方向是关键：从已知 NP 完全问题归约到新问题
NP 难不等于不能解：伪多项式（背包 $O(nC)$ ）、参数化（顶点覆盖 $O(2^k n)$ ）、真实实例的结构都留了活路
近似比是可证明的质量保证；可近似性本身是问题性质
现代 SAT/ILP 求解器能解很多"理论上难"的实例：先建模喂求解器
启发式无保证但实践有效；决策按"确认难 → 参数 → 近似 → 求解器 → 启发式"顺序走