NP-hard 与近似算法：当最优解算不出来

Part 3”优”的前四站，我们建立了一套精确且高效的组合优化工具：最小生成树（贪心即最优）、网络流（增广路 + 对偶性）、匹配（增广路 + Hungarian）、着色与划分（贪心启发式 + METIS）。但一路走来，我们不断遇到一堵墙——

“这个问题是 NP-hard 的。”

哈密顿回路无法像欧拉回路那样多项式判定。最大团、最大独立集、最小顶点覆盖（一般图）都是 NP-hard。$k$-着色在 $k \geq 3$ 时就是 NP-complete。平衡图划分也是 NP-hard。

这些问题不会消失——它们是图上最核心的优化问题。物流公司要规划配送路线（TSP），芯片设计师要划分电路模块（图划分），生物学家要连接蛋白质网络的关键子集（Steiner tree）。面对 NP-hard，我们不是放弃，而是换一种方式求解。

本文是 Part 3 的最后一站。我们先汇总全路径中遇到的 NP-hard 问题，然后用 TSP 作为主线，展示近似算法如何巧妙地利用前几篇的工具（MST + 匹配 + 欧拉回路）获得有保证的近似解。接着推广到 LP 松弛、参数化复杂度（FPT）和启发式搜索——五种面对 NP-hard 的武器。

算法范式：约束松弛与近似（LP Relaxation, Christofides）、贪心（近似算法中）

NP-hard 图问题全景

在正式讨论解法之前，先回顾整条学习路径中遇到的 NP-hard 问题，统一到一张表里。

这张表有几个关键观察：

1. 有些问题完全不可近似：一般 TSP、最大团、最大独立集——除非 P = NP，否则不存在多项式时间的常数近似比算法。
2. 有些问题有漂亮的近似算法：度量 TSP 的 $3/2$ 近似（Christofides）、最小顶点覆盖的 $2$-近似（LP 取整）、Steiner tree 的 $\approx 1.39$ 近似。
3. 问题的”结构”决定可近似性：度量 TSP 比一般 TSP 好得多，因为三角不等式提供了额外约束；二部图上的顶点覆盖可以精确求解（König 定理，Art. 13），但一般图上只能 $2$-近似。

快速回顾：P、NP、NP-hard

在展开算法之前，精确定义这几个术语。

• P：存在多项式时间算法的决策问题。我们在前几篇中遇到的大多数问题都在 P 中：最短路径（Dijkstra, $O((V+E)\log V)$）、最大流（Dinic, $O(V^2 E)$）、最大匹配（Edmonds’ blossom, $O(V^2 E)$）、2-着色（BFS, $O(V+E)$）。

• NP（Nondeterministic Polynomial）：给定一个解（certificate），能在多项式时间内验证它是否正确的决策问题。例如，“这张图有大小 $\geq k$ 的团吗？“——如果有人给你一个 $k$ 节点的集合，你可以在 $O(k^2)$ 时间内检查它们是否全连接。所有 P 中的问题都在 NP 中（找到解自然能验证）。

• NP-hard：至少和 NP 中最难的问题一样难。如果任何一个 NP-hard 问题有多项式算法，那么所有 NP 问题都有多项式算法（即 P = NP）。NP-hard 问题不需要是决策问题——优化版本的 TSP（“最短回路是什么？“）也是 NP-hard。

• NP-complete = NP $\cap$ NP-hard：既在 NP 中，又是 NP-hard 的。3-SAT、3-着色、哈密顿回路的决策版本都是 NP-complete。

核心要点：NP-hard 意味着——除非 P = NP——不存在多项式时间的精确算法。但这不意味着我们无能为力。

TSP：旅行商问题

定义

TSP（Travelling Salesman Problem）：给定 $n$ 个城市和两两之间的距离 $d(i, j)$，找一条经过每个城市恰好一次的最短哈密顿回路。

这和 Art. 4 中的哈密顿回路密切相关：哈密顿回路问某条回路是否存在（决策问题），TSP 问最短的那条是什么（优化问题）。

TSP 有两个版本：

• 一般 TSP：距离 $d(i,j)$ 可以是任意非负值，甚至不满足三角不等式。
• 度量 TSP（metric TSP）：距离满足三角不等式 $d(i,j) \leq d(i,k) + d(k,j)$。这是大多数实际场景的情形——城市间的路程不会因为绕道而变短。

