第四部分：计算复杂性与近似解

本部分探讨计算的边界，定义什么是“难解”问题，并介绍在无法求得精确解时的应对策略。

4.1 NP 完全理论 (NP-Completeness Theory)

在现有的算法设计技术中，分治策略 (Divide-and-Conquer)、动态规划 (Dynamic Programming) 和贪心算法 (Greedy Algorithm) 已经成功解决了大量计算问题。然而，仍存在一类问题，至今未能找到高效的（多项式时间的）算法。典型的“难解”问题包括：

0-1 背包问题 (0-1 Knapsack Problem)
旅行商问题 (Traveling Salesperson Problem, TSP)
集合覆盖问题 (Set Cover Problem)
顶点覆盖问题 (Vertex Cover Problem)

4.1.1 问题

判定问题和最优化问题

判定问题是指输出仅有两种可能结果的问题，即答案属于集合 {Yes, No} 或 {1, 0}。
最优化问题的目标是在所有可行解 (Feasible Solution) 中，寻找一个具有最优值（最大值或最小值）的解。

在计算复杂性研究中，通常关注判定问题，因为其结构更简单且易于标准化。然而，最优化问题与判定问题之间存在紧密的对应关系。

任何一个最优化问题都可以通过引入一个阈值 (Threshold) 参数转化为对应的判定问题：

求图 $G$ 的最小生成树 $T$等价于给定图 $G$ 和正整数 $k$，判断是否存在边权和不超过 $k$ 的生成树
求价值最大的物品子集等价于给定物品集、背包容量 $W$ 和正整数 $V$，判断是否存在总价值至少为 $V$ 的物品子集？

算法理论表明，判定问题在计算上不会比对应的最优化问题更难。（最优化问题的算法通常可以用来求解判定问题）

编码方案与输入规模

为了衡量算法的时间复杂度，必须明确“输入规模”的定义。输入规模不仅取决于问题实例本身，还取决于所采用的编码方式。

编码方案 $e: I \to {0, 1}^$ 是一个将判定问题 $Q$ 的实例 $x \in I$ 映射为二进制串 $e(x)$ 的函数。
实例 $x$ 的*输入规模定义为二进制串的长度 $|x| = |e(x)|$。

例如合数问题输入为正整数 $n$，二进制编码长度$\lceil \log_2(n+1) \rceil$，输入规模为$O(\log n)$。

排序问题输入n个整数，编码长度为$n \times m$，其中 $m$ 是最大整数的二进制位数。

如果两个编码方案 $e_1$ 和 $e_2$ 可以通过多项式时间可计算的函数相互转换，则称它们是多项式相关的。即存在多项式 $p$，使得 $|e_2(x)| \le p(|e_1(x)|)$。
对于多项式相关的编码方案，一个问题是否属于多项式时间可解（P类）是独立于具体编码选择的。

注意：一进制编码（计算步骤数量直接对应于数字的数值大小（Value），而不是数字的位数）通常会导致输入规模指数级膨胀（例如整数 $W$ 编码为 $W$ 个 1），从而使伪多项式时间算法（如 $O(nW)$ 的背包算法）看似高效，实则非多项式时间。标准复杂度理论基于二进制编码。

P 类与 NP 类

$P$ 类是所有可以在多项式时间内被确定性算法求解的判定问题的集合。即$Q \in P$ 当且仅当存在算法 $A$ 和常数 $k$，使得对于任意实例 $x$，算法 $A$ 能在 $O(|x|^k)$ 时间内输出正确判定结果。

$NP$ 类并非指“非多项式时间”，而是指“非确定性多项式时间”。其核心特征在于解的可验证性

对于NP类问题，引入整数和验证算法：

证书 (Certificate)：对于“是”的实例 $x$，存在一个辅助信息串 $y$（证书），作为 $x$ 属于 $Y_I$ 的证据。
验证算法 $A(x, y)$：以实例 $x$ 和证书 $y$ 为输入。若 $A(x, y)=1$，则确认 $x$ 的答案为“是”。

例如，对于0/1背包问题，转化为判断问题后可以写作：给定物品集合、容量 $W$ 和一个目标价值 $K$，是否存在一个物品子集，使得其总重量不超过 $W$ 且总价值至少为 $K$？

证书 $y$ 就是能够证明上述问题的答案为 “Yes” 的证据，比如一个具体的物品选择方案
验证算法包括对总重量、总价值的计算

NP 的定义：
判定问题 $Q \in NP$，当且仅当存在一个多项式时间验证算法 $A$ 和常数 $c$，满足：

对于任意 $x \in Y_I$（答案为“是”），存在一个长度为 $O(|x|^c)$ 的证书 $y$，使得 $A(x, y) = 1$。
对于任意 $x \in N_I$（答案为“否”），不存在任何证书 $y$ 使得 $A(x, y) = 1$。

例如对于0/1背包问题，证书可以是一个下标集合 $S \subseteq {1, 2, \dots, n}$，表示被选中的物品编号，也可以是一个长度为 $n$ 的二进制向量 $y = (y_1, y_2, \dots, y_n)$，其中 $y_i=1$ 表示选中第 $i$ 个物品，$y_i=0$ 表示不选。都是符合多项式长度的。

即，NP问题关注能否在多项式时间内验证证书是否有效。

定理：$P \subseteq NP$，是否 $P = NP$是计算机科学领域最大的开放问题之一。

示例

布尔可满足性问题 (SAT, Boolean Satisfiability)
第一个被证明为 NP-完全的问题
问题实例 (Instance)：

一组布尔变量 $X = {x_1, x_2, \dots, x_n}$
一个由变量 $X$、逻辑非 ($\neg$)、逻辑或 ($\lor$)、逻辑与 ($\land$) 以及括号构成的公式 $\phi$

是否存在一种真值赋值 (Truth Assignment) $\mu: X \rightarrow {0, 1}$（即对每个变量 $x_i$ 赋予真 $T$ 或假 $F$），使得公式 $\phi$ 的最终计算结果为真（TRUE）

3-CNF 可满足性问题(3-SAT)

问题实例 (Instance)：

