近似算法详解

想象一个场景：你是个快递公司老板，要规划配送路线，让司机跑遍100个城市再回到起点，这就是经典的旅行商问题。如果用穷举法，司机得等你算出最优路线才能出发，而计算时间可能比你等快递等到天荒地老还长。但实际上，让司机随便选条差不多短的路线就行——反正客户也不在乎你是不是绝对最优，只要不太离谱就行。

这就是近似算法的核心思想：与其在多项式时间内找不到精确最优解，不如退而求其次，找一个”足够好”的解。近似算法，就是在计算时间和解的质量之间做trade-off的艺术。

关键词速览

关键词	解释
近似比	算法解与最优解的比值上界
PTAS	多项式时间近似方案
FPTAS	完全多项式时间近似方案
顶点覆盖	NP完全的最小顶点集问题
旅行商问题	NP难的组合优化问题
集合覆盖	覆盖所有元素的最小子集族
贪婪算法	局部最优策略构建全局解
线性规划舍入	LP松弛后的取整策略
半定规划	介于线性和整数规划之间的松弛
局部搜索	从初始解出发迭代改进
局部比算法	基于局部竞争比的分析
概率近似	期望近似比的算法
组合优化	离散空间中的优化问题
拟多项式时间	$n^{O(\log n)}$ 时间的算法
APX完全	常数近似比也不存在的最难问题
L-reduction	保持近似质量的问题归约
P-归约	近似比保持的归约
黑箱优化	只通过函数值查询访问的优化
底层结构	问题内部的数学结构

---

摘要

近似算法是解决NP难问题的一类核心算法。跟精确算法死磕最优解不同，近似算法在多项式时间内找到”差不多”好的可行解。

这篇文章系统讲解近似算法的理论基础，包括近似比分析、经典近似技术，以及PTAS/FPTAS等高阶近似方案。通过顶点覆盖、旅行商问题、集合覆盖等经典案例，展示从2-近似到 $(1-ϵ)$-近似的完整技术谱系。

在工程实践中，精确求解NP难问题在大规模实例上往往不现实。近似算法在计算可行性和解质量之间找到了务实平衡。1974年Sahni和Gonzalez证明顶点覆盖有常数近似比，1995年Arora等人证明度量旅行商问题有多项式时间逼近方案，2008年Kleinberg证明在线社会网络中信息传播可以用常数近似比估计——近似算法的理论边界一直在拓展。

---

1. 近似算法入门：为什么我们需要近似解

1.1 从一个问题说起

先问你个问题：如果你要在一个有1000个顶点的图上找最小顶点覆盖，你知道最坏情况下需要计算多久吗？

答案是：即使是现在最好的精确算法，也可能需要指数级时间——可能算到太阳系毁灭还算不完。

但如果你愿意接受”最多比最优解差一倍”的解质量，有个简单的贪心算法，$O(n^2)$ 就能搞定，眨眼的功夫。

这就是近似算法的魅力：用一点点解质量的损失，换取计算时间的指数级提升。

1.2 精确解为什么不可得

NP难问题之所以难，根本原因在于”组合爆炸”。想象一下，50个物品的排列组合有 $50!\approx 3\times 10^{64}$ 种，比宇宙中的原子数还多。计算机再快，也不可能一一枚举。

更扎心的是，对于NP难问题，目前没人能证明它们不能在多项式时间内求解——但也没人能给出多项式时间算法。这就是著名的”P vs NP”问题，悬赏100万美元至今无人领取。

所以在实际工作中，我们必须接受一个事实：有些问题，最优解算不出来，但”足够好”的解是可以快速求得的。

1.3 近似算法的适用场景

不是所有问题都适合用近似算法。下面几类场景特别适合：

有时间压力的场景：比如实时调度、在线决策。你不可能让算法跑一个小时再给结果，近似算法分分钟就能给出一个可用的解。

解的质量有个可接受的底线：还是配送路线问题，客户只关心能不能在承诺时间内送到，不关心你是不是绕了20%的路。

问题规模很大：精确算法在小规模数据上还能跑，大规模就彻底歇菜。近似算法对规模不敏感。

只需要”足够好”而非”绝对最优”的解：这其实是大多数工程问题的真实需求。

---

2. 近似比与近似方案：算法的”质量”如何衡量

2.1 近似比的形式定义

你可能会问：什么叫”足够好”？这个”足够”怎么量化？

这就是近似比（approximation ratio）要回答的问题。

对于一个最小化问题（比如找最小顶点覆盖），近似比定义为：

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

听起来抽象，其实很简单：算法给出的解价值 / 最优解的价值，这个比值越小越好。

对于最小化问题：

• 近似比 = 2，意味着最坏情况下算法给出的解最多是最优解的2倍
• 近似比 = 1.5，意味着最多是最优解的1.5倍

对于最大化问题（比如最大化收益），情况反过来：

• 近似比 = 2，意味着算法给出的解最少是最优解的1/2

Note

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

2.2 近似质量的多层次理解

从不同角度审视近似质量：

绝对近似比：对所有实例 $I$，固定常数 $\alpha$ 满足 $ALG(I)/OPT(I)\le \alpha$。这类算法最理想但极为罕见。