不可近似性：一般 TSP 不存在常数近似比的多项式算法（除非 P = NP）。直觉：如果距离可以任意设置，那么把”不在哈密顿回路上的边”的权重设为极大值，近似 TSP 就等价于判定哈密顿回路是否存在——而这本身就是 NP-complete。

度量 TSP 可以近似：三角不等式约束了”绕道代价”不会太高，这为近似算法提供了关键把手。

精确算法：Held-Karp DP

TSP 的精确解法是 Held-Karp 动态规划（1962）：

• 状态：$\text{dp}[S][j]$ = 从城市 0 出发，经过集合 $S$ 中的所有城市，最后停在城市 $j$ 的最短路径长度。
• 转移：$\text{dp}[S][j] = \min_{i \in S \setminus \{j\}} (\text{dp}[S \setminus \{j\}][i] + d(i, j))$
• 答案：$\min_{j \neq 0} (\text{dp}[\{0,1,\ldots,n-1\}][j] + d(j, 0))$
• 复杂度：$O(2^n \cdot n^2)$ 时间，$O(2^n \cdot n)$ 空间。

$O(2^n \cdot n^2)$ 比暴力枚举 $O(n!)$ 好很多——$n = 20$ 时，$n! \approx 2.4 \times 10^{18}$ 而 $2^{20} \cdot 20^2 \approx 4.2 \times 10^8$，差了 10 个数量级。但 $n = 30$ 时 $2^{30} \approx 10^9$ 已经勉强，$n = 50$ 完全不可行。

Christofides 算法：$3/2$ 近似

1976 年，Nicos Christofides 提出了度量 TSP 的经典 $3/2$ 近似算法，保持最佳近似比长达 45 年（直到 2021 年被微弱改进）。它的漂亮之处在于组合了三篇不同文章的工具：

1. MST（Art. 11）
2. 最小权完美匹配（Art. 13）
3. 欧拉回路（Art. 4）

算法步骤：

Step 1：求最小生成树 MST。设 MST 的总权重为 $w(\text{MST})$。

Step 2：找 MST 中所有奇度节点。欧拉回路需要每个节点度数为偶数。MST 中度数为奇数的节点集合记为 $O$。由”图的度数和 = $2m$（偶数）“知，$|O|$ 一定是偶数。

Step 3：在奇度节点集合 $O$ 上求最小权完美匹配 $M$。这是在完全图 $K_{|O|}$ 上求最小权完美匹配——Edmonds 的 blossom 算法可以在 $O(|O|^3)$ 时间内解决。

Step 4：合并 MST 和 M 得到多重图 $H$。$H$ 中每个节点的度数都是偶数——MST 中的偶度节点不受影响，奇度节点多了一条匹配边变成偶度。

Step 5：在 $H$ 上找欧拉回路。$H$ 是连通的（MST 保证）且每个节点度数为偶数，所以欧拉回路存在（Art. 4 的 Euler 定理）。用 Hierholzer 算法 $O(m)$ 找出。

Step 6：shortcut（捷径化）。欧拉回路可能重复经过某些城市。按回路顺序，跳过已经访问过的城市，直接前往下一个未访问城市。由三角不等式，捷径不会变长。

走查：5 城市示例

我们在 5 个城市 A-E 上走查 Christofides。城市坐标：A(70,50), B(170,30), C(190,120), D(110,150), E(40,100)。

Step 1：MST（用 Prim 算法）：

步骤	加入边	权重
1	A-B	$\sqrt{100^2 + 20^2} \approx 102.0$
2	B-C	$\sqrt{20^2 + 90^2} \approx 92.2$
3	A-E	$\sqrt{30^2 + 50^2} \approx 58.3$
4	E-D	$\sqrt{70^2 + 50^2} \approx 86.0$

MST 总权重 $\approx 338.5$。

Step 2：奇度节点。MST 的边：A-B, B-C, A-E, E-D。

• A: 度 2（A-B, A-E）— 偶
• B: 度 2（A-B, B-C）— 偶
• C: 度 1（B-C）— 奇
• D: 度 1（E-D）— 奇
• E: 度 2（A-E, E-D）— 偶

奇度节点集合 $O = \{C, D\}$。