变量集合：$U = {u_1, u_2, \dots, u_n}$
子句集合：一组子句 $C = {C_1, C_2, \dots, C_m}$
合取范式 (CNF)：整个公式是所有子句的逻辑与（AND），即 $\phi = C_1 \land C_2 \land \dots \land C_m$。
3-文字限制：每个子句 $Ci$ 恰好包含 3 个文字的逻辑或（OR），即 $C_i = (l{i1} \lor l{i2} \lor l{i3})$。文字 (Literal) $l$ 是变量 $u$ 或其否定 $\neg u$

是否存在一种真值赋值，使得 $\phi$ 中所有的子句 $C_i$ 同时为真？

给定证书（赋值 $\mu$），算法遍历所有 $m$ 个子句。
对于每个子句 $C_i = (l_1 \lor l_2 \lor l_3)$，检查其中是否至少有一个文字为真。
若所有 $m$ 个子句均满足条件，则验证通过。

这两个算法的证书长度都是O(n)。

4.1.2 多项式时间归约和NP完全类

归约

归约是比较两个问题计算难度相对大小的核心工具

设 $Q_1$ 和 $Q_2$ 是两个判定问题。若存在一个从 $Q_1$ 到 $Q_2$ 的多项式时间归约，记为 $Q_1 \le_P Q_2$。

归约由一个多项式时间可计算的函数 $f: {0, 1}^ \to {0, 1}^$ 构成，该函数将 $Q_1$ 的任意实例 $x$ 转换为 $Q_2$ 的实例 $f(x)$，并满足：

$x \in Y_{I1} \iff f(x) \in Y_{I2}$

$Q_1 \le_P Q_2$ 意味着 $Q_1$ 不会比 $Q_2$ 更难。解决 $Q_2$ 的能力涵盖了解决 $Q_1$ 的能力。
若 $Q_1 \le_P Q_2$ 且 $Q_2 \in P$，则 $Q_1 \in P$。
若 $Q_1 \le_P Q_2$ 且 $Q_2 \le_P Q_3$，则 $Q_1 \le_P Q_3$

NP完全类(NP-Complete, NPC)

NP 完全类包含了 NP 中“最难”的问题。一个判定问题 $Q$ 被称为 NP 完全的，当且仅当它满足两个条件：

属于 NP ($Q \in NP$)：问题本身是可验证的。
NP 难 (NP-Hard)：对于任意 $Q’ \in NP$，都有 $Q’ \le_P Q$。（即 NP 中的每个问题都能归约到它）。

其中，NP 难 (NP-Hard)包括仅满足条件 (2) 但不一定满足条件 (1) 的问题。这类问题至少和 NPC 问题一样难，甚至可能不在 NP 中（即不可验证）。

计算等价性：对于任意两个 NPC 问题 $Q_1, Q_2$，必有 $Q_1 \le_P Q_2$ 且 $Q_2 \le_P Q_1$。这说明所有 NPC 问题在多项式时间可归约的意义下是等价的。
若存在任何一个 NPC 问题是多项式时间可解的（即属于 P），则所有 NP 问题均为多项式时间可解（即 $P=NP$）。
反之，若 $P \neq NP$，则没有任何 NPC 问题存在多项式时间算法。

NP完全性的证明方法

要证明一个新问题 $Q$ 是 NP 完全的，一般：

证明上界 ($Q \in NP$)：
展示存在一个多项式时间的验证算法，使得对于任意“是”的实例，存在一个多项式长度的证书。
证明下界 (NP-Hardness via Reduction)：找到一个已知的 NP 完全问题 $Q{known}$，并证明 $Q{known} \le_P Q$。
- 逻辑：由于所有 NP 问题都能归约到 $Q{known}$，而 $Q{known}$ 又能归约到 $Q$，根据传递性，所有 NP 问题都能归约到 $Q$。方
- 向注意：归约方向必须是已知 NPC $\to$ 新问题，而非反之。

4.1.3 经典归约链 (Classic Reductions)

整个规约链始于 Cook-Levin 定理，随后分支到不同的问题域

逻辑基础：布尔可满足性问题 (Boolean Satisfiability, SAT) $\xrightarrow{\text{Cook-Levin}}$ 3-CNF 可满足性问题 (3-CNF Satisfiability, 3-SAT)

图论分支：3-CNF 可满足性问题 (3-CNF Satisfiability, 3-SAT) $\xrightarrow{}$ 团问题 (Clique Problem, DCLIQUE) $\xrightarrow{}$ 顶点覆盖问题 (Vertex Cover, DVC) $\xrightarrow{}$ 集合覆盖问题 (Set Cover, SC)

同时：团问题 (Clique Problem, DCLIQUE) $\xrightarrow{}$ 独立集问题 (Independent Set, DIS)

数值与调度分支：3-CNF 可满足性问题 (3-CNF Satisfiability, 3-SAT) $\xrightarrow{}$ 子集和问题 (Subset Sum, SUBSET-SUM) $\xrightarrow{}$ 带有开放时间和截止时间的调度问题 (Scheduling with Release times and Deadlines, SRD)

路径与遍历分支：3-CNF 可满足性问题 (3-CNF Satisfiability, 3-SAT) $\xrightarrow{}$ 有向哈密顿回路问题 (Directed Hamiltonian Circuit, DHC) $\xrightarrow{}$ 哈密顿回路问题 (Hamiltonian Circuit, HC)

同时：有向哈密顿回路问题 (Directed Hamiltonian Circuit, DHC) $\xrightarrow{}$ 旅行商判定问题 (Traveling Salesperson Problem, DTSP)

4.2 近似算法 (Approximation Algorithms)

当问题被证明是 NP-Hard 时，我们退而求其次，寻找多项式时间内的“近似最优解”。

4.2.1 近似算法

近似算法 (Approximation Algorithm) 定义为一类能在多项式时间内运行，并产生近似解的算法。

优化问题的四元组模型

一个优化问题 $Q$ 可在数学上形式化为一个四元组：

$Q = (I_Q, SOL_Q, m_Q, goal_Q)$

$I_Q$ (Instances)：问题 $Q$ 的所有合法实例的集合。
$SOL_Q(x)$ (Feasible Solutions)：一个函数，对于给定实例 $x \in I_Q$，生成其所有可行解的集合。
$m_Q(x, y)$ (Measure Function)：评估函数。对于实例 $x$ 和可行解 $y \in SOL_Q(x)$，$m_Q(x, y)$ 给出了该解的价值（整数或实数）。
$goal_Q$ (Goal)：优化目标，取值为 $MAX$（最大化）或 $MIN$（最小化）。

