近似算法详解

关键词速览

关键词	解释
近似比	算法解与最优解的比值上界
PTAS	多项式时间近似方案
FPTAS	完全多项式时间近似方案
顶点覆盖	NP完全的最小顶点集问题
旅行商问题	NP难的组合优化问题
集合覆盖	覆盖所有元素的最小子集族
贪婪算法	局部最优策略构建全局解
线性规划舍入	LP松弛后的取整策略
概率近似	期望近似比的算法
组合优化	离散空间中的优化问题

摘要

近似算法是解决 NP难 问题的一种核心范式。与精确算法追求最优解不同，近似算法在多项式时间内找到”足够接近”最优解的可行解。本文系统阐述近似算法的理论基础，包括近似比分析、经典近似技术，以及PTAS/FPTAS等高阶近似方案。通过顶点覆盖、旅行商问题、集合覆盖等经典案例，展示从2-近似到 $(1-ϵ)$-近似的完整技术谱系。

---

1. 近似算法的理论基础

1.1 近似比的形式定义

对于一个最小化问题 $\Pi$ 和近似算法 $\mathcal{A}$，定义近似比（approximation ratio）：

$$\rho (n)=\underset{I\in {\mathcal{I}}_n}{\max }\frac{ALG(I)}{OPT(I)}$$

其中 $ALG(I)$ 为算法输出值，$OPT(I)$ 为最优值。对于 $\alpha$-近似算法，满足 $\rho (n)\le \alpha$。

定义形式化：

一个算法 $\mathcal{A}$ 是 $\alpha$-近似算法，当且仅当对所有输入实例 $I$，都有

$$\frac{ALG(I)}{OPT(I)}\le \alpha \text{（最小化问题）}$$

或

$$\frac{OPT(I)}{ALG(I)}\le \alpha \text{（最大化问题）}$$

Note

注意：近似比越小，算法越接近最优。对于最小化问题，$\alpha >1$；对于最大化问题，$\alpha >1$ 表示解至少达到最优的 $1/\alpha$。

1.2 近似方案的层次

近似方案	时间复杂度	近似质量
$\beta$-近似	$O(n^k)$ 常数 $\beta$	常数近似比
PTAS	$O(n^{1/ϵ})$	$(1+ϵ)$-近似
FPTAS	$O(n^3/{ϵ}^2)$	$(1+ϵ)$-近似

PTAS的定义：

$$\forall ϵ>0,\exists \text{算法 }{A}_{ϵ}:\text{在 }O(n^{f(1/ϵ)})\text{ 时间内给出 }(1+ϵ)\text{-近似}$$

FPTAS的定义：

$$\forall ϵ>0,\exists \text{算法 }{A}_{ϵ}:\text{在 }O(n^c\cdot (1/ϵ{)}^2)\text{ 时间内给出 }(1+ϵ)\text{-近似}$$

---

2. 顶点覆盖问题与2-近似算法

2.1 问题定义

顶点覆盖（Vertex Cover）问题：给定无向图 $G=(V,E)$，找到最小顶点集 $C\subseteq V$，使得每条边至少有一个端点在 $C$ 中。

形式化：

$$\text{最小化 }|C|\text{s.t.}\forall (u,v)\in E:u\in C\vee v\in C$$

2.2 2-近似算法的设计与分析

贪婪边选择算法：

def vertex_cover_2_approx(G=(V, E)):
    C = ∅                                    # 覆盖集初始化
    E' = E.copy()                           # 边集副本
    
    while E' is not empty:
        # 选择任意边 (u, v)
        (u, v) = E'.pick_arbitrary_edge()
        
        # 将两端点加入覆盖集
        C.add(u)
        C.add(v)
        
        # 删除所有与u或v关联的边
        E'.remove_all_incident_to(u)
        E'.remove_all_incident_to(v)
    
    return C

2-近似证明：

设算法选取的边集合为 $A=\{e_1,e_2,...,e_k\}$，每条边 $e_i$ 被选中时，其两个端点加入 $C$。

上界：$|C|=2k$（每个顶点覆盖最多贡献2个端点）

下界：设最优解为 $OPT$，任意最优解 $C^{\ast }$ 必须覆盖边集 $A$ 中的所有边。由于 $A$ 中任意两条边不相邻（否则会被删除），覆盖 $A$ 至少需要 $k$ 个顶点：

$$|OPT|\ge k$$

因此：

$$\frac{|C|}{|OPT|}\le \frac{2k}{k}=2$$

证毕。

Example

考虑完全二分图 $K_{n,n}$，最小顶点覆盖为 $n$（选取一侧所有顶点）。贪婪算法每次选一条边，取两个端点，最终可能选取 $2n$ 个顶点。近似比为2。

---

3. 旅行商问题的近似

3.1 问题的计算复杂性

旅行商问题（TSP）存在两个变体：

• 一般TSP：寻找最小哈密顿回路，NP难
• 度量TSP：满足三角不等式的完全图，APX完全

3.2 度量TSP的2-近似

算法思想：最小生成树 + 欧拉回路 + 抄近路

def metric_tsp_2_approx(G, w):
    # G: 完全图, w: 度量权重函数（三角不等式）
    
    # 1. 计算最小生成树T
    T = mst_prim(G, w)
    
    # 2. 对T进行深度优先遍历，得到节点序列
    tour = dfs_preorder(T)
    
    # 3. 去除重复节点（抄近路）
    shortcut_tour = remove_duplicates(tour, w)
    
    return shortcut_tour

2-近似证明：

设 $MST$ 为最小生成树权重，$OPT$ 为最优TSP回路权重。

引理1：$MST\le OPT$

去掉最优回路任意一条边，得到一棵生成树，故 $MST\le OPT-\max (e)<OPT$