Step 3：最小权完美匹配。$O$ 只有 2 个节点，匹配就是边 C-D，权重 $\sqrt{80^2 + 30^2} \approx 85.4$。

Step 4：多重图 = MST $\cup$ $\{C\text{-}D\}$。

Step 5：欧拉回路。例如 A → B → C → D → E → A。

Step 6：shortcut。这条回路没有重复节点，已经是哈密顿回路。总长度 $\approx 102.0 + 92.2 + 85.4 + 86.0 + 58.3 = 423.9$。

最优 TSP 回路（A → E → D → C → B → A）总长度 $\approx 58.3 + 86.0 + 85.4 + 92.2 + 102.0 = 423.9$。在这个例子中 Christofides 恰好找到了最优解。

近似比证明：为什么 $\leq 3/2$

定理：对于满足三角不等式的 TSP 实例，Christofides 算法给出的回路长度 $\leq \frac{3}{2} \cdot \text{OPT}$。

证明思路：

1. MST 是 OPT 的下界。最优 TSP 回路经过所有节点恰好一次，删去其中一条边得到一棵生成树。因此 $w(\text{MST}) \leq \text{OPT}$。

2. 奇度节点上的最小匹配 $\leq \text{OPT}/2$。考虑最优回路中的奇度节点 $O = \{v_1, v_2, \ldots, v_{2k}\}$（按回路顺序排列）。这 $2k$ 个节点将最优回路分成 $2k$ 段。把相邻段交替分组，得到两个匹配方案：$\{v_1 v_2, v_3 v_4, \ldots\}$ 和 $\{v_2 v_3, v_4 v_5, \ldots\}$。由三角不等式，每个匹配方案的总权重 $\leq$ 最优回路对应段的长度之和。两个方案合起来覆盖了整条最优回路，所以较小的那个 $\leq \text{OPT}/2$。最小权完美匹配至多和这个一样重，因此 $w(M) \leq \text{OPT}/2$。

3. 总计：$w(\text{MST}) + w(M) \leq \text{OPT} + \text{OPT}/2 = \frac{3}{2} \cdot \text{OPT}$。shortcut 由三角不等式不增加长度。$\blacksquare$

交互对比：最优 vs Christofides vs 贪心

下面的交互组件在同一组 7 个城市上展示三种方法的结果。切换按钮对比路线和总长度。

最优解Christofides贪心最近邻MST

最优 TSP 路线：遍历所有 7! / 2 = 2520 种排列找到的最短回路。

观察：Christofides 给出的路线通常非常接近最优（近似比远小于理论上界 $1.5$），而贪心最近邻虽然快速但质量不稳定。

Christofides 之后

Christofides 的 $3/2$ 近似比从 1976 年保持了 45 年未被改进。2021 年，Karlin, Klein, Oveis Gharan 在 STOC 上发表了一个 $(3/2 - \epsilon)$ 近似算法（$\epsilon \approx 10^{-36}$），首次突破了 $3/2$ 的壁垒。虽然改进极其微小，但理论意义重大——它说明 $3/2$ 不是度量 TSP 的最终答案。

近似算法的一般方法：LP 松弛

Christofides 是一种组合式近似算法。还有一种更系统化的近似方法——LP 松弛（Linear Programming Relaxation）。

松弛的直觉

注意术语区分：此处的”松弛”（relaxation）指的是约束放松——将整数约束放松为实数约束，和 Art. 6: 最短路径 中 Bellman-Ford / Dijkstra 的”边松弛”（edge relaxation，即尝试通过一条边缩短距离估计值）是完全不同的概念。

许多图上的优化问题可以写成整数线性规划（Integer Linear Program, ILP）：

• 每个节点/边有一个 0/1 决策变量 $x_i \in \{0, 1\}$（选或不选）
• 目标函数是线性的：最小化/最大化 $\sum c_i x_i$
• 约束是线性的：$\sum a_{ij} x_j \leq b_i$

ILP 是 NP-hard 的。但如果把 $x_i \in \{0, 1\}$ 的约束松弛为 $x_i \in [0, 1]$——允许变量取 0 到 1 之间的任意实数值——就得到一个线性规划（LP），可以在多项式时间内精确求解（单纯形法实践中很快，内点法理论上多项式）。