例如最小顶点覆盖问题：

实例 ($I$)：无向图 $G = (V, E)$。
可行解 ($SOL$)：图 $G$ 的顶点子集 $U \subseteq V$，满足覆盖性质：对于 $E$ 中任意一条边 $(v_i, v_j)$，至少有一个端点属于 $U$（即 $v_i \in U$ 或 $v_j \in U$）。
估量 ($m$)：顶点子集的大小 $|U|$。
目标 ($goal$)：$MIN$，即寻找规模最小的顶点覆盖。

优化问题的复杂性

NPO 类

一个优化问题 $Q$ 属于 NPO 类，当且仅当满足以下四个条件

实例集 $I_Q$ 可在多项式时间内识别
可行解 $y$ 的大小受限于实例 $x$ 大小的多项式（即 $|y| \le q(|x|)$）
给定 $x$ 和 $y$，可在多项式时间内判定 $y$ 是否属于 $SOL_Q(x)$
评估函数 $m_Q$ 可在多项式时间内计算
若优化问题 $Q \in NPO$，则其对应的判定问题 $Q_D \in NP$

PO类
PO 类包含那些属于 NPO 且存在多项式时间算法能找到最优解及最优值的问题。
$PO \subseteq NPO$。

NP-难优化问题

如果一个 NPO 问题 $Q$ 对应的判定问题 $Q_D$ 是 NP-难 (NP-Hard) 的，则称 $Q$ 为 NP-难优化问题。

近似解的度量

设 $x$ 为问题实例，$y$ 为近似算法生成的解，$m(x, y)$ 为其值，$m^*(x)$ 为最优解的值。

相对误差

定义 $E(x, y)$ 为近似解与最优解的归一化偏差：

$E(x, y) = \frac{|m^*(x) - m(x, y)|}{\max\{m^*(x), m(x, y)\}}$

对于最小化问题：$E(x, y) = \frac{m(x, y) - m^(x)}{m(x, y)} = 1 - \frac{m^(x)}{m(x, y)}$。
对于最大化问题：$E(x, y) = \frac{m^(x) - m(x, y)}{m^(x)} = 1 - \frac{m(x, y)}{m^*(x)}$。

$\epsilon$-近似算法：对任意实例 $x$，满足 $E(x, A(x)) \le \epsilon$。

性能比
亦称近似比 (Approximation Ratio)，记为 $R(x, y)$，且总有 $R \ge 1$

$R(x, y) = \max \left( \frac{m(x, y)}{m^*(x)}, \frac{m^*(x)}{m(x, y)} \right)$

最小化问题：$R = m(x, y) / m^*(x)$。
最大化问题：$R = m^*(x) / m(x, y)$。
当 $R(x, y) = 1$ 时，$y$ 为最优解。

$r$-近似算法：对任意实例 $x$，满足 $R(x, A(x)) \le r$。

多项式时间近似方案：一个算法被称为 PTAS，如果对于任意固定的 $\epsilon > 0$，其运行时间是输入规模 $n$ 的多项式函数。
$Time(n, \epsilon) = O(n^{f(1/\epsilon)})$
完全多项式时间近似方案：一个算法被称为 FPTAS，如果其运行时间在 $n$ 和 $1/\epsilon$ 上同时是多项式的。这是近似算法中的“黄金标准”。
$Time(n, \epsilon) = O(\text{poly}(n) \cdot \text{poly}(1/\epsilon))$
这意味着即便要求较高的精度，运行时间也可以控制在多项式范围内。

4.2.2 基于贪心的近似算法

旅行商问题

实例：$n$ 个城市 $C={1, \dots, n}$，任意两点间距离 $d(i, j) \in \mathbb{Z}^+$。

目标：寻找一条遍历所有城市恰好一次并回到起点的回路（哈密顿回路），使得总距离最小化。

最近邻居算法：总是访问离当前位置最近的未访问城市

对于一般图 (General Graph)，无法保证常数级的性能比。通过调整最后一条边的长度，近似解的误差 $R$ 可以任意大。例如，最优解路径长为 8，而贪心解路径长为 $4+w$。当 $w \to \infty$ 时，$R \to \infty$。

不可近似性定理：如果 $P \neq NP$，则对于一般的旅行商问题，不存在任何多项式时间的 $r$-近似算法（其中 $r \ge 1$ 为常数）。

假设存在一个 $r$-近似算法 $A$。我们可以利用 $A$ 来解决 NP-完全的哈密顿回路问题 (Hamiltonian Cycle Problem)。

给定无向图 $G=(V, E)$，构造一个完全加权图 $G’$：
- 若 $(u, v) \in E$，则 $d(u, v) = 1$。
- 若 $(u, v) \notin E$，则 $d(u, v) = r \cdot n + 1$
若 $G$ 有哈密顿回路，则 $G’$ 中最优旅程长度 $m^*(G’) = n$（全由权重为 1 的边构成）
若 $G$ 无哈密顿回路，则 $G’$ 的任意旅程必包含至少一条“惩罚边”，长度至少为 $(n-1) \times 1 + (rn+1) = (r+1)n$

运行算法 $A$ 求解 $G’$。由于 $A$ 是 $r$-近似的，其输出解 $s_a$ 满足 $m(G’, s_a) \le r \cdot m^*(G’)$。

若 $G$ 有哈密顿回路：$m^*(G’)=n \implies m(G’, s_a) \le rn$
若 $G$ 无哈密顿回路：$m(G’, s_a) \ge (r+1)n > rn$
因此，通过判断 $m(G’, s_a)$ 是否小于等于 $rn$，即可在多项式时间内判定 $G$ 是否有哈密顿回路。这意味着 $P=NP$，与假设矛盾。

欧几里得旅行商问题

这类旅行商问题满足条件： $d[i, j] \le d[i, k] + d[k, j]$，对任意 $i, j$，满足 $d[i, j] = d[j, i]$。

对于满足三角不等式的 TSP 实例 $x$，最近邻居算法产生的近似解 $s_a$ 满足：