引理2：算法返回的路径 $\le 2\cdot MST$

深度优先遍历访问每条树边恰好两次（去+回），总权重 $2\cdot MST$。抄近路不增加权重（三角不等式）。

综合：

$$ALG\le 2\cdot MST\le 2\cdot OPT$$

3.3 Christofides算法：更好的1.5-近似

1976年Christofides提出改进算法：

1. 计算最小生成树 $T$
2. 在奇度数顶点集合 $O$ 上找最小完美匹配 $M$
3. 合并 $T+M$ 得到欧拉图
4. 寻找欧拉回路并抄近路

近似比：$3/2$（至今仍是度量TSP最好的常近似比）

---

4. 集合覆盖问题

4.1 问题定义

集合覆盖（Set Cover）问题：给定元素集合 $U$ 和若干子集族 $\mathcal{S}=\{S_1,S_2,...,S_m\}$，每子集有代价 $c_i$，找到最小代价的子集族覆盖所有元素。

形式化：

$$\text{最小化 }\sum _{i:S_i\in \mathcal{C}}{c}_i\text{s.t.}\bigcup _{S_i\in \mathcal{C}}{S}_i=U$$

4.2 对数 n-近似：贪婪算法

def set_cover_greedy(U, S, costs):
    C = ∅                    # 选中的集合
    uncovered = U.copy()     # 未覆盖元素
    
    while uncovered:
        # 选择性价比最高的集合：覆盖最多新元素/单位代价
        S_best = argmax_S( |S ∩ uncovered| / cost(S) )
        
        C.add(S_best)
        uncovered -= S_best
    
    return C

对数近似比证明：

设贪婪算法选择 $k$ 个集合：$S_1,S_2,...,S_k$。

关键不等式：每次迭代至少覆盖 $1/k$ 的剩余元素。

设 $n_i$ 为第 $i$ 步的剩余未覆盖元素数，则：

$$n_{i+1}\le n_i\left(1-\frac{1}{k}\right)$$

经过 $k$ 步后：$n_k\le n_0(1-1/k{)}^k<1$

因此 $k\le H_n=\ln n+O(1)$。

最优解满足 $OPT\ge \text{max cost}$，故：

$$\frac{ALG}{OPT}\le \frac{k\cdot \text{max cost}}{OPT}\le H_n$$

Warning

集合覆盖不能有常数近似比（除非 $P=NP$），因为问题本身是APX难。

---

5. PTAS与FPTAS的构造技术

5.1 PTAS：基于输入的局部调整

以调度问题为例：$n$ 个作业、$m$ 台机器、最小化最大完工时间（makespan）。

LPT（Longest Processing Time First） 算法：

1. 按处理时间降序排列作业
2. 依次分配到当前负载最小的机器

近似比：$4/3-1/(3m)$

5.2 FPTAS：伪多项式时间 + 核化

以背包问题为例，经典的FPTAS构造：

def knapsack_fptas(items, W, ε):
    # 伪多项式时间算法 + 缩放技术
    
    # 1. 计算价值上界 V = max_i(v_i)
    V = max(item.value for item in items)
    
    # 2. 缩放因子 K = ε * V / n
    K = ε * V / n
    
    # 3. 缩放价值
    for item in items:
        item.scaled_value = floor(item.value / K)
    
    # 4. 在缩放空间应用伪多项式DP
    dp = knapsack_dp_scaled(items, n * V / K)
    
    # 5. 反缩放
    return unscale(dp)

时间复杂度：$O(n^2\cdot V/\epsilon )$ → 通过缩放变为 $O(n^3/{\epsilon }^2)$

---

6. 随机近似算法

6.1 概率分析框架

随机近似算法通过期望近似比提供保证：

一个随机化算法 $\mathcal{A}$ 是 $\alpha$-近似，如果

$$\mathbb{E}[ALG(I)]\le \alpha \cdot OPT(I)$$

6.2 随机化顶点覆盖

def randomized_vertex_cover(G):
    # 每个顶点以1/2概率独立选择
    C = {v for v in V if random() < 0.5}
    
    # 修复：添加覆盖所有边的端点
    for (u, v) in E:
        if u not in C and v not in C:
            C.add(random.choice([u, v]))
    
    return C

期望近似比：$2$

---

7. 近似算法的局限性

7.1 APX完全性

存在一类问题，其常数近似比不存在——APX难问题：

• 集合覆盖（对数近似是紧的）
• 最大切割（GOA算法给出0.878-近似）
• 旅行商问题（一般形式APX难）

7.2 PCP定理与硬度

PCP定理（概率可检验证明）：

$$NP=PCP(\log n,O(1))$$

这意味着存在1-近似对NP也是难的（除非 $P=NP$）。

---

8. 近似算法在AI中的应用

8.1 神经网络剪枝

将网络剪枝建模为子模函数优化问题，使用贪婪算法实现 $(1-1/e)$-近似。

8.2 图神经网络的节点采样

GCN的层采样策略使用蒙特卡洛近似，在保持图卷积质量的同时降低计算复杂度。

8.3 强化学习的函数近似

值函数近似可以看作连续空间的集合覆盖问题，使用核方法实现函数近似。

---

参考来源

1. Vazirani, V. V. (2013). Approximation Algorithms. Springer.
2. Williamson, D. P., & Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press.
3. Christofides, N. (1976). Worst-case Analysis of a New Heuristic for the Travelling Salesman Problem. Technical Report.
4. Håstad, J. (1999). Some Optimal Inapproximability Results. JACM.
5. Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach.

---

相关文档

• 计算复杂性理论深度 - NP完全性与问题归约
• 组合优化深度指南 - 线性规划和整数规划
• 随机算法深度 - Las Vegas与Monte Carlo方法
• 在线算法详解 - 竞争分析与最优决策