“松弛”的直觉是：原问题要求”选或不选”（离散的、困难的），松弛后允许”选一半”（连续的、容易的）。LP 的解是 ILP 的一个下界（最小化问题）或上界（最大化问题），因为松弛扩大了可行域。

然后我们需要取整（rounding）：把 LP 的实数解映射回整数解，并分析这个映射引入了多少误差——这就是近似比。

顶点覆盖的 $2$-近似：LP 取整经典例子

问题回顾：最小顶点覆盖（Art. 10）——找最少的节点集合 $C$，使得每条边至少有一个端点在 $C$ 中。

ILP 建模：

$\min \sum_{v \in V} x_v$

$\text{s.t. } x_u + x_v \geq 1, \quad \forall (u, v) \in E$

$x_v \in \{0, 1\}, \quad \forall v \in V$

其中 $x_v = 1$ 表示选中节点 $v$，$x_u + x_v \geq 1$ 保证每条边至少被一个端点覆盖。

LP 松弛：将 $x_v \in \{0, 1\}$ 改为 $x_v \in [0, 1]$。

取整规则：对 LP 最优解 $x^*$，令 $\hat{x}_v = 1$ 若 $x^*_v \geq 1/2$，否则 $\hat{x}_v = 0$。

走查：小图上的 LP 取整

考虑图 $G$：4 个节点 A, B, C, D，5 条边 A-B, A-C, B-C, B-D, C-D（三角形 A-B-C 加上 D 连接 B 和 C）。

Step 1：写 LP。

$\min\ x_A + x_B + x_C + x_D$

约束（每条边）：$x_A + x_B \geq 1$, $x_A + x_C \geq 1$, $x_B + x_C \geq 1$, $x_B + x_D \geq 1$, $x_C + x_D \geq 1$，以及 $0 \leq x_i \leq 1$。

Step 2：求解 LP。最优解：$x_A = x_B = x_C = x_D = 0.5$，目标值 $= 2.0$。（可验证：每条边的约束都是 $0.5 + 0.5 = 1 \geq 1$，满足。任何更小的值都会违反某个约束。）

Step 3：取整。所有 $x_i^* = 0.5 \geq 0.5$，全部取整为 $1$。覆盖集 $C = \{A, B, C, D\}$，大小 $= 4$。

对比最优整数解：$C^* = \{B, C\}$，大小 $= 2$。检验：A-B(B$\checkmark$), A-C(C$\checkmark$), B-C(B$\checkmark$), B-D(B$\checkmark$), C-D(C$\checkmark$)。

本例中近似比 $= 4/2 = 2$，恰好达到了理论上界。

$2$-近似比的证明

定理：上述 LP 取整算法给出的顶点覆盖大小 $\leq 2 \cdot \text{OPT}$。

证明：

1. 取整后的解是合法覆盖。对任意边 $(u, v)$，LP 约束保证 $x^*_u + x^*_v \geq 1$，因此至少有一个 $\geq 1/2$，取整后至少一个为 $1$。

2. 取整的代价 $\leq 2 \times$ LP 最优。对任意节点 $v$，如果 $\hat{x}_v = 1$（即 $x^*_v \geq 1/2$），则 $\hat{x}_v = 1 \leq 2 x^*_v$。因此：

$\sum_v \hat{x}_v \leq 2 \sum_v x^*_v = 2 \cdot \text{OPT}_\text{LP}$

3. LP 最优 $\leq$ 整数最优。LP 松弛扩大了可行域，所以 $\text{OPT}_\text{LP} \leq \text{OPT}_\text{ILP}$。

4. 合起来：$|\hat{C}| = \sum_v \hat{x}_v \leq 2 \cdot \text{OPT}_\text{LP} \leq 2 \cdot \text{OPT}_\text{ILP}$。$\blacksquare$

半整性（half-integrality）：一个深刻的事实是，顶点覆盖的 LP 松弛总是有半整数最优解——每个变量要么 $0$、$1/2$ 或 $1$。这意味着 LP 的信息已经相当”接近”整数解了。在二部图上更好：LP 最优解总是整数，这正是 König 定理——二部图的最小顶点覆盖 = 最大匹配，可以精确求解。

参数化复杂度（FPT）