$R(x, s_a) = \frac{m(x, s_a)}{m^*(x)} \le \frac{1}{2}(\lceil \log_2 n \rceil + 1)$

其中 $n$ 为城市数量，$m^*(x)$ 为最优解的值。这表明近似比被限制在 $O(\log n)$ 级别，而非无界。

证明
设图 $G$ 有 $n$ 个节点。近似解 $s_a$ 的 $n$ 条边按权重递减排列为 $e_1, e_2, \dots, e_n$，权重分别为 $l_1 \ge l_2 \ge \dots \ge l_n$。
对于任意两个节点 $v_i, v_h$，若在算法执行过程中：

$v_i$ 在 $v_h$ 之前被加入：当算法处理到 $v_i$ 时，$v_h$ 是可选的未访问节点。贪心选择性质保证了选中的边 $e_i$ 长度 $l_i$ 不会超过到 $v_h$ 的距离，即 $d(v_i, v_h) \ge l_i$
$v_i$ 在 $v_h$ 之后被加入：同理，当处理到 $v_h$ 时，选中的边 $e_h$ 满足 $d(v_h, v_i) \ge l_h$。
任意两点间距离满足 $d(v_i, v_h) \ge \min(l_i, l_h)$

构造局部路径 $T_k$，令 $1 \le k \le n/2$。定义顶点子集 $C_k = {v_i \mid 1 \le i \le 2k}$（即前 $2k$ 个具有最长关联边的顶点）。
设 $T_k$ 是仅包含 $C_k$ 中顶点的路径序列，且该序列中顶点的相对顺序与最优解 $s^*$ 中的出现顺序一致。

在 $T_k$ 中相邻的两个顶点 $v_r, v_s$，在原最优解 $s^*$ 中可能相邻，也可能不相邻。
由三角不等式，直接连接 $v_r, v_s$ 的距离不超过 $s^$ 中从 $v_r$ 到 $v_s$ 的路径长度。
$T_k$ 的总长度 $|T_k| \le m^(x)$

$T_k$ 包含 $2k$ 个顶点和 $2k$ 条边。对于 $T_k$ 中的任意边 $(v_i, v_h)$，根据步骤 1 的推论，有 $d(v_i, v_h) \ge \min(l_i, l_h)$。求和可得：

$m^*(x) \ge |T_k| = \sum_{(v_i, v_h) \in T_k} d(v_i, v_h) \ge \sum_{(v_i, v_h) \in T_k} \min(l_i, l_h)$

由于 $Ck$ 包含了对应最长边 $e_1, \dots, e{2k}$ 的顶点，可以证明求和项至少包含 $l_{2k}$ 及其之前的项。推导可得：

$m^*(x) \ge 2 \sum_{i=k+1}^{2k} l_i$

对上述不等式关于 $k = 2^j$ 进行求和（$j = 0, 1, \dots, \lceil \log_2 n \rceil - 1$）：

$\lceil \log_2 n \rceil \cdot m^*(x) \ge 2 \sum_{i=2}^n l_i = 2 (m(x, s_a) - l_1)$

即：

$m(x, s_a) \le \frac{1}{2} m^*(x) \lceil \log_2 n \rceil + l_1 \le \frac{1}{2} m^*(x) (\lceil \log_2 n \rceil + 1)$

得到$R(x, s_a) \le \frac{1}{2} (\lceil \log_2 n \rceil + 1)$

绕树两周算法和Christofides 算法

这个算法的原理很好理解，即首先生成最小生成树，然后从起点开始绕树一周（从图上看是从内侧绕到外侧，或者相反，实际上构建一条欧拉回路）。然后，在沿着定点队列走一遍，删除重复的节点，形成近似解。

在一个无向图中，一个顶点 $v$ 的度（记为 $deg(v)$），就是连接该顶点的边的数量。欧拉回路的充要条件：一个连通图存在欧拉回路（即可以一笔画经过所有边并回到起点），当且仅当图中所有顶点的度数都是偶数。

定理：绕树两周算法是 Metric TSP 的 2-近似算法。

设最优 TSP 旅程为 $s^$，其长度为 $m^(x)$。删除 $s^$ 中的任意一条边得到一棵生成树 $T$。显然 $w(T^) \le w(T) < m^*(x)$。
加倍后的图 $G’$ 总边权为 $2 w(T^)$。因此，第 3 步生成的欧拉回路长度为 $2 w(T^) < 2 m^*(x)$。
由于距离满足三角不等式，删除重复的节点不会增加路径长度（相当于折线取直）。因此，近似解 $s_a$ 的长度 $m(x, s_a)$ 不超过欧拉回路的长度。

$m(x, s_a) \le 2 w(T^) < 2 m^(x)$，即近似比 $R \le 2$。

绕树两周算法为了构造欧拉图，简单粗暴地加倍了所有边，导致成本增加了一倍。Christofides 算法的核心洞见在于：仅需处理度数为奇数的顶点即可构造欧拉图，从而通过更精细的加边策略降低成本。

计算最小生成树 $T^*$。
找出 $T^*$ 中度数为奇数的顶点集合 $X$。由图论性质知 $|X|$ 必为偶数。
在导出子图 $G[X]$ 中，寻找最小权完美匹配 (Minimum Weight Perfect Matching) $M$ （最小权重的两两配对）。
将 $T^$ 的边与 $M$ 的边合并，形成多重图 $H = T^ \cup M$。$H$ 中所有顶点的度数（连接的边数）均为偶数（奇度点因匹配增加 1 度变为偶度）。
在 $H$ 中寻找欧拉回路，消除重复顶点，得到近似解 $t$。

这种算法是1.5-近似算法，区别在于：

$s’_X$ 是一个偶数个顶点的回路，它可以分解为两个不相交的完美匹配 $M_1$ 和 $M_2$，有$w(M_1) + w(M_2) = w(s’_X) \le m^*(x)$
由于 $M$ 是最小权匹配，故 $w(M) \le \min(w(M_1), w(M_2)) \le \frac{1}{2} m^*(x)$

这就是少的0.5的来源

最大背包问题