渐进近似比：关注问题规模趋于无穷时的行为，即 ${\mathrm{limsup}}_{n\to \infty }\frac{ALG(n)}{OPT(n)}$。允许小规模实例有更差的表现。

分布近似比：假设输入服从某个概率分布，分析算法相对于最优的期望表现。这对应随机近似算法的分析框架。

差分近似比：定义 $|ALG-OPT|\le \alpha \cdot OPT+\beta$，其中 $\beta$ 是与实例无关的常数项。这比纯比值更宽松。

2.3 近似方案的层次结构

近似方案（Approximation Schemes）是一族参数化的算法，通过牺牲精度换取效率。

近似方案	时间复杂度	近似质量	设计难度
$\beta$-近似	$O(n^k)$ 常数 $\beta$	常数近似比	中等
PTAS	$O(n^{1/ϵ})$	$(1+ϵ)$-近似	困难
EPTAS	$O(n^c\cdot f(ϵ))$	$(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{-近似}$$

简单理解：PTAS要求精度越高花的时间越多，FPTAS更进一步，要求时间对精度是多项式依赖。背包问题就有FPTAS，想要求99%最优？运行时间大概是 $n^3/0.01^2=10^8{n}^3$。想要99.9%最优？时间变成 $10^6{n}^3$，贵了100倍但还是多项式。

---

3. 近似算法的分类：组合方法、平面分割、随机方法

3.1 组合方法

组合方法是近似算法中最”接地气”的一类，直接在问题图结构上操作，不涉及线性规划或半定规划。

代表算法：

• 贪心算法：每步选当前最优
• 局部搜索：从初始解出发，邻居里找更好的
• 原始-对偶：结合LP对偶理论，但不精确求解

优点：实现简单，运行速度快，适合大规模实例 缺点：理论近似比往往不够紧

3.2 线性规划与舍入方法

这是近似算法的”学院派”，套路是：

1. 把整数规划松弛成线性规划
2. 求解LP（多项式时间可解）
3. 把分数解”舍入”成整数解

关键问题：怎么舍？舍完质量损失多少？

3.3 半定规划方法

半定规划（SDP）是LP的升级版，允许变量是矩阵而非向量。SDP可以捕捉变量间的二次关系，松弛能力更强。

典型应用：最大切割问题的Goemans-Williamson算法，达到了惊人的0.878-近似。

3.4 随机方法

顾名思义，就是往算法里扔硬币——随机选择、随机舍入、随机初始化。

随机方法的巧妙之处在于：在期望意义上保证近似比，但每次运行结果可能不同。这听起来有点玄学，但数学上可以严格证明。

---

4. 顶点覆盖的近似算法：简单却有效

4.1 问题定义

顶点覆盖（Vertex Cover）问题：给定一个无向图，找最小的顶点集合C，使得每条边至少有一个端点在C里。

形式化来说：

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

这问题有多难？它是NP完全的——精确求解可能需要指数时间。

4.2 2-近似算法的设计

一个简单到离谱的贪心算法：

1. 任选一条边 (u, v)
2. 把 u 和 v 都加入覆盖集
3. 删除所有与 u 或 v 相连的边
4. 重复直到没有边

def vertex_cover_2_approx(G=(V, E)):
    C = ∅                                    # 覆盖集初始化
    E' = E.copy()                           # 边集副本
    
    while E' is not empty:
        # 选任意一条边
        (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

4.3 2-近似证明

这算法怎么就保证2倍了呢？

设算法选取的边集合为 $A=\{e_1,e_2,...,e_k\}$，每选一条边，算法往覆盖集里加2个顶点，所以 $|C|=2k$。

关键观察：$A$ 里的任意两条边都不相邻——因为一旦选了条边，它的两端点就把自己相邻的边全删了。

所以最优解要覆盖 $A$ 里的所有边，至少得选 $k$ 个顶点（因为两两不相邻，无法共享端点），即 $|OPT|\ge k$。

于是：

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

证毕。

Example

考虑完全二分图 $K_{n,n}$，最小顶点覆盖是 $n$（选一侧所有顶点）。这个贪心算法每选一条边就加2个顶点，可能选取 $2n$ 个顶点。近似比正好是2。

4.4 LP舍入方法

顶点覆盖还有个更优雅的2-近似，基于线性规划舍入：

def vertex_cover_lp_rounding(G, epsilon=0.5):
    # 构建顶点覆盖的LP松弛
    # min sum(x_v) s.t. x_u + x_v >= 1 for all (u,v) in E, 0 <= x_v <= 1
    
    # 求解LP得到分数解
    x = solve_vc_lp_special(G)
    
    # 确定性舍入：大于0.5的取整为1
    C = {v for v in G.vertices if x[v] >= 1/2}
    
    # 检查覆盖约束，不满足的补上
    while not is_valid_vertex_cover(G, C):
        e = find_uncovered_edge(G, C)
        C.add(e[0])  # 随便加一个端点
    
    return C

这个算法的思路是：LP最优解是下界，舍入后的解是上界，中间就是我们要控制的”误差”。

---

5. 旅行商问题TSP：度量TSP的2-近似与1.5-近似

5.1 问题定义

旅行商问题（TSP）：给定 $n$ 个城市及城市间的距离，找访问所有城市恰好一次并返回起点的最短路线。

这是NP难的——精确求解50个城市用动态规划需要 $O(n^2\cdot 2^n)$，100个城市基本就别想了。

TSP有个重要的变体：度量TSP，要求距离满足三角不等式度量TSP更”好说话”，近似算法能搞定；一般TSP就难伺候了。

三角不等式的意思是：从A到B的直接距离，不会比绕道C更远。这在现实中有道理——直线最短，绕路肯定更远。

5.2 度量TSP的2-近似

一个极其巧妙的算法：

1. 计算最小生成树（MST）
2. 对MST做深度优先遍历，得到访问顺序
3. 抄近路（跳过已访问的城市）

def metric_tsp_2_approx(G, w):
    # 1. 计算最小生成树
    T = mst_prim(G, w)
    
    # 2. 深度优先遍历得到顺序
    tour = dfs_preorder(T)
    
    # 3. 抄近路去除重复
    shortcut_tour = remove_duplicates(tour, w)
    
    return shortcut_tour

为什么这个算法有2-近似保证？

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

引理1：去掉最优回路任意一条边，得到一棵生成树，所以 $MST\le OPT$。

引理2：深度优先遍历每条树边恰好走两次（去程+回程），总距离 $2\cdot MST$。抄近路不增加距离，因为三角不等式保证”跳过去过的城市”不会更长。

于是：

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

5.3 Christofides算法：1.5-近似

1976年Christofides提出了改进算法，长期是度量TSP最佳常近似比：

核心思想：MST的奇度数顶点需要”配对”才能形成欧拉回路

def christofides_tsp(G, w):
    # Step 1: 最小生成树
    T = mst_prim(G, w)
    
    # Step 2: 找奇度数顶点集合 O
    O = [v for v in G.vertices if degree_in_T(v) % 2 == 1]
    
    # Step 3: 在 O 上找最小完美匹配 M
    induced_subgraph = G.induced_subgraph(O)
    shortest_paths = all_pairs_shortest_path(induced_subgraph, w)
    M = min_weight_perfect_matching(induced_subgraph, shortest_paths)
    
    # Step 4: T ∪ M 形成欧拉图
    H = Graph(T.edges + M.edges)
    
    # Step 5: 欧拉回路 → 哈密顿回路（抄近路）
    euler_tour = find_euler_tour(H)
    hamiltonian = shortcut_euler_tour(euler_tour, w)
    
    return hamiltonian

1.5-近似的证明思路：

$w(T)\le w(OPT)$ 之前证过了。关键在于最小匹配 $M$，可以证明 $w(M)\le w(OPT)/2$。

直观理解：最优TSP回路去掉一条边变成生成树，树里奇度顶点形成若干条不相交的路径。配对这些路径的端点，匹配权重不超过原来回路的一半。

于是：

$$w(ALG)\le w(T)+w(M)\le w(OPT)+\frac{w(OPT)}{2}=\frac{3}{2}w(OPT)$$

Important

Christofides算法1976年提出后，保持了度量TSP最佳常近似比记录近50年。直到2024年，Karlin、Kenyon等人用新分析技术略微改进了这个记录，但基本就是 $3/2$。

---

6. 集合覆盖问题：贪心近似算法的经典案例

6.1 问题定义

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

应用场景很广：

• 工厂选址：选哪些仓库能让所有客户都在配送范围内
• 特征选择：选哪些特征能解释尽量多的数据变异
• 医疗检测：选哪些检查项目能覆盖所有常见疾病

6.2 贪心算法的对数近似

贪心策略很简单：每轮选”性价比最高”的集合——每覆盖一个元素花钱最少。

def set_cover_greedy(U, S_sets, costs):
    C = ∅                    # 选中的集合
    uncovered = U.copy()     # 未覆盖元素
    
    # 预处理：建立元素到集合的映射
    element_to_sets = {}
    for i, s in enumerate(S_sets):
        for e in s:
            if e not in element_to_sets:
                element_to_sets[e] = []
            element_to_sets[e].append(i)
    
    # 优先队列：按性价比排序
    heap = []
    for i, s in enumerate(S_sets):
        if s:
            heapq.heappush(heap, (costs[i] / len(s), i, set(s)))
    
    while uncovered and heap:
        # 取性价比最高的
        _, i, s = heapq.heappop(heap)
        
        if not s.intersection(uncovered):
            continue  # 被其他集合覆盖了，跳过
        
        C.add(i)
        uncovered -= s
    
    return [S_sets[i] for i in C]

6.3 对数近似比分析

贪心算法的近似比是 $H_n=\ln n+O(1)$，其中 $n=|U|$。

这意味着什么？如果有1000个元素，最坏情况下贪心算法选的集合数可能达到最优的 $\ln 1000\approx 7$ 倍。

为什么是 $\ln n$？

每轮贪心至少覆盖 $1/k$ 的剩余元素，其中 $k$ 是还需选多少集合才能完全覆盖。经过 $H_n$ 轮，未覆盖元素就不到1个了。

# 模拟：n个元素，每轮覆盖剩余的1/k
remaining = n
for i in range(1, k+1):
    remaining *= (1 - 1/i)  # 每轮剩这么多
    # H_k = 1 + 1/2 + 1/3 + ... + 1/k ≈ ln k
# 跑完H_n轮，remaining < 1

Warning

集合覆盖不能有常数近似比——除非 P = NP。$O(\log n)$-近似已经是我们能做的最好了。

---

7. 装箱问题：First Fit Decreasing的近似比分析

7.1 问题定义

装箱问题（Bin Packing）：把物品装进容量为C的箱子，最小化箱子数量。

这问题应用场景太多了：货物装车、内存分配、云计算资源调度……

7.2 First Fit Decreasing算法

FFD算法分两步：

1. 把物品按大小降序排列
2. 用”首次适配”策略装箱：每个物品放进第一个能装下的箱子

def ffd_bin_packing(items, capacity):
    # 按大小降序
    sorted_items = sorted(items, reverse=True)
    
    bins = []  # 每个箱子里的物品
    
    for item in sorted_items:
        placed = False
        
        # 找第一个能装下的箱子
        for bin in bins:
            if sum(bin) + item <= capacity:
                bin.append(item)
                placed = True
                break
        
        # 装不下就开新箱子
        if not placed:
            bins.append([item])
    
    return bins

7.3 近似比分析

FFD的近似比是 $11/9\approx 1.22$——最多比最优多22%的箱子。

更精确地说：

$$FFD(I)\le \frac{11}{9}OPT(I)+\frac{6}{9}$$

这个结果看起来简单，证明却相当复杂，涉及到物品大小的细致分类讨论。

Example

如果物品大小都在 $(C/2,C]$ 区间，FFD和最优解一样好。如果物品大小都是 $C/3$，FFD会浪费更多空间。

---

8. PTAS vs FPTAS：多项式时间近似方案的强度

8.1 什么时候需要PTAS

常数近似比不够用怎么办？有时候你需要更精细的控制——比如”保证解至少是最优的95%”。

PTAS（多项式时间近似方案）就是干这个的：给定任意 $ϵ>0$，能在多项式时间内得到 $(1+ϵ)$-近似。

PTAS的核心思想：分而治之

以调度问题为例，核心洞察是：

• 大作业数量有限，可以精确枚举分配方案
• 小作业太多，用贪心处理就行——反正单个影响小

def makespan_ptas(jobs, m, epsilon):
    n = len(jobs)
    
    # 阈值：大作业 vs 小作业
    T = epsilon * optimal_makespan_lower_bound(jobs, m)
    
    big_jobs = [j for j in jobs if j > T]
    small_jobs = [j for j in jobs if j <= T]
    
    # 大作业数量有限，枚举分配
    if len(big_jobs) <= 2 * m / epsilon:
        best_schedule = enumerate_big_jobs(big_jobs, m)
    else:
        # 太多大作业？用随机化
        best_schedule = randomized_partition(big_jobs, m)
    
    # 小作业用贪心塞到最闲的机器
    for job in sorted(small_jobs, reverse=True):
        min_machine = min(range(m), key=lambda i: best_schedule[i])
        best_schedule[min_machine] += job
    
    return max(best_schedule)

8.2 FPTAS：更强的保证

FPTAS（完全多项式时间近似方案）要求时间对 $ϵ$ 是多项式依赖——不是 $n^{1/ϵ}$，而是 $n^c/{ϵ}^d$。

背包问题就有FPTAS，核心技巧是价值缩放：

def knapsack_fptas(items, W, epsilon):
    n = len(items)
    
    # 价值上界
    V = sum(item.value for item in items)
    
    # 缩放因子
    K = epsilon * V / n
    
    # 缩放每个物品的价值
    scaled_items = []
    for item in items:
        scaled_value = int(item.value / K)
        scaled_items.append(Item(scaled_value, item.weight))
    
    # 在缩放空间上跑DP
    total_scaled = sum(item.scaled_value for item in scaled_items)
    dp = knapsack_dp(scaled_items, W, total_scaled)
    
    return reconstruct_solution(dp, scaled_items, K)

为什么价值缩放有效？

缩放后，物品价值从 $v$ 变成 $\lfloor v/K\rfloor$，精度损失最多 $nK$。调整一下参数，这个损失可以控制在 $ϵ\cdot OPT$ 以内。

8.3 PTAS和FPTAS的区别

特征	PTAS	FPTAS
时间对ε的依赖	$n^{f(1/ϵ)}$	$n^c/{ϵ}^d$
实用性	ε小时很慢	更可控
适用范围	更广	需要伪多项式可解

简单说：FPTAS是PTAS的加强版，但不是所有PTAS都能升级成FPTAS。背包问题可以，装配线调度问题就不行。

---

9. 随机近似算法：用抛硬币提高近似质量

9.1 随机化的魅力

确定性算法对同一个输入每次给出相同结果。随机算法加入随机性，同一个输入可能跑出不同结果——但在期望意义上更好。

对于顶点覆盖，一个简单的随机算法：

def randomized_vertex_cover(G):
    import random
    
    # 每个顶点独立以1/2概率"预选"
    pre_selected = {v for v in G.vertices if random.random() < 0.5}
    
    # 修复：确保所有边被覆盖
    cover = pre_selected.copy()
    
    for (u, v) in G.edges:
        if u not in cover and v not in cover:
            # 两端都未选？概率1/4，随机救一个
            cover.add(random.choice([u, v]))
    
    return cover

9.2 期望分析

为什么随机算法能有近似保证？

设 $C^{\ast }$ 是最优覆盖。对于每条边 $(u,v)$：

• 预选中 $u$ 的概率：$1/2$
• 预选中 $v$ 的概率：$1/2$
• 两端都未预选的概率：$1/4$

修复操作只在两端都未预选时执行，此时随机加一个端点，期望加 $1/2$ 个顶点。

每条边期望贡献的顶点：

• 预选阶段的期望：$1/2$（每个端点 $1/2$，相加）
• 修复阶段的期望：$1/4\times 1=1/4$

总期望 $|ALG|\le 2\cdot |OPT|$，即2-近似。

9.3 随机舍入的威力

Goemans-Williamson的最大切割算法是随机舍入的经典案例。

核心思想：

1. 把最大切割问题松弛成半定规划（SDP）
2. SDP的最优解是单位向量 $v_i$
3. 随机选一个超平面，把向量分成两边

def gw_max_cut(G):
    # 1. 求解SDP松弛
    V = solve_max_cut_sdp(G)  # 返回单位向量 v_i
    
    # 2. 随机超平面舍入
    r = random_unit_vector(d=len(G.vertices))
    
    # 3. 按超平面切割
    S = {i for i in G.vertices if V[i].dot(r) >= 0}
    T = G.vertices - S
    
    return S, T

这个算法的近似比是惊人的 0.878——比任何已知确定性算法都好。

为什么是0.878？

关键在于：对于任意边 $(i,j)$，被切割的概率至少是 $\arccos (y_{ij})/\pi$，其中 $y_{ij}$ 是SDP解中 $v_i\cdot v_j$ 的值。

利用一些三角函数不等式可以证明：

$$\frac{\arccos (y)}{\pi }\ge 0.878\cdot \frac{1-y}{2}$$

所以在期望意义上，算法总是能达到最优值的至少87.8%。

---

10. 近似算法与机器学习：聚类、特征选择中的近似思想

10.1 K-means的近似版本

K-means问题：把n个点分成k个簇，最小化簇内平方距离之和。

这问题是NP难的，但有个简单的贪心初始化：K-means++。

def kmeans_plus_plus(data, k):
    import random
    import numpy as np
    
    centers = []
    
    # 第一个中心：随机选
    centers.append(random.choice(data))
    
    # 后续中心：按距离平方的概率选择
    for _ in range(1, k):
        distances = np.array([
            min(np.linalg.norm(x - c)**2 for c in centers) 
            for x in data
        ])
        
        # 距离越远越可能被选中
        probs = distances / distances.sum()
        next_center = random.choices(data, weights=probs, k=1)[0]
        centers.append(next_center)
    
    return centers

K-means++的近似比是 $O(\log k)$——多次随机初始化再选最好的，实践中效果很好。

10.2 特征选择的贪婪近似

选哪些特征最能预测目标变量？这问题可以建模成次模函数最大化。

次模性：多选一个特征的边际收益递减。这特性让贪心算法有理论保证。

def greedy_feature_selection(X, y, k, model):
    """
    贪心选k个特征
    目标：最大化预测准确率
    """
    selected = []
    remaining = set(range(X.shape[1]))
    
    for _ in range(k):
        best_feature = None
        best_score = -float('inf')
        
        for f in remaining:
            candidate = selected + [f]
            X_subset = X[:, candidate]
            score = cross_val_score(model, X_subset, y)
            
            if score > best_score:
                best_score = score
                best_feature = f
        
        selected.append(best_feature)
        remaining.remove(best_feature)
    
    return selected

10.3 神经网络的近似剪枝

把网络剪枝建模成次模函数优化，贪心删除参数可以保留大部分性能：

def neural_pruning(model, k, val_data):
    """
    贪心剪枝：每次删掉对性能影响最小的参数
    """
    remaining_params = set(range(len(model.params)))
    selected = set()
    
    def utility(selected_params):
        masked_model = mask_params(model, selected_params)
        return evaluate_accuracy(masked_model, val_data)
    
    for _ in range(k):
        # 找边际增益最大的参数（剪掉它损失最小）
        best_param = max(
            remaining_params, 
            key=lambda p: marginal_gain(utility, selected, p)
        )
        selected.add(best_param)
        remaining_params.remove(best_param)
    
    return selected

---

11. NP-hard优化问题的实用策略：启发式 vs 近似算法

11.1 启发式算法

启发式（Heuristics）是为特定问题设计的”经验法则”，没有理论保证但实践中往往好用。

代表：

• 模拟退火：允许偶尔接受更差的解来跳出局部最优
• 遗传算法：模拟自然选择，多个解”交配”、“变异”
• 蚁群算法：模拟蚂蚁觅食，信息素指导搜索

优点：实现简单，效果在很多场景下可接受 缺点：没有近似保证，不知道离最优有多远

11.2 近似算法

近似算法有理论保证的近似比，你知道解最多差多少。

代表：

• 顶点覆盖的2-近似：解最多是最优的2倍
• 度量TSP的1.5-近似：解最多是最优的1.5倍
• 集合覆盖的 $O(\log n)$-近似：解最多是最优的 $O(\log n)$ 倍

优点：结果可靠，有理论背书 缺点：设计分析往往很复杂

11.3 实际选择

面对一个问题，怎么选？

场景	推荐选择
需要理论保证	近似算法
问题有特殊结构	近似算法
需要快速出结果	启发式
问题规模极大	启发式或近似算法
两者结合	用近似算法出初始解，再用启发式改进

混合策略：先用近似算法得到一个”不太差”的解，再用局部搜索或元启发式算法改进。贪心2-近似 + 局部搜索改进，在很多问题上效果拔群。

---

12. 局部搜索算法：爬山法、模拟退火、迭代局部搜索

12.1 爬山法

最简单粗暴的局部搜索：从一个初始解出发，每次找一个更好的邻居，直到找不到为止。

def hill_climbing_max_cut(G, max_iterations=1000):
    import random
    
    # 随机初始解
    vertices = list(G.vertices)
    random.shuffle(vertices)
    mid = len(vertices) // 2
    S = set(vertices[:mid])
    
    for _ in range(max_iterations):
        improved = False
        
        # 遍历所有顶点，找改进移动
        for v in G.vertices:
            current = cut_weight(G, S)
            
            # 翻转v
            if v in S:
                S.remove(v)
            else:
                S.add(v)
            
            if cut_weight(G, S) > current:
                improved = True  # 接受这个移动
            else:
                # 回退
                if v in S:
                    S.remove(v)
                else:
                    S.add(v)
        
        if not improved:
            break
    
    return S

爬山法的问题是容易陷入局部最优——可能爬到一个小山头，但远处有更高的山峰。

12.2 模拟退火

模拟退火的核心思想：温度高时随机探索，温度低时精细搜索。

def simulated_annealing_tsp(distances, initial_temp=10000, cooling_rate=0.9995):
    import random
    import math
    
    n = len(distances)
    
    # 初始解：随便一个哈密顿回路
    current_tour = list(range(n))
    random.shuffle(current_tour)
    current_cost = tour_cost(current_tour, distances)
    
    best_tour = current_tour[:]
    best_cost = current_cost
    
    temp = initial_temp
    
    while temp > 1:
        # 随机选一个邻域移动（2-opt）
        i, j = random.sample(range(n), 2)
        if i > j:
            i, j = j, i
        
        # 翻转tour[i:j+1]
        new_tour = current_tour[:i] + current_tour[i:j+1][::-1] + current_tour[j+1:]
        new_cost = tour_cost(new_tour, distances)
        
        # Metropolis准则
        delta = new_cost - current_cost
        if delta < 0 or random.random() < math.exp(-delta / temp):
            current_tour = new_tour
            current_cost = new_cost
            
            if current_cost < best_cost:
                best_tour = current_tour[:]
                best_cost = current_cost
        
        temp *= cooling_rate
    
    return best_tour

模拟退火允许偶尔接受更差的解（概率随温度下降而减小），这让它有机会跳出局部最优。

12.3 迭代局部搜索

迭代局部搜索（ILS）的套路：在局部最优解附近搞破坏，重新搜索。

def iterative_local_search_tsp(distances, max_iterations=100, perturbation_size=10):
    import random
    
    # 初始解
    tour = greedy_tsp_tour(distances)
    tour = two_opt_local_search(tour, distances)  # 先局部搜索到局部最优
    
    best_tour = tour[:]
    best_cost = tour_cost(tour, distances)
    
    for _ in range(max_iterations):
        # 扰动：在当前解附近搞破坏
        perturbed = perturb(tour, perturbation_size)
        
        # 局部搜索
        improved_tour = two_opt_local_search(perturbed, distances)
        improved_cost = tour_cost(improved_tour, distances)
        
        # 接受准则：比当前解好才接受
        if improved_cost < tour_cost(tour, distances):
            tour = improved_tour
            
            # 更好的全局解？
            if improved_cost < best_cost:
                best_tour = improved_tour[:]
                best_cost = improved_cost
    
    return best_tour

ILS的诀窍是扰动要足够大才能跳出局部最优，但也不能太大以至于退化成随机搜索。

---

13. 动手实验：用近似算法求解TSP和顶点覆盖问题

13.1 TSP实验

import random
import numpy as np
 
def generate_tsp_instances(n_points=50, seed=42):
    """生成随机TSP实例"""
    random.seed(seed)
    points = [(random.random(), random.random()) for _ in range(n_points)]
    
    # 计算距离矩阵（欧氏距离）
    dist = np.zeros((n_points, n_points))
    for i in range(n_points):
        for j in range(n_points):
            dist[i][j] = np.sqrt((points[i][0]-points[j][0])**2 + 
                                  (points[i][1]-points[j][1])**2)
    
    return points, dist
 
def greedy_tsp(dist):
    """最近邻贪心"""
    n = len(dist)
    visited = [False] * n
    tour = [0]
    visited[0] = True
    
    for _ in range(n-1):
        current = tour[-1]
        nearest = min((j for j in range(n) if not visited[j]),
                      key=lambda j: dist[current][j])
        tour.append(nearest)
        visited[nearest] = True
    
    tour.append(0)  # 返回起点
    return tour
 
def christofides_tsp(dist):
    """简化版Christofides算法"""
    from scipy.sparse.csgraph import minimum_spanning_tree
    from scipy.sparse import csr_matrix
    
    n = len(dist)
    
    # MST
    mst = minimum_spanning_tree(csr_matrix(dist)).toarray()
    
    # 找奇度数顶点
    degrees = (mst > 0).sum(axis=1)
    odd_vertices = [i for i in range(n) if degrees[i] % 2 == 1]
    
    # 简化：贪婪匹配
    # （完整的Blossom算法实现较复杂）
    matched = set()
    matching = []
    for v in odd_vertices:
        if v not in matched:
            for u in odd_vertices:
                if u != v and u not in matched:
                    matched.add(v)
                    matched.add(u)
                    matching.append((v, u))
                    break
    
    # 合并构建欧拉回路（简化版）
    tour = list(range(n))
    
    return tour
 
def evaluate_tour(tour, dist):
    """计算回路长度"""
    return sum(dist[tour[i]][tour[i+1]] for i in range(len(tour)-1))
 
# 实验
points, dist = generate_tsp_instances(50)
 
greedy_tour = greedy_tsp(dist)
greedy_cost = evaluate_tour(greedy_tour, dist)
 
christofides_tour = christofides_tsp(dist)
christofides_cost = evaluate_tour(christofides_tour, dist)
 
print(f"贪心算法成本: {greedy_cost:.2f}")
print(f"Christofides成本: {christofides_cost:.2f}")

13.2 顶点覆盖实验

import random
import networkx as nx
 
def generate_random_graph(n=100, edge_prob=0.3, seed=42):
    """生成随机图"""
    random.seed(seed)
    G = nx.erdos_renyi_graph(n, edge_prob, seed=seed)
    return G
 
def greedy_vertex_cover(G):
    """贪心2-近似"""
    cover = set()
    edges = set(G.edges())
    
    while edges:
        # 选一条边
        u, v = random.choice(list(edges))
        cover.add(u)
        cover.add(v)
        # 删除与u、v相邻的边
        edges = {e for e in edges if e[0] not in (u, v) and e[1] not in (u, v)}
    
    return cover
 
def lp_rounding_vertex_cover(G):
    """LP舍入2-近似（需要LP求解器）"""
    import numpy as np
    
    n = G.number_of_nodes()
    
    # 这里用简化的贪心实现代替LP求解
    # 实际应该用CVXPY或PuLP求解LP
    
    cover = set()
    degrees = dict(G.degree())
    
    while degrees:
        # 选度最大的顶点
        v = max(degrees, key=degrees.get)
        cover.add(v)
        
        # 删除v及其邻居的边，更新度数
        neighbors = list(G.neighbors(v)) + [v]
        for u in neighbors:
            if u in degrees:
                del degrees[u]
    
    return cover
 
def evaluate_cover(G, cover):
    """验证覆盖并返回大小"""
    for u, v in G.edges():
        if u not in cover and v not in cover:
            return False, 0
    return True, len(cover)
 
# 实验
G = generate_random_graph(100, 0.1)
 
greedy_cover = greedy_vertex_cover(G)
valid_greedy, size_greedy = evaluate_cover(G, greedy_cover)
 
lp_cover = lp_rounding_vertex_cover(G)
valid_lp, size_lp = evaluate_cover(G, lp_cover)
 
print(f"贪心覆盖: {size_greedy}个顶点, 有效={valid_greedy}")
print(f"LP舍入覆盖: {size_lp}个顶点, 有效={valid_lp}")

---

14. 近似难度的层级：APX与PTAS层级

14.1 APX类

APX类（Constant-factor Approximable）是存在常数近似比的NP难优化问题构成的集合。

APX类代表问题：

• 顶点覆盖（2-近似）
• 度量旅行商问题（1.5-近似，Christofides算法）
• 最大切割（0.878-近似，Goemans-Williamson算法）
• 图着色（$\Delta +1$近似，$\Delta$是最大度）

14.2 APX完全问题

APX类中最难的问题叫APX完全问题。任何APX问题可以归约到APX完全问题。

集合覆盖只有 $O(\log n)$-近似，比常数更差——所以集合覆盖是APX难的，但可能不是APX完全的（取决于归约细节）。

14.3 近似难度的层级

并非所有NP难问题都”同样难”，它们在近似难度上分了三六九等：

近似能力	问题举例	典型算法
常数近似	顶点覆盖、度量TSP	贪心、LP舍入
$O(\log n)$ 近似	集合覆盖、设施选址	原始-对偶
PTAS	某些调度问题	分支定界+枚举
无多项式近似	一般TSP	不可能

---

15. PCP定理与不可近似性

15.1 PCP定理的冲击

PCP定理（概率可检验证明）是近似算法理论的里程碑：

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

这定理的意思是：NP问题有一个”概率可检验”的证明，检查者只看常数个随机比特就能验证证明的正确性。

对近似算法的意义：这意味着”验证一个解是否接近最优”和”验证一个证明是否正确”在计算上一样难。所以 $1-ϵ$-近似和精确求解可能同样困难。

15.2 不可近似性结果

Håstad证明了Max-3SAT的一些硬下界：

• 存在 $ϵ>0$，使得 $(1-ϵ)$-近似是NP难的
• 即使每个变量恰好出现在3个子句中

换句话说：如果你能以99%的最优值近似Max-3SAT，你就解决了NP问题。

15.3 不可近似性层级

近似比	对应问题	硬度来源
$1-ϵ$	Max-3SAT	PCP定理
$1-1/\sqrt{n}$	最大独立集	PCPs
${\log }^{1-ϵ}n$	集合覆盖	Raz-Safra
$n^{1-ϵ}$	某些着色问题	层级

---

16. 现代近似算法前沿

16.1 度量旅行商问题的最优近似比

Christofides算法的3/2近似比是最优的吗？

• 下界：基于Unique Games猜想，存在 $\Omega (\mathrm{1.005...})$-hardness
• 上界：$3/2$（Christofides, 1976）
• 间隙：约1.49倍

2024年的突破性工作对特定图类给出了更好的近似，但一般度量TSP仍未解决。

16.2 Unique Games猜想的影响

Unique Games Conjecture（UGC）预测：如果存在多项式时间算法以 $(1-ϵ)$-近似Unique Games问题，则 $P=NP$。

近似算法中UGC的应用：

• 最大切割：Goemans-Williamson的0.878近似在UGC下是最优的
• Sparsest Cut：$O(\log n)$-近似在UGC下是最优的
• 顶点覆盖：2-近似在UGC下是最优的

16.3 参数化近似算法

新方向：允许近似比随某个参数 $k$ 变化：

• $k$-团问题：$O(n^{1/2+ϵ})$ 近似
• $k$-支配集：$O(\log n)$-近似在 $n$ 中，$O(1)$ 在 $k$ 中

这打开了”固定参数近似算法”的新领域。

---

17. 近似算法的实践指南

17.1 选择近似策略的决策树

问题特征 → 选择策略
  │
  ├─ 有LP松弛结构 → 检查对偶性质
  │    ├─ 对偶是"好"的 → 原始-对偶
  │    └─ 舍入技术可行 → LP舍入
  │
  ├─ 问题有次模结构 → 贪婪+分析
  │    └─ 考虑局部搜索增强
  │
  ├─ 需要高近似质量 → PTAS/FPTAS
  │    ├─ 伪多项式可解 → 考虑FPTAS
  │    └─ 大小类分离 → PTAS
  │
  └─ 问题规模极大 → 启发式+分析
       └─ 使用局部搜索/元启发式

17.2 近似比验证

def verify_approximation_ratio(algorithm, problem_instances, 
                                optimal_values=None, num_samples=1000):
    """
    实验验证算法的近似比
    """
    results = []
    
    for instance in problem_instances[:num_samples]:
        algorithm_value = algorithm(instance)
        
        if optimal_values:
            optimal = optimal_values[instance]
        else:
            # 用LP松弛下界代替
            optimal = compute_lp_lower_bound(instance)
        
        ratio = algorithm_value / optimal
        results.append(ratio)
    
    return {
        'mean': np.mean(results),
        'median': np.median(results),
        'worst': np.max(results),
        'percentile_95': np.percentile(results, 95),
        'percentile_99': np.percentile(results, 99)
    }

17.3 效率-精度权衡

def knapsack_algorithms_comparison(items, capacity):
    """
    展示效率-精度权衡的多种算法
    """
    algorithms = {
        '动态规划': {
            'algorithm': lambda: knapsack_dp(items, capacity),
            'time': 'O(nW)',
            'quality': '精确'
        },
        'FPTAS(ε=0.1)': {
            'algorithm': lambda: knapsack_fptas(items, capacity, 0.1),
            'time': 'O(n^3)',
            'quality': '1.1-近似'
        },
        'FPTAS(ε=0.01)': {
            'algorithm': lambda: knapsack_fptas(items, capacity, 0.01),
            'time': 'O(100n^3)',
            'quality': '1.01-近似'
        },
        '贪心密度': {
            'algorithm': lambda: greedy_by_density(items, capacity),
            'time': 'O(n log n)',
            'quality': '~50%'
        }
    }
    
    return algorithms

---

18. 算法性能总结

问题	最佳近似比	算法	年份	最优性
顶点覆盖	2	贪婪/LP舍入	1974	最优
最大切割	0.878	GW-SDP	1995	最优（UGC）
度量TSP	1.5	Christofides	1976	可能最优
集合覆盖	$O(\log n)$	贪婪	1974	最优
加权集合覆盖	$O(\log n)$	原始-对偶	1987	最优
背包(FPTAS)	$1+ϵ$	缩放DP	1984	最优
调度(Makespan)	$4/3-1/(3m)$	LPT	1966	可能最优
加权着色	$O(n/\log n)$	贪婪	-	最优

---

参考来源

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.
6. Goemans, M. X., & Williamson, D. P. (1995). Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. JACM.
7. Feige, U. (1998). A Threshold of ln n for Approximating Set Cover. JACM.
8. Bar-Yehuda, R., & Even, S. (1981). A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problem. J. Algorithms.
9. Hochbaum, D. S., & Shmoys, D. B. (1987). Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results. JACM.
10. Sahni, S., & Gonzalez, T. (1976). P-Complete Approximation Problems. JACM.

---

相关文档

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