LP 松弛和近似算法的思路是”降低期望”——接受不精确的解。参数化复杂度（Parameterized Complexity）提供了另一条路：利用问题中某个参数小的特点，在该参数上允许指数增长，但在输入大小 $n$ 上保持多项式。

FPT 的定义

一个参数化问题是 FPT（Fixed-Parameter Tractable）的，如果存在算法的时间复杂度为：

$O(f(k) \cdot n^c)$

其中 $k$ 是问题参数，$f$ 是只依赖 $k$ 的函数（可以是指数、超指数），$n$ 是输入大小，$c$ 是与 $k$ 无关的常数。

关键：指数爆炸被”关”在参数 $k$ 里。如果 $k$ 很小，算法就是实际可行的多项式时间。

顶点覆盖的 FPT 算法

问题：给定图 $G$ 和整数 $k$，是否存在大小 $\leq k$ 的顶点覆盖？

算法（分支搜索树，bounded search tree）：

1. 取任意一条边 $(u, v)$。
2. 分支：$u$ 或 $v$ 至少有一个在覆盖中。
   • 分支 1：将 $u$ 放入覆盖，删除 $u$ 及其所有关联边，$k \leftarrow k - 1$。
   • 分支 2：将 $v$ 放入覆盖，删除 $v$ 及其所有关联边，$k \leftarrow k - 1$。
3. 递归，直到 $k = 0$ 或没有边剩余。

走查：5 节点图 A-B, A-C, B-C, B-D，$k = 2$。

步骤	选择边	分支	覆盖集	剩余边	剩余 $k$
0	—	—	$\emptyset$	A-B, A-C, B-C, B-D	2
1	A-B	选 B	$\{B\}$	A-C	1
2	A-C	选 A	$\{B, A\}$	$\emptyset$	0
			找到！ $\{A, B\}$ 大小 = 2 $\leq k$

另一条路径：Step 1 选 A 而不是 B → $\{A\}$, 剩 B-C, B-D → Step 2 选 B → $\{A, B\}$, 剩 $\emptyset$ → 也找到。

复杂度：搜索树的每个节点分两支，深度最多 $k$，所以树有 $\leq 2^k$ 个叶子。每层做 $O(n)$ 工作（删除节点和边）。总计 $O(2^k \cdot n)$。

当 $k = 20$ 时，$2^{20} \approx 10^6$，乘以 $n$ 完全可行。但 $k = 50$ 时 $2^{50} \approx 10^{15}$，就不行了。FPT 的价值在于：许多实际问题的参数确实很小——网络安全中的关键节点数量有限，社交网络中的核心社区规模不大。

Treewidth：图”像树的程度”

树宽（treewidth）是参数化复杂度中最重要的图参数之一。直觉上，树宽衡量一个图”有多接近树”——树的 treewidth = 1，完全图 $K_n$ 的 treewidth = $n-1$。

树分解（tree decomposition）：将图 $G = (V, E)$ “分解”为一棵树 $T$，树的每个节点（称为”袋子”，bag）包含 $G$ 的一组节点，满足：

1. 每条边 $(u, v) \in E$ 至少被某个袋子同时包含；
2. 对 $G$ 的每个节点 $v$，包含 $v$ 的所有袋子在 $T$ 中形成连通子树。

树宽 = 最大袋子大小 $- 1$（减 1 是惯例，使树的 treewidth = 1）。

Courcelle 定理（1990）：如果一个图的 treewidth 为 $k$，则任何可以用 MSO$_2$（二阶单调逻辑） 表达的图性质，都可以在 $O(f(k) \cdot n)$ 时间内判定。

这意味着在 treewidth 小的图上，很多 NP-hard 问题变成 FPT：顶点覆盖、独立集、着色、哈密顿回路……都可以通过树分解上的动态规划高效求解。

哪些图的 treewidth 小？

• 树：$tw = 1$
• 外平面图：$tw \leq 2$
• 系列并联图：$tw \leq 2$
• $k \times n$ 网格图：$tw = k$
• 平面图：$tw = O(\sqrt{n})$

实际意义：许多实际网络（道路网络、电路布局）具有较小的 treewidth。Google 的路网分析就利用了道路网络近似平面、treewidth 有界的特性来加速最短路径查询。

启发式与元启发式