输入：$n$ 个物品 $U={u1, \dots, u_n}$，每个物品有重量 $w_i$ 和价值 $v_i$。背包总承重为 $W$
目标：寻找物品子集 $S \subseteq U$，使得 $\sum{u \in S} wu \le W$ 且总价值 $\sum{u \in S} v_u$ 最大。

基础策略是按价值密度 ($v_i/w_i$) 降序排列物品，并依次装入背包。、

显然，误差无上界。

增强贪心算法

运行基础贪心算法，得到解 $U’$（价值 $v(U’)$）。
运行基础贪心算法，得到解 $U’$（价值 $v(U’)$）。
输出 $\max{v(U’), v_{max}}$。

这是一种2近似算法。
贪心过程在遇到第一个无法装入的物品 $uj$ 时停止。
此时背包内物品为 $u_1, \dots, u{j-1}$，总价值 $V_{j-1} = v(U’)$。

根据线性松弛性质，最优解 $m^(x)$ 的上界为装入前 $j-1$ 个物品再加上物品 $j$ 的一部分（分数背包），故 $m^(x) < V_{j-1} + v_j$。
- 若 $vj \le V{j-1}$：则 $m^*(x) < 2 V_{j-1} \le 2 m(x, s_a)$。
- 若 $vj > V{j-1}$：由于 $uj$ 单个能放入背包（假设所有物品均不超重，否则若$u_j$不能单个能放入背包，显然当前解就是最优解），算法会比较 $u{max}$。显然 $v(u{max}) \ge v_j$。
  此时 $m^*(x) < V{j-1} + vj < 2 v_j \le 2 v(u{max}) \le 2 m(x, s_a)$。

Sahni算法

输入参数 $k$（控制精度的参数）

生成所有基数小于等于 $k$ 的物品子集 $S’$。
对于每个满足重量限制的子集 $S’$，在剩余容量内，对剩下的物品运行基础贪心算法进行填充，得到完整解 $S’’$。
输出所有 $S’’$ 中价值最大的解。

子集数量约为 $O(n^k)$，贪心填充耗时 $O(n)$，总时间 $O(k n^{k+1})$。因此是n的多项式时间算法。

这种算法的近似比： $R \le 1 + \frac{1}{k}$

因此这种算法是一种PTAS算法。

Algorithm SahniKnapsack
输入：n 个物品的集合 U（已按价值密度 v_i/w_i 非递增排序），背包容量 W，精度参数 k。
输出：最大总价值 P_max。
1. P_max ← 0
2. for 每一个满足 |S'| ≤ k 的子集 S' ⊆ U
3.    current_w ← sum(w_i for i in S')
4.    current_p ← sum(v_i for i in S')
5.    if current_w ≤ W then
6.       rem_w ← W - current_w
7.       for j ← 1 to n  (对剩余物品贪心填充)
8.          if j ∉ S' and w_j ≤ rem_w then
9.             current_p ← current_p + v_j
10.            rem_w ← rem_w - w_j
11.         end if
12.      end for
13.      if current_p > P_max then P_max ← current_p
14.   end if
15. end for
16. output P_max

最小顶点覆盖问题

实例：给定无向图 $G = (V, E)$。

可行解：图 $G$ 的顶点子集 $U \subseteq V$，满足覆盖性质：对于 $E$ 中的任意一条边 $(u, v)$，至少有一个端点属于 $U$（即 $u \in U$ 或 $v \in U$）。

估量：顶点集合的大小 $|U|$。

目标：寻找基数最小的顶点覆盖 $U^*$，即最小化 $|U|$。

贪心思路是：迭代地选择一条边，将其其中一个端点加入覆盖集，并删除该端点覆盖的所有边。

对于星型图（中心点连接所有叶子节点），若算法不幸总是选择叶子节点，最终解的大小将是 $|V|-1$，而最优解仅需选取 1 个中心点。此时近似比退化为 $|V|-1$。

VCOVERAPPROX

每选中一条未覆盖的边，就将其两个端点都加入覆盖集。

记算法选出的边的集合为 $A$。算法每选中一条边，就会删除与其端点相连的所有其他边。因此，集合 $A$ 中的任意两条边都不共享公共端点。

由于 $A$ 中各边互不相连（无公共顶点），要覆盖 $A$ 中的 $|A|$ 条边，最优解 $U^$ 至少需要从每条边中选取 1 个端点，即$|U^| \ge |A|$。

算法在每一步向 $U$ 中加入 2 个顶点（即 $A$ 中边的两个端点），$|U| = 2|A|$。

得：

$|U| = 2|A| \le 2|U^*|$

Algorithm VCOVERAPPROX
输入：无向图 G=(V, E)。
输出：G 的顶点覆盖 C，其中 C ⊆ V。
1. C ← ∅
2. E' ← E
3. while E' ≠ ∅
4.    从 E' 中任选一条边 (u, v)
5.    C ← C ∪ {u, v}
6.    从 E' 中删除所有与 u 关联的边
7.    从 E' 中删除所有与 v 关联的边
8. end while
9. output C

4.2.3 基于局部搜索的近似算法

最大割问题

实例：给定一个无向图 $G = (V, E)$。

可行解：将顶点集合 $V$ 划分为两个互不相交的集合 ${V_1, V_2}$（即 $V_1 \cup V_2 = V$ 且 $V_1 \cap V_2 = \emptyset$）。

度量标准：割的大小 (Cut Size)，即所有连接 $V_1$ 中一点与 $V_2$ 中一点的边的总数。

目标：寻找一个划分，使得割的大小最大化 (MAX)。

局部搜索算法

从一个初始解出发，通过定义“邻域结构”，不断在当前解的邻域中寻找更优解，直至无法改进（达到局部最优）

对于最大割问题，当前划分 $(V_1, V_2)$的邻域包含 $n$ 个候选解。每个邻居解是通过将单个顶点 $v_k$ 从当前集合移至另一集合而得到的。

若 $v_k \in V_1$，新划分为 $(V_1 - {v_k}, V_2 \cup {v_k})$
若 $v_k \in V_2$，新划分为 $(V_1 \cup {v_k}, V_2 - {v_k})$。

算法的流程是：

初始化 $(V_1, V_2)$
检查所有顶点 $v_k$。若移动 $v_k$ 能增加跨割边的数量，则执行移动并更新划分
重复步骤 2，直到没有任何顶点的移动能增加割的大小

Local-Cut 算法是最大割问题的 2-近似算法

设算法终止时的解为 $s_a = (V_1, V_2)$。由于处于局部最优，对于任意顶点 $v$，将其移至另一集合不会增加跨割边数。
定义 $N_1(v)$ 为 $v$ 在 $V_1$ 中的邻居数，$N_2(v)$ 为 $v$ 在 $V_2$ 中的邻居数。
- 若 $v \in V_1$，移动后跨割边变化量为 $N_1(v) - N_2(v)$。由局部最优知 $N_1(v) - N_2(v) \le 0 \implies N_1(v) \le N_2(v)$。
- 同理，若 $v \in V_2$，有 $N_2(v) \le N_1(v)$。
记 $n_1$ 为 $V_1$ 内部边数，$n_2$ 为 $V_2$ 内部边数，$m(G, s_a)$ 为跨割边数。总边数 $n = n_1 + n_2 + m(G, s_a)$。
- 对 $V1$ 中所有顶点求和：$\sum{v \in V_1} (N_1(v) - N_2(v)) = 2n_1 - m(G, s_a) \le 0$
- 对 $V2$ 中所有顶点求和：$\sum{v \in V_2} (N_2(v) - N_1(v)) = 2n_2 - m(G, s_a) \le 0$。
- 两式相加：$2(n_1 + n_2) - 2m(G, s_a) \le 0$
- 代入 $n_1 + n_2 = n - m(G, s_a)$，得 $2(n - m(G, s_a)) - 2m(G, s_a) \le 0 \implies n \le 2m(G, s_a)$。


Algorithm Local-Cut
输入：无向图 G=(V, E)。
输出：最大割的一个划分 (V1, V2)。
1. V1 ← ∅
2. V2 ← V
3. improve ← true
4. while improve
5.    improve ← false
6.    for 每一个顶点 u ∈ V
7.       w_same ← u 与同侧集合顶点的连边数
8.       w_diff ← u 与异侧集合顶点的连边数
9.       if w_same > w_diff then
10.         if u ∈ V1 then V1 ← V1 - {u}, V2 ← V2 ∪ {u}
11.         else V2 ← V2 - {u}, V1 ← V1 ∪ {u}
12.         improve ← true
13.      end if
14.   end for
15. end while
16. output (V1, V2)

4.2.4 基于线性优化的近似算法

最小加权顶点覆盖问题

实例：无向图 $G=(V, E)$，每个顶点 $v_i \in V$ 关联一个正权值 $c_i$。
可行解：顶点覆盖 $C \subseteq V$。
度量：覆盖集 $C$ 的总权值 $w(C) = \sum_{v_i \in C} c_i$。
目标：寻找总权值最小的顶点覆盖 $C^*$。

整数规划模型：

引入 0-1 变量 $x_i$： $x_i = \begin{cases} 1, & \text{若 } v_i \in C \\ 0, & \text{否则} \end{cases}$

目标函数：$ Min \sum_{v_i \in V} c_i x_i$
约束条件：

覆盖约束：$x_i + x_j \ge 1, \quad \forall (v_i, v_j) \in E$
整数约束：$x_i \in {0, 1}, \quad \forall v_i \in V$

这是一个NP完全问题。

线性规划松弛与四舍五入

将整数约束 $x_i \in {0, 1}$ 松弛为线性约束 $0 \le x_i \le 1$

LP 可在多项式时间内求解（如内点法）。
设 $w(x{LP}^)$ 为 LP 最优值，$w(C^)$ 为 IP 最优值。显然 $w(x{LP}^) \le w(C^)$。

求解 LP 得到最优解 $\mathbf{x}^ = (x_1^, \dots, x_n^)$。对于每个 $x_i^$:

若 $x_i^* \ge 1/2$，则令 $x_i = 1$（将 $v_i$ 加入覆盖 $C$）。
若 $x_i^* < 1/2$，则令 $x_i = 0$。

对于任意边 $(v_i, v_j)$，LP 约束保证 $x_i^ + x_j^ \ge 1$。这意味着 $x_i^$ 和 $x_j^$ 中至少有一个 $\ge 1/2$。
因此，舍入后至少有一个顶点被选中，即所有边均被覆盖，$C$ 是合法的顶点覆盖。
输出集合 $C = {v_i \mid x_i^* \ge 1/2}$

该算法是最小加权顶点覆盖问题的 2-近似算法。

$w(C) = \sum_{v_i \in C} c_i \le \sum_{v_i \in C} c_i (2 x_i^*) = 2 \sum_{v_i \in C} c_i x_i^*$

由于对于 $v_i \notin C$，$x_i^* \ge 0$，故：

$w(C) \le 2 \sum_{v_i \in V} c_i x_i^* = 2 w(x_{LP}^*)$

结合下界性质 $w(x_{LP}^) \le w(C^)$，得：

$w(C) \le 2 w(C^*)$

即近似比 $R \le 2$。

4.2.5 基于随机算法的近似算法

机近似算法在执行过程中引入了随机选择，对于给定实例 $x$，算法输出的可行解的值是一个随机变量 $m(x)$。

性能比通常使用期望性能比来衡量：

$R = \max \left\{ \frac{m^*(x)}{E[m(x)]}, \frac{E[m(x)]}{m^*(x)} \right\}$

最大可满足性问题

实例：定义在变量集 $X={x_1, \dots, x_n}$ 上的析取子句集合 $C={c_1, \dots, c_m}$。
解：真值赋值 $f: X \to {True, False}$。
度量：赋值 $f$ 下为真的子句数量。
目标：最大化满足的子句数。

朴素随机算法

对于每个变量 $x_i$，独立地以 $1/2$ 的概率赋值为 True，以 $1/2$ 的概率赋值为 False。

设实例 $x$ 包含 $c$ 个子句，且每个子句至少包含 $k$ 个文字。则 RS 算法输出解的期望值满足：

$E[m_{RS}(x)] \ge \left(1 - \frac{1}{2^k}\right) c$

由于最优解 $m^*(x) \le c$（最多满足所有子句），故：

$\frac{m^*(x)}{E[m(x)]} \le \frac{c}{(1 - 2^{-k})c} = \frac{2^k}{2^k - 1} \le 2$

最大加权可满足性问题与 GRWS 算法

每个子句 $c_j$ 关联一个权重 $w(c_j)$。目标是最大化被满足子句的总权重。

引入 0-1 变量 $y_i$（对应 $x_i$）和 $z_j$（对应 $c_j$ 是否满足），建立IP模型：

Maximize $\sum w(c_j) z_j$

Subject to: $\sum{i \in P_j} y_i + \sum{i \in N_j} (1-y_i) \ge z_j$，其中 $P_j, N_j$ 分别为子句 $c_j$ 中正文字和负文字的索引集合。

LP 松弛：将 $y_i, z_j \in {0, 1}$ 松弛为 $0 \le y_i, z_j \le 1$。求解得到最优分数解 $(y^, z^)$。

GRWS算法：对于每个变量 $x_i$，以概率 $p_i = y_i^*$ 赋值为 True。

对应的近似比为 $1 - (1-1/k)^k\rightarrow\frac{1}{1-1/e} = \frac{e}{e-1} \approx 1.582$。

注意在k = 2时，朴素的随机算法的近似比为4/3，小于GRWS算法的上界。事实上分别运行两种算法，输出两者中较优的那个解，可以将近似比上界降低至4/3。

$W_1 + W_2 \ge \sum_{c_j \in C} w(c_j) (\gamma_{k_j} + \alpha_{k_j}) z_j^*$

对于 RS 算法：子句 $c_j \in C_k$ 被满足的概率为 $\gamma_k = 1 - 2^{-k}$
对于 GRWS 算法：子句 $c_j \in C_k$ 被满足的概率至少为 $\alpha_k z_j^*$，其中 $\alpha_k = 1 - (1 - 1/k)^k$。

考察系数和 $\gamma_k + \alpha_k$ 的性质：

当 $k=1$ 时：$\gamma_1 = 1 - 1/2 = 0.5 $\alpha_1 = 1 - (0)^1 = 1$ \gamma_1 + \alpha_1 = 1.5$
当 $k=2$ 时：$\gamma_2 = 1 - 1/4 = 0.75 $\alpha_2 = 1 - (1/2)^2 = 0.75$ \gamma_2 + \alpha_2 = 1.5$
当 $k \ge 3$ 时：$\gamma_k + \alpha_k \ge 3/2$ 恒成立。

$W_1 + W_2 \ge \sum_{c_j \in C} w(c_j) \left(\frac{3}{2}\right) z_j^* = \frac{3}{2} m^*_{LP}(x)$ $\frac{W_1 + W_2}{2} \ge \frac{3}{4} m^*_{LP}(x) \ge \frac{3}{4} m^*(x)$

加权最小顶点覆盖问题

输入：一个无向图 $G=(V, E)$，以及每个顶点 $v$ 的权重 $w(v)$（自然数）。
输出：一个顶点集合 $U$，使得图中的每条边都至少有一个端点在 $U$ 中（即 $U$ 是一个顶点覆盖）。
目标：希望 $U$ 中所有顶点的总权重 $\sum_{v \in U} w(v)$ 尽可能小。

在构建顶点覆盖集时，并不是贪心地每次都选权重最小的点，而是按概率选择，其中权重越小的点被选中的概率越大。

Algorithm RandomWVC
输入：无向图 G=(V, E)，顶点权重函数 w : V → N。
输出：加权顶点覆盖 U。
1. U ← ∅
2. while E ≠ ∅
3.    从 E 中任选一条边 (u, v)
4.    p ← w(v) / (w(u) + w(v))
5.    以概率 p 选择 x ← u，否则选择 x ← v
6.    U ← U ∪ {x}
7.    从 E 中删除所有与 x 关联的边
8. end while
9. output U

这也是一个2-近似算法。

$E[\text{cost}] = w(v) \cdot \frac{w(t)}{w(v)+w(t)} + w(t) \cdot \frac{w(v)}{w(v)+w(t)}$ $E[\text{cost}] = \frac{2 w(v) w(t)}{w(v) + w(t)}$

因此对于每一条边，代价不会超过二倍最优解

蒙特卡洛算法和拉斯维加斯算法

蒙特卡罗算法肯定快，但不一定对。

它会在固定的时间（通常是多项式时间）内给出一个答案。

这个答案大概率是正确的，但也存在一定的概率是错误的。

通常可以通过重复运行算法多次来将错误率降低到任意小的程度（例如重复 $k$ 次，错误率降为 $1/2^k$）。

例如：在一个正方形里画个圆，随机撒豆子。通过数豆子在圆内的比例来估算 $\pi$。你撒的豆子越多，结果越准，但永远是近似值。

拉斯维加斯算法只要它输出了结果，这个结果一定是正确的。它的运行时间是一个随机变量。运气好瞬间算完，运气不好可能要算很久（甚至在理论上可能永远算不完，尽管概率极低）。

比如随机化快速排序 (Randomized QuickSort)：每次随机选一个 Pivot（基准值）。结果：排序结果一定是有序的（绝对正确）。时间：运气好是 $O(N \log N)$，运气极其糟糕（每次都选到最大或最小值）则是 $O(N^2)$。

Las Vegas = Monte Carlo + 验证器 (Verifier) + 无限循环 (While Loop)

4.2.6 基于动态规划的近似算法

背包问题的动态规划解法

状态定义：$M^*(k, V)$ 表示从前 $k$ 个物品中选取，使得总价值恰好为 $V$ 的最小重量

递推方程： $M^*(k, V) = \min \begin{cases} M^*(k-1, V) & \text{不选 } x_k \\ M^*(k-1, V-v_k) + w_k & \text{选 } x_k \text{ (需 } v_k \le V \text{)} \end{cases}$

初始条件：$M^(1, v_1) = w_1, M^(1, 0) = 0$，其余为 $\infty$（无定义）。

最优解：寻找最大的 $V^$，使得 $M^(n, V^*) \le W$

时间复杂度：$O(n \sum vi) = O(n \cdot n v{max}) = O(n^2 v_{max})$

如前所述，这是伪多项式时间 (Pseudo-Polynomial Time) 算法，因为运行时间依赖于数值 $v{max}$，而非数值的编码长度 $\log v{max}$。

数值缩放技术

为了消除运行时间对 $v_{max}$ 的依赖，我们通过降低价值的精度来缩减搜索空间。

物品集 $X$，背包容量 $W$，近似参数 $r > 1$

确定缩放因子：令 $v{max} = \max_i v_i$。定义缩放位数 $t = \lfloor \log_2 (\frac{r-1}{r} \frac{v{max}}{n}) \rfloor$
对每个物品 $x_i$，计算新价值 $v’_i = \lfloor v_i / 2^t \rfloor$（相当于右移 $t$ 位）。
在缩减后的实例 $(X’, W)$ 上运行上述动态规划算法，得到最优子集 $Y$

这相当于对价值进行了量化，原本整数空间的价值被量化到$\lfloor\frac{nr}{v{max}(r-1)} \rfloor$为粒度的空间。量化后空间的大小降低到$v{max}\times\frac{nr}{v_{max}(r-1)} = nr/(r-1)$

使用这一项代替原本时间复杂度中的$v_{max}$，这个算法的时间复杂度是$O(n^3 \frac{r}{r-1})$。

同样，因为粒度大小为$\lfloor\frac{r-1}{r} \frac{v_{max}}{n}\rfloor$，缩放导致的价值损失不会大于这个量：

$m*(x) < n\times\frac{v_{max}(r-1)}{nr} + m(x) = \frac{v_{max}(r-1)}{r} + m(x)$

选择对于任意$r>\frac{v_{max}}{m(x,r)}$，可保证 $m^*(x) \le r \cdot m(x, r)$。而r本身永远大于等于1，所以当所有物品都能独立放入背包时（如果不能，可以直接剔除这些物体），这一项恒成立。

如此，可见算法是关于n和误差倒数(1/(r-1))的多项式时间复杂度。这是一个FPTAS近似算法。

4.2.7 近似复杂度类

根据问题是否存在多项式时间近似算法，以及该算法对精度的逼近能力，我们将 NPO 问题划分为不同的层级。

假设 $P \neq NP$，则这些类之间存在严格的包含关系：

$FPTAS \subset PTAS \subset APX \subset NPO$

APX类

如果 NPO 问题 $Q$ 存在一个多项式时间算法，且其近似比为常数 $r \ge 1$，则称 $Q \in APX$。

如最小顶点覆盖问题 (2-近似)；欧几里得 TSP (1.5-近似)；最大割问题 (2-近似)。

若 $P \neq NP$，则 $APX \subset NPO$。这意味着存在属于 NPO 但不属于 APX 的问题（即不存在常数近似算法的问题），典型的例子是一般图 TSP

扩展类 (F-APX)：对于某些问题，近似比不是常数而是输入规模 $n$ 的函数：

log-APX：近似比为 $O(\log n)$，如集合覆盖问题。
poly-APX：近似比为 $O(n^k)$，如最大团问题

PTAS 类

NPO 问题 $Q$ 属于 PTAS，如果存在算法 $A(x, r)$，对于任意实例 $x$ 和任意精度要求 $r > 1$：

算法输出一个 $r$-近似解。
算法的运行时间关于实例规模 $|x|$ 是多项式的。

运行时间的示例是 $O(|x|^{f(1/(r-1))})$。虽然关于 $|x|$ 是多项式，但随着 $r \to 1$（精度要求提高），指数部分可能急剧增大。如上文提及的Sahni背包问题。

若 $P \neq NP$，则 $PTAS \subset APX$。这意味着存在属于 APX 但不属于 PTAS 的问题（即APX-完全问题），典型的例子是最小装箱问题 (Bin Packing) 和 Max-3SAT。

FPTAS 类

NPO 问题 $Q$ 属于 FPTAS，如果存在算法 $A(x, r)$，满足 PTAS 的条件，且运行时间关于实例规模 $|x|$ 和误差倒数 $1/(r-1)$ 均为多项式

运行时间形如 $O(|x|^a \cdot (1/(r-1))^b)$。这类算法不仅能逼近最优解，而且在提高精度时，计算成本的增加是可控的。

如基于动态规划的背包问题近似算法，时间复杂度为 $O(n^3 / (r-1))$

若 $P \neq NP$，则 $FPTAS \subset PTAS$。这意味着存在属于 PTAS 但不属于 FPTAS 的问题，典型的例子是平面图上的最大独立集问题。

FPTAS 是 NP-难优化问题所能达到的最佳近似结果（除非 $P=NP$）

4.2.8 近似保持的归约

近似保持的规约

在计算复杂性理论中，多项式时间归约用于判定问题的难度传递。对于优化问题，我们需要一种更强的归约形式，不仅能映射实例，还能保持解的近似精度。

设 $Q1$ 和 $Q_2$ 是两个 NPO 问题。若存在两个多项式时间可计算的函数 $f, g$ 和一个常数 $\alpha \ge 1$，满足以下条件，则称 $Q_1$ 可 AP-归约至 $Q_2$（记为 $Q_1 \le{AP} Q_2$）：

实例映射 ($f$)：对于 $Q_1$ 的任意实例 $x$ 和任意误差参数 $r > 1$，映射得到 $Q_2$ 的实例 $x’ = f(x, r)$。
解映射 ($g$)：对于 $Q_2$ 的实例 $x’$ 的任意可行解 $y’$，映射回 $Q_1$ 的可行解 $y = g(x, y’, r)$。
误差传递：若 $y’$ 是 $x’$ 的 $r$-近似解，则 $y$ 是 $x$ 的 $(1 + \alpha(r-1))$-近似解。 $R_{Q2}(x', y') \le r \implies R_{Q1}(x, y) \le 1 + \alpha(r-1)$

规约通常有两种用途：

正向传播（构造算法）：
若 $Q1 \le{AP} Q_2$ 且 $Q_2 \in APX$（或 $PTAS$），则 $Q_1 \in APX$（或 $PTAS$）。
这意味着如果我们能近似求解 $Q_2$，就能近似求解 $Q_1$。
反向证明（证明难度）：
若 $Q1 \le{AP} Q_2$ 且已知 $Q_1 \notin APX$（或 $Q_1 \notin PTAS$），则 $Q_2 \notin APX$（或 $Q_2 \notin PTAS$）。
这是证明一个问题难以近似的标准方法。