当问题规模太大，精确算法不可行，近似算法的保证不够好（或不存在），FPT 的参数也不小时，启发式（heuristic）是最后的武器。启发式没有理论上的近似比保证，但在实践中往往能找到很好的解。

局部搜索（Local Search）

基本思路：从一个初始解出发，反复做小的改动（邻域操作），如果改进则接受。对于 TSP，经典的邻域操作是 2-opt：

1. 选择回路中的两条非相邻边 $(a,b)$ 和 $(c,d)$
2. 删除它们，用 $(a,c)$ 和 $(b,d)$ 重新连接
3. 如果新回路更短，接受

2-opt 的时间复杂度为每步 $O(n^2)$（尝试所有边对）。实践中从 Christofides 或最近邻的结果出发做 2-opt，往往能把误差缩减到最优解的 $1\%$-$5\%$ 以内。

模拟退火（Simulated Annealing）

局部搜索的问题是容易陷入局部最优。模拟退火借鉴金属退火的物理过程，以一定概率接受更差的解：

• 温度 $T$ 高时，大概率接受坏解（探索）
• 温度 $T$ 低时，几乎只接受好解（利用）
• $T$ 逐步降低

接受概率：如果新解比旧解差 $\Delta E$，则以 $e^{-\Delta E / T}$ 的概率接受。

遗传算法（Genetic Algorithm）

维护一个解的”群体”（population），通过选择（保留好的）、交叉（组合两个解的特征）、变异（随机扰动）来进化。TSP 中，一个”个体”就是一个城市排列，交叉可以是子路径交换。

蚁群优化（Ant Colony Optimization）

模拟蚂蚁寻找食物的行为。多只”蚂蚁”在图上构建回路，路径上留下”信息素”。好的路径信息素浓度更高，后续蚂蚁更倾向于走这些路径。特别适合 TSP 和车辆路径问题（VRP）。

实践选择：对于 TSP，当前最好的实际方法是 LKH（Lin-Kernighan-Helsgott）——一种高级局部搜索，结合了 3-opt、5-opt 等复杂邻域操作。LKH 在数万城市规模上通常能找到最优解或与最优差距 $<0.1\%$ 的解。精确求解器方面，Concorde 是目前最强大的 TSP 精确求解器，使用分支定界 + 切割平面，已经求解了超过 85,000 个城市的实例。

复杂度与近似比对比表

问题	精确算法	近似比	近似方法	FPT
度量 TSP	$O(2^n \cdot n^2)$	$3/2 - \epsilon$	Christofides (+ 2021)	—
一般 TSP	$O(2^n \cdot n^2)$	不可常数近似	—	—
最小顶点覆盖	NP-hard	2	LP 取整	$O(2^k \cdot n)$
最大独立集	NP-hard	不可 $n^{1-\epsilon}$	—	$O(2^k \cdot n)$ via 覆盖
最大团	$O(3^{n/3})$	不可 $n^{1-\epsilon}$	—	$O(2^k \cdot n)$ via 覆盖的补
图着色 ($\chi \geq 3$)	$O(2^n \cdot n)$	$O(n^{0.199})$	SDP	treewidth $k$ → $O(k^k \cdot n)$
Steiner Tree	$O(3^k \cdot n + 2^k \cdot n^2)$	$\ln 4 + \epsilon \approx 1.39$	LP + 取整	$O(3^k \cdot n)$ (k = 终端数)
平衡划分	—	$O(\sqrt{\log n})$	SDP + 扩展	treewidth $k$ → FPT

应用场景

物流路径规划（TSP / VRP）

TSP 和它的推广——VRP（Vehicle Routing Problem，多辆车的路径规划）——是物流行业的核心问题。

• UPS: 其 ORION（On-Road Integrated Optimization and Navigation）系统每天为 55,000 名司机规划路线，使用 Christofides + 局部搜索（2-opt/3-opt），每年节省约 4 亿美元燃油费和 1 亿英里行驶距离。
• Google OR-Tools: 开源的组合优化工具包，内置 TSP 和 VRP 求解器，支持时间窗口、容量约束、多车队等现实约束。核心算法是引导式局部搜索（Guided Local Search）+ 大规模邻域搜索。
• 典型规模：数百到数千个配送点，求解时间限制在几秒到几分钟。

VLSI 布局

芯片设计中，需要将数百万个逻辑门划分到不同区域（图划分），并布线连接它们（Steiner tree）。

• METIS（Art. 14 中介绍的多级划分方法）是工业标准。
• Steiner tree 用于最小化芯片内的布线长度。由于问题规模巨大，通常使用 FPT 算法（终端数 $k$ 有限）+ 局部优化。
• Intel、TSMC 等的设计工具都内置了这些近似算法。

资源调度

• 课表排期（图着色，Art. 14）：大学排课本质上是着色问题。MIT 和 Cambridge 的排期系统使用 DSatur + 局部搜索。
• 云计算虚拟机分配：将虚拟机映射到物理服务器（二维装箱 + 图着色），Google 和 AWS 使用 LP 松弛 + 贪心的混合方法。
• 频率分配（着色变体）：5G 基站的频率规划，使用着色 + 列生成（column generation）的 LP 方法。

生物信息学

• 蛋白质交互网络中的 Steiner tree：给定一组”种子基因”（已知与某疾病相关），找最小的子网络连接它们。FPT 算法（参数 = 种子数，通常 $< 20$）在这里非常合适。
• 基因调控网络的关键节点识别：最小顶点覆盖 = 最小”控制集”。FPT 顶点覆盖算法在中等规模网络（数千节点）上实际可行。

总结

本文是 Part 3”优”的最后一站。我们系统地面对了 NP-hard 这堵墙，并展示了五种越过它的武器：

• 精确算法（指数时间）：Held-Karp DP $O(2^n \cdot n^2)$ 解 TSP，回溯搜索解小规模实例。适用于 $n < 25$-$30$。
• 近似算法（多项式时间，有保证）：Christofides 是皇冠上的明珠——组合 MST + 匹配 + 欧拉回路实现 $3/2$ 近似。LP 取整是系统化方法——顶点覆盖 $2$-近似的推导展示了”松弛 → 取整 → 分析损失”的标准范式。
• FPT（参数化多项式）：顶点覆盖 $O(2^k \cdot n)$ 在参数 $k$ 小时完全可行。Treewidth 是最强的结构参数——Courcelle 定理让几乎所有 NP-hard 问题在树宽有界的图上变为 FPT。
• 启发式/元启发式（无保证但实践好）：2-opt 局部搜索、模拟退火、遗传算法、蚁群优化。LKH 和 Concorde 是 TSP 求解的实际标准。
• 特殊结构利用：二部图上的覆盖问题可精确求解（König 定理）；平面图的着色不超过 4 色；treewidth 小的图适合 FPT。

Christofides 算法为什么漂亮？ 因为它不是凭空发明一个新技巧，而是把三篇不同文章的工具组合在一起——MST 提供骨架，匹配修补奇度节点，欧拉回路缝合成完整路线，三角不等式保证捷径不亏。这种”组合已有工具”的思维方式，正是算法设计中最优雅的形式。

Part 3”优”到此完结。从最小生成树到网络流，从匹配到着色，再到本文的近似与 FPT——我们建立了一套完整的组合优化工具箱。下一篇进入 Part 4”建模”——Art. 16: 随机图模型——从”在图上优化”转向”为什么现实世界的图长这个样子”。

实现指引

算法	库	函数/方法
TSP 近似 (Christofides)	NetworkX	nx.approximation.christofides(G, weight='weight')
TSP 贪心	NetworkX	nx.approximation.greedy_tsp(G, weight='weight')
TSP 精确 (小规模)	python-tsp	solve_tsp_dynamic_programming(distance_matrix)
TSP 精确 (大规模)	Concorde	concorde.TSPSolver.from_data(xs, ys) (pyconcorde)
最小顶点覆盖 (2-近似)	NetworkX	nx.approximation.min_weighted_vertex_cover(G)
Steiner Tree (近似)	NetworkX	nx.approximation.steiner_tree(G, terminal_nodes)
图着色 (贪心)	NetworkX	nx.coloring.greedy_color(G, strategy='DSATUR')
VRP / TSP	Google OR-Tools	ortools.constraint_solver.routing
TSP (LKH 启发式)	elkai / lkh	elkai.solve_float_matrix(dist_matrix)
图划分	METIS	metis.part_graph(G, nparts=k)
Treewidth (近似)	NetworkX	nx.algorithms.approximation.treewidth_min_degree(G)