近似算法详解

关键词速览

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

摘要

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

在现代计算实践中，精确求解NP难问题在大规模实例上往往不可行。近似算法提供了一条介于计算可行性与解质量之间的务实路径。从1974年Sahni和Gonzalez证明顶点覆盖的常数近似比，到1995年Arora等人证明度量旅行商问题的多项式时间逼近方案（PTAS），再到2008年Kleinberg证明了在线社会网络中的信息传播可以用常数近似比估计，近似算法的理论边界持续拓展。

本文将从五个维度展开：首先建立近似算法的数学基础与分类体系；然后深入剖析六大经典近似技术的设计哲学与理论保证；接着通过丰富的算法案例展示技术细节；再讨论近似难度的层级结构与下界证明；最后探讨近似算法与机器学习、运筹优化和生物信息学等领域的深度融合。

1. 近似算法的理论基础

1.1 近似比的形式定义

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

ρ (n) = I \in I_{n} max \frac{A L G ( I )}{OPT ( I )}

其中 $A L G (I)$ 为算法输出值， $OPT (I)$ 为最优值。对于 $α$ -近似算法，满足 $ρ (n) \leq α$ 。

定义形式化：

一个算法 $A$ 是 $α$ -近似算法，当且仅当对所有输入实例 $I$ ，都有
$\frac{A L G ( I )}{OPT ( I )} \leq α （最小化问题）$
或
$\frac{OPT ( I )}{A L G ( I )} \leq α （最大化问题）$

Note

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

近似质量的多层次理解：

从不同视角审视近似质量，可以得到更丰富的洞见：

绝对近似比：对所有实例 $I$ ，固定常数 $α$ 满足 $A L G (I) / OPT (I) \leq α$ 。这类算法最理想但极为罕见。
渐进近似比：关注问题规模趋于无穷时的行为，即 $lim sup_{n \to \infty} \frac{A L G ( n )}{OPT ( n )}$ 。允许小规模实例有更差的表现。
分布近似比：假设输入服从某个概率分布，分析算法相对于最优的期望表现。这对应随机近似算法的分析框架。
差分近似比：定义 $∣ A L G - OPT ∣ \leq α \cdot OPT + β$ ，其中 $β$ 是与实例无关的常数项。这比纯比值更宽松。

1.2 近似方案的层次结构

近似方案（Approximation Schemes）是一族参数化的算法，通过牺牲精度换取效率。层次越深，能力越强，但计算代价也越高。

近似方案	时间复杂度	近似质量	设计难度
$β$ -近似	$O (n^{k})$ 常数 $β$	常数近似比	中等
PTAS	$O (n^{1/ ϵ})$	$(1 + ϵ)$ -近似	困难
EPTAS	$O (n^{c} \cdot f (ϵ))$	$(1 + ϵ)$ -近似	极难
FPTAS	$O (n^{3} / ϵ^{2})$	$(1 + ϵ)$ -近似	极难

PTAS的定义：

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

FPTAS的定义：

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

**EPTAS（高效PTAS）**是对PTAS的增强，要求时间复杂度为 $n^{O (1)} \cdot f (ϵ)$ ，即多项式因子不依赖于 $ϵ$ 的函数形式。

多项式时间近似方案的存在性层级：

并非所有NP难问题都有PTAS。根据近似难度的研究，问题可以按近似方案的可用性分层：

具有常数近似比的问题：存在某个固定 $α$ 的 $α$ -近似算法。如顶点覆盖（2-近似）、集合覆盖（ $O (lo g n)$ -近似）、最大切割（0.878-近似）。
具有渐近PTAS的问题：当输入规模足够大时，可以达到任意精度。如某些装箱问题的变体。
具有PTAS但无FPTAS的问题：时间复杂度随 $ϵ$ 的倒数指数增长，但仍为多项式。如某些调度问题。
完全没有多项式时间近似方案的问题：除非 $P = NP$ ，否则任何多项式时间算法都无法提供有意义的近似。如0-1扩展率问题。

1.3 近似难度的层级：APX与PTAS层级

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

APX类问题的典型代表：

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

PTAS类：存在PTAS的NP难问题构成PTAS类。PTAS ⊂ APX，即有PTAS的问题必定有常数近似比（取足够大的 $ϵ$ ）。

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

集合覆盖是APX完全的吗？实际上，集合覆盖只有 $O (lo g n)$ -近似，这比对数更差——所以集合覆盖是APX难的但可能不是APX完全的（取决于具体的归约定义）。

Gap-preserving归约：近似算法设计中的关键工具。若问题A到问题B存在gap-preserving归约，则A的近似比下界可以传递到B。

Example

设 $Π_{1}$ 和 $Π_{2}$ 是两个优化问题，若存在多项式时间函数 $f$ 和常数 $α \geq 1$ 使得：

若 $I$ 是 $Π_{1}$ 的YES实例（最优值 $\leq s$ ），则 $f (I)$ 是 $Π_{2}$ 的YES实例

若 $I$ 是 $Π_{1}$ 的NO实例（最优值 $\geq t$ ），则 $f (I)$ 是 $Π_{2}$ 的NO实例

其中 $t / s \geq α$ ，则 $Π_{2}$ 的近似难度至少为 $α$ 。

1.4 近似比与计算复杂度的深层联系

近似算法的研究揭示了NP难问题内部的精细结构。并非所有NP难问题都”同样难”——它们在近似难度上存在显著差异。

精确求解 vs 近似求解的时间鸿沟：

问题	精确算法复杂度	最佳常数近似比	近似算法复杂度
顶点覆盖	$O (1.2 2^{n})$	2	$O (n^{2})$
最大切割	$O (1.1 5^{n})$	0.878	$O (n^{2.37})$
旅行商(度量)	$O (2^{n})$	1.5	$O (n^{3})$
集合覆盖	$O (2^{n})$	$O (lo g n)$	$O (n^{2})$
图着色(一般)	$O (2^{n})$	$O (n / lo g n)$	$O (n^{2})$

Important

近似算法使NP难问题从”在多项式时间内无法精确求解”变为”在多项式时间内可以接近最优求解”。这一转变对于工程应用具有决定性意义。

2. 近似算法的六大核心技术

2.1 贪心法（Greedy Method）

贪心法是最直观也最常用的近似技术。其核心思想是：在每一步做出当前最优的选择，期望通过局部最优的累积达到全局近似最优。

贪心法的设计原则：

最优子结构：问题的最优解包含子问题的最优解
贪心选择性质：可以通过局部最优选择构造全局最优解
无后效性：某状态一旦确定，不受后续决策影响

贪心法的典型应用场景：

活动选择问题：选择最大数量的不重叠活动
哈夫曼编码：构造最优前缀码
最小生成树：Prim和Kruskal算法
分数背包问题：按单位价值贪心

def greedy_activity_selection(activities):
    """
    贪心选择最大数量的兼容活动
    策略：按结束时间排序，依次选择最早结束且与已选活动兼容的活动
    """
    # 按结束时间排序
    sorted_activities = sorted(activities, key=lambda a: a.end)
    
    selected = []
    last_end_time = -float('inf')
    
    for activity in sorted_activities:
        if activity.start >= last_end_time:
            selected.append(activity)
            last_end_time = activity.end
    
    return selected

贪心法的近似保证分析：

贪心法的近似质量取决于问题的底层结构。以下是几类典型情况的分析框架：

拟阵上的贪心：若优化问题可以建模为拟阵上的独立集最大化，则贪心法给出最优解。
次模函数最大化：对于单调次模函数的约束最大化，简单的贪心法给出 $(1 - 1/ e)$ -近似（约63.2%）。
非次模函数：贪心法可能表现不佳，需要更复杂的技术。

Warning

贪心法并非万能。某些问题（如旅行商问题的贪心近似）可能给出任意差的近似比（接近 $O (lo g n)$ ）。设计贪心算法时必须仔细分析其近似保证。

2.2 线性规划松弛与舍入（LP Relaxation and Rounding）

线性规划松弛是近似算法中最有力的技术之一。其核心思想是：将离散优化问题松弛为连续优化问题，求解后设法将分数解”舍入”为整数解。

标准流程：

原始ILP → 松弛为LP → 求解LP → 舍入 → 整数解

舍入策略的分类：

确定性舍入：使用固定的规则将分数解转换为整数解
随机舍入：以一定概率选择每个变量的整数值
参数化舍入：基于某个参数决定舍入阈值
顺序舍入：按一定顺序依次固定变量

def lp_rounding_vertex_cover(G):
    """
    顶点覆盖的LP松弛与确定性舍入
    """
    from scipy.optimize import linprog
    import numpy as np
    
    n = len(G.vertices)
    
    # 构建ILP: min sum(x_v) s.t. x_u + x_v >= 1, x_v in {0,1}
    # 松弛为LP: min sum(x_v) s.t. x_u + x_v >= 1, 0 <= x_v <= 1
    
    # LP求解（使用顶点覆盖的特殊结构）
    x = solve_vertex_cover_lp(G)
    
    # 确定性舍入：取阈值 0.5
    C = {v for v in G.vertices if x[v] >= 0.5}
    
    # 验证覆盖性质（舍入可能不满足约束，需要后处理）
    while not is_valid_cover(G, C):
        uncovered_edge = find_uncovered_edge(G, C)
        C.add(uncovered_edge.u)  # 任选一个端点加入
    
    return C

LP舍入的典型下界：

若LP的最优值为 $L P^{*}$ ，最优整数值为 $OPT$ ，则 $L P^{*} \leq OPT$ 。舍入得到的解 $A L G$ 满足：

A L G \leq α \cdot L P^{*} \leq α \cdot OPT

其中 $α$ 是舍入过程的近似因子。分析的关键在于建立 $A L G$ 与 $L P^{*}$ 的联系。

2.3 半定规划松弛（Semidefinite Programming Relaxation）

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

SDP vs LP：

特征	线性规划	半定规划
变量形式	向量	对称矩阵
约束类型	线性不等式	半正定性 + 线性
求解复杂度	多项式（单纯形/内点）	多项式（内点法）
松弛能力	弱	强
典型应用	0-1变量的线性约束	向量嵌入问题

Goemans-Williamson最大切割算法：

最大切割问题可以自然地建模为SDP：

max \frac{1}{2} (i, j) \in E \sum (1 - v_{i} \cdot v_{j}) s.t. ∥ v_{i} ∥ = 1, v_{i} \in R^{n}

其中 $v_{i} \cdot v_{j} = 1$ 表示顶点 $i$ 和 $j$ 在同一侧， $v_{i} \cdot v_{j} = - 1$ 表示在不同侧。

def gw_max_cut(G):
    """
    Goemans-Williamson SDP近似算法
    返回一个近似比为0.878的最大切割
    """
    # 1. 求解SDP松弛
    V = solve_max_cut_sdp(G)  # 返回单位向量 v_i
    
    # 2. 随机超平面舍入
    # 随机选择单位向量 r（服从均匀分布）
    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

GW算法的近似比证明思路：

设 $y_{ij} = E [v_{i} \cdot v_{j}]$ 是随机超平面舍入后边 $(i, j)$ 被切割的概率。可以证明：

E [切割权重] = (i, j) \in E \sum \frac{arccos ( y _{ij} )}{π} \geq 0.878 \cdot (i, j) \in E \sum \frac{1 - y _{ij}}{2}

其中 $\frac{1 - y _{ij}}{2}$ 是SDP松弛给出的切割值上界。

Important

GW算法是近30年来最重要的近似算法之一。它将最大切割的近似比从0.5（简单随机）提升到0.878，并且这个结果在Unique Games猜想成立时是最优的。

2.4 原始-对偶方法（Primal-Dual Method）

原始-对偶方法是贪心法与LP对偶理论的优雅结合。它在不使用精确LP求解的情况下，构造近似比为常数的主问题和其对偶的可行解。

原始-对偶的哲学：

避免精确求解：不求解大规模LP，而是通过迭代构造
对偶可行性：始终保持对偶变量的非负性和约束满足
原始可行性：逐步增加原始变量以满足约束
紧密界分析：利用对偶可行解的价值界定原始解的近似比

def primal_dual_set_cover(U, S_sets, costs):
    """
    集合覆盖的原始-对偶算法
    """
    # 初始化
    primal_solution = {}  # 原始变量
    dual_solution = {}   # 对偶变量
    covered = set()      # 已覆盖元素
    
    for s in S_sets:
        primal_solution[s] = 0
    
    for e in U:
        dual_solution[e] = 0
    
    # 迭代构造
    while covered != U:
        # 增加未覆盖元素的对偶值
        min_cost_ratio = float('inf')
        for e in U - covered:
            # 增加 e 的对偶值直到某个集合的约束紧绑
            # 即 sum_e' in S of dual[e'] = cost(S)
            dual_solution[e] += 1
        
        # 选择被紧绑的集合
        for s in S_sets:
            if sum(dual_solution[e] for e in s) >= costs[s]:
                primal_solution[s] = 1
                covered.update(s)
                # 重置相关元素的对偶值
                for e in s:
                    dual_solution[e] = 0
    
    return [s for s in S_sets if primal_solution[s] == 1]

原始-对偶的分析框架：

设 $P$ 是原始问题的目标函数， $D$ 是对偶问题的目标函数。根据弱对偶定理， $D \leq P^{*}$ ，其中 $P^{*}$ 是原始最优值。

若算法构造的原始解 $P$ 和对偶解 $D$ 满足 $P \leq α \cdot D$ ，则 $P \leq α \cdot P^{*}$ ，即得到 $α$ -近似。

2.5 局部搜索（Local Search）

局部搜索是一种朴素的迭代改进方法：从一个初始可行解出发，通过一系列小的”扰动”（局部操作）改进解的质量，直到无法改进为止。

局部搜索的核心要素：

邻域定义：如何从当前解产生邻居
邻域搜索策略：最佳改进、最速上升、第一改进
跳出机制：防止陷入局部最优
时间复杂度：单次搜索的终止条件

def local_search_max_cut(G, max_iterations=1000):
    """
    最大切割的局部搜索算法
    邻域：将一个顶点从一侧移动到另一侧
    """
    import random
    
    # 随机初始切割
    vertices = list(G.vertices)
    random.shuffle(vertices)
    mid = len(vertices) // 2
    S = set(vertices[:mid])
    T = set(vertices[mid:])
    
    for _ in range(max_iterations):
        improved = False
        
        # 遍历所有顶点，找改进移动
        for v in G.vertices:
            current_gain = cut_weight(G, S, T)
            
            # 将v从当前侧移动到另一侧
            if v in S:
                S.remove(v)
                T.add(v)
            else:
                T.remove(v)
                S.add(v)
            
            new_gain = cut_weight(G, S, T)
            
            if new_gain <= current_gain:
                # 回退
                if v in S:
                    S.remove(v)
                    T.add(v)
                else:
                    T.remove(v)
                    S.add(v)
            else:
                improved = True
        
        if not improved:
            break
    
    return S, T

局部搜索的近似保证：

局部搜索算法通常不提供理论上的常数近似比保证，但实践中往往表现出色。为了获得理论保证，需要分析局部最优解的性质：

势函数分析：定义一个减少的”势”，证明局部最优隐含全局近似
参数化局部搜索：如 $k$ -交换局部搜索，保证局部最优解的质量
平滑分析：通过输入的平滑扰动证明平均情况性能

Example

对于旅行商问题，简单的2-opt局部搜索在实践中可以接近最优解，但理论下界较弱。通过增加邻域（3-opt、4-opt）可以提升近似质量，但计算成本也急剧增加。

2.6 割平面法（Cut Generation）与分支定界

割平面法是混合整数规划求解的核心技术，通过迭代添加约束（割）来缩小可行域与LP松弛之间的间隙。

割平面法的工作原理：

while True:
    solve LP relaxation
    if LP solution is integer:
        return LP solution  # 最优解
    else:
        add cutting plane  # 添加割，缩小间隙

有效不等式的类型：

分数割平面：打破分数顶点
整数割：排除当前分数解但保留整数解
组合割：基于问题结构的专用割
分离问题：找到最违反约束的割

def cutting_plane_knapsack(items, capacity):
    """
    背包问题的割平面法
    """
    # 初始LP：只包含变量边界 0 <= x_i <= 1
    lp = create_lp([0, 1], [0, 1])  # 简化的LP接口
    
    for iteration in range(max_iterations):
        solution = lp.solve()
        
        if is_integer(solution):
            return solution
        
        # 尝试分离有效不等式
        if capacity - sum(item.weight * solution[i] for i, item in enumerate(items)) < epsilon:
            # 使用贪婪方法构造1-范数球不等式
            add_valid_inequality(lp, generate_knapsack_cut(items, solution))

分支定界与割平面的结合：

现代MILP求解器（如CPLEX、Gurobi）将割平面法与分支定界深度结合：

节点选择策略：最佳优先、深度优先、最小冲突
分支变量选择：最强分数、最强伪成本、混合策略
割平面库：预先生成的常见割平面
用户割平面：基于问题知识的自定义割

3. 经典近似算法详解

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

3.1.1 问题定义

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

形式化：

最小化 ∣ C ∣ s.t. \forall (u, v) \in E : u \in C \lor v \in C

计算复杂性：

精确求解： $O (1.2 2^{n})$ （使用局部搜索与剪枝的最新算法）
近似求解：存在简单的2-近似算法
难度定位：NP完全问题，常数近似是APX完全

顶点覆盖的整数规划形式：

min v \in V \sum x_{v} s.t. x_{u} + x_{v} \geq 1, \forall (u, v) \in E, x_{v} \in {0, 1}, \forall v \in V

对应的LP松弛为将 $x_{v} \in {0, 1}$ 替换为 $0 \leq x_{v} \leq 1$ 。

3.1.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 ∣ = 2 k$ （每个顶点覆盖最多贡献2个端点）

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

∣ OPT ∣ \geq k

因此：

\frac{∣ C ∣}{∣ OPT ∣} \leq \frac{2 k}{k} = 2

证毕。

3.1.3 顶点覆盖LP舍入的2-近似

def vertex_cover_lp_rounding(G, epsilon=0.5):
    """
    基于LP舍入的确定性2-近似算法
    """
    # 构建顶点覆盖的LP松弛
    # min sum(x_v) s.t. x_u + x_v >= 1 for all (u,v) in E, 0 <= x_v <= 1
    
    # 使用专门的对偶方法求解（避免通用LP求解器）
    # 这里使用Bar-Yehuda-Even算法
    
    # 求解LP并获取分数解
    x = solve_vc_lp_special(G)
    
    # 确定性舍入
    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

3.1.4 Bar-Yehuda-Even算法：基于代价共享的1/2-近似

Bar-Yehuda和Even于1981年提出了一个更精细的算法，利用对偶性达到1/2-近似（对于最小化问题，1/2-近似意味着解最多是最优解的2倍，这是相同的近似比但算法更精妙）：

def bar_yehuda_even(G):
    """
    Bar-Yehuda-Even算法的伪代码描述
    
    核心思想：利用LP对偶增加"单位成本覆盖元素数"
    """
    # 初始化
    covered = set()
    cover = set()
    pi = {v: 0 for v in G.vertices}  # 对偶变量
    
    while len(covered) < len(G.edges):
        # 增加未被覆盖边的对偶值
        for e in G.edges - covered:
            pi[e] += 1
        
        # 找到满足pi约束紧绑的顶点
        for v in G.vertices:
            # 计算 v 关联边的对偶和
            sum_pi = sum(pi[(u,v)] for u in G.neighbors(v))
            
            if sum_pi >= 1 and v not in cover:
                # 将 v 加入覆盖集
                cover.add(v)
                
                # 更新被覆盖的边
                for e in G.incident_edges(v):
                    covered.add(e)
    
    return cover

Example

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

3.2 旅行商问题的近似

3.2.1 问题的计算复杂性

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

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

度量TSP的三角不等式保证：

对于度量TSP，权重函数 $w : E \to R^{+}$ 满足：

w (u, v) \leq w (u, x) + w (x, v), \forall u, v, x \in V

这个条件保证”绕路”不会比”直连”更短，是许多近似技术成立的前提。

3.2.2 度量TSP的2-近似

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

def metric_tsp_2_approx(G, w):
    """
    度量TSP的2-近似算法
    
    时间复杂度: O(n^2 log n) 使用Prim + O(n) 的欧拉回路构造
    近似比: 2
    """
    # 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 \leq OPT$

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

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

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

综合：

A L G \leq 2 \cdot MST \leq 2 \cdot OPT

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

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

算法步骤：

def christofides_tsp(G, w):
    """
    Christofides算法的详细实现
    时间复杂度: O(n^3) - 主要开销在最小完美匹配
    近似比: 3/2
    
    核心洞察：MST的奇度数顶点需要通过匹配添加边来形成欧拉图
    """
    # Step 1: 计算最小生成树 T
    T = mst_prim(G, w)
    
    # Step 2: 找到 T 中奇度数的顶点集合 O
    O = [v for v in G.vertices if degree_in_T(v) % 2 == 1]
    
    # O 总是有偶数个顶点（握手定理）
    # |O| >= 2, 通常远小于 |V|
    
    # Step 3: 在 O 诱导的子图上找最小完美匹配 M
    # 构建 O 的完全图，权重为原图中的最短路距离
    induced_subgraph = G.induced_subgraph(O)
    shortest_paths = all_pairs_shortest_path(induced_subgraph, w)
    
    # 最小完美匹配（可以用Blossom算法在 O(|O|^3) 内求解）
    M = min_weight_perfect_matching(induced_subgraph, shortest_paths)
    
    # Step 4: 合并 T 和 M，得到欧拉图 H = T ∪ M
    H = Graph(T.edges + M.edges)
    # H 中所有顶点度数变为偶数
    
    # Step 5: 找 H 的欧拉回路
    euler_tour = find_euler_tour(H)
    
    # Step 6: 抄近路得到哈密顿回路
    hamiltonian = shortcut_euler_tour(euler_tour, w)
    
    return hamiltonian

1.5-近似证明：

引理1（MST性质）： $w (T) \leq w (OPT)$

引理2（匹配性质）：对于奇度数顶点集合 $O$ ，存在一个完美匹配 $M$ 使得 $w (M) \leq w (OPT) /2$ 。

证明思路：将最优TSP回路去掉一条边得到生成树 $T^{*}$ ， $T^{*}$ 中 $O$ 的顶点度数为奇数。在 $O$ 上， $T^{*}$ 形成若干条不相交的路径。通过配对这些路径的端点，可以构造一个匹配，其权重不超过 $T^{*}$ 权重的一半。

引理3（抄近路不增加权重）：由于三角不等式，抄近路后的回路权重不超过原始欧拉回路权重。

综合：

w (A L G) \leq w (T) + w (M) \leq w (OPT) + \frac{w ( OPT )}{2} = \frac{3}{2} w (OPT)

Important

Christofides算法在1976年提出后，保持了度量TSP最佳常近似比的记录长达近50年。直到2024年，Karlin、Kenyon和Yudelson等人提出了新的分析技术，将最佳可达近似比略微改进为 $1.5 - ϵ$ 的某个小 $ϵ$ ，但非常接近 3/2。

3.2.4 一般TSP的不可近似性

对于不满足三角不等式的一般TSP，近似难度急剧增加：

定理（Sahni-Gonzalez 1974）：若 $P \neq = NP$ ，则一般TSP不存在常数近似比的多项式时间近似算法。

更强的不可近似性结果：

若NP ≠ P，即使对于极大度约束的图（如最大度3），一般TSP的近似也是困难的。Lagrange松弛技术（将度约束转化为惩罚项）在实践中有效，但理论上难以给出有意义的界。

3.3 集合覆盖问题

3.3.1 问题定义

集合覆盖（Set Cover）问题：给定元素集合 $U$ 和若干子集族 $S = {S_{1}, S_{2}, ..., S_{m}}$ ，每子集有代价 $c_{i}$ ，找到最小代价的子集族覆盖所有元素。

形式化：

最小化 i : S_{i} \in C \sum c_{i} s.t. S_{i} \in C ⋃ S_{i} = U

应用场景：

设施选址问题
药物研发中的分子筛选
信息检索中的文档聚类
网络覆盖优化

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

def set_cover_greedy(U, S, costs):
    """
    集合覆盖的贪婪算法
    
    时间复杂度: O(|U| * |S|) - 朴素实现
                 O((|U| + |S|) * log(|U|)) - 使用优先队列优化
    近似比: H_n = O(log n)，其中 n = |U|
    """
    import heapq
    
    C = ∅                    # 选中的集合
    uncovered = U.copy()     # 未覆盖元素
    
    # 计算每个元素被包含的集合
    element_to_sets = {}
    for i, s in enumerate(S):
        for e in s:
            if e not in element_to_sets:
                element_to_sets[e] = []
            element_to_sets[e].append(i)
    
    # 优先队列：(cost_per_element, set_id, remaining_elements)
    # 使用元组排序：先按性价比，再按ID
    heap = []
    for i, s in enumerate(S):
        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
        
        # 更新已选集合的性价比
        remaining = s.intersection(uncovered)
        if remaining:
            new_ratio = costs[i] / len(remaining) if remaining else float('inf')
            heapq.heappush(heap, (new_ratio, i, remaining))
    
    return [S[i] for i in C]

对数近似比证明：

设贪婪算法选择 $k$ 个集合： $S_{1}, S_{2}, ..., S_{k}$ 。

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

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

n_{i + 1} \leq n_{i} (1 - \frac{1}{k})

经过 $k$ 步后： $n_{k} \leq n_{0} (1 - 1/ k)^{k} < 1$

因此 $k \leq H_{n} = ln n + O (1)$ 。

最优解满足 $OPT \geq max cost$ ，故：

\frac{A L G}{OPT} \leq \frac{k \cdot max cost}{OPT} \leq H_{n}

3.3.3 加权集合覆盖的原始-对偶算法

def weighted_set_cover_primal_dual(U, S_sets, costs):
    """
    加权集合覆盖的原始-对偶算法
    近似比: O(log n)
    """
    # 初始化
    price = {e: 0 for e in U}  # 元素价格
    selected = set()          # 选中的集合
    covered = set()           # 已覆盖元素
    
    while covered != U:
        # 增加未覆盖元素的价格
        delta = min(costs[s] / |s - covered| for s in range(len(S_sets)) if s not in selected)
        
        for e in U - covered:
            price[e] += delta
        
        # 找到紧绑的集合
        for i, s in enumerate(S_sets):
            if i not in selected:
                contribution = sum(price[e] for e in s)
                if contribution >= costs[i] * (1 - 1/(len(U)+1)):
                    selected.add(i)
                    covered.update(s)
    
    return [S_sets[i] for i in selected]

Warning

集合覆盖不能有常数近似比（除非 $P = NP$ ），因为问题本身是APX难。实际上，在NP ≠ P的前提下， $o (lo g n)$ -近似也是不可能的（Raz-Safra定理）。

3.4 负载均衡问题的近似

3.4.1 问题定义

负载均衡（Load Balancing）问题有多种变体，最经典的是最小化最大完工时间（Makespan Minimization）：

给定 $m$ 台机器和 $n$ 个作业
每个作业 $j$ 有处理时间 $p_{j}$
将作业分配到机器上，最小化最大机器的负载

问题形式化：

min i max j \in S_{i} \sum p_{j} s.t. S_{1}, ..., S_{m} 是对 {1, ..., n} 的划分

3.4.2 List Scheduling：2-近似

Graham于1966年提出的List Scheduling算法：

def list_scheduling(jobs, m):
    """
    List Scheduling算法
    
    时间复杂度: O(n log m) - 每次分配需要找最小负载机器
    近似比: 2 - 1/m
    
    策略：按任意顺序（贪婪选择最闲机器）分配作业
    """
    loads = [0] * m  # 每台机器的当前负载
    
    for job in jobs:
        # 找到负载最小的机器
        min_machine = loads.index(min(loads))
        loads[min_machine] += job
    
    return max(loads)

2-近似证明：

设 $L^{*}$ 是最优makespan。

下界1： $L^{*} \geq max_{j} p_{j}$ （单个最长作业）
下界2： $L^{*} \geq \frac{1}{m} \sum_{j} p_{j}$ （平均负载）

考虑任意机器 $i$ ，其最终负载 $L_{i}$ 由两部分组成：

最后分配的作业 $j^{*}$ ，有 $p_{j^{*}} \leq L^{*}$
其他作业，总和 $\leq L^{*}$

因此 $L_{i} \leq 2 L^{*}$ ，即 $A L G \leq 2 \cdot OPT$ 。

3.4.3 LPT算法：更好的4/3-近似

Longest Processing Time First（LPT）按作业大小降序排列后再分配：

def lpt_scheduler(jobs, m):
    """
    LPT算法
    
    时间复杂度: O(n log n) - 排序
    近似比: 4/3 - 1/(3m)
    
    核心洞察：先处理大作业能减少"尾部"波动
    """
    # 按处理时间降序排列
    sorted_jobs = sorted(jobs, reverse=True)
    
    loads = [0] * m
    
    for job in sorted_jobs:
        min_machine = loads.index(min(loads))
        loads[min_machine] += job
    
    return max(loads)

4/3-近似证明（概要）：

设 $L^{*}$ 是最优值。考虑最后一个被分配的作业 $j$ 。

若 $j$ 的处理时间 $\leq L^{*} /3$ ，则算法性能良好
若 $j$ 的处理时间 $> L^{*} /3$ ，则最多只有 $2 m$ 个这样的作业

通过详细的界限分析可以得到 $A L G \leq (4/3 - 1/ (3 m)) \cdot OPT$ 。

Example

考虑 $m = 2$ 台机器，作业大小为 $[100, 100, 1, 1, 1, 1]$ 。LPT算法先分配两个100，再分配四个1，最终makespan = 102。LPT给出2+4=6分配到两台机器上为3+3=6，最优解也是6，比值接近1。

4. PTAS与FPTAS的构造技术

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

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

LPT（Longest Processing Time First） 算法：

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

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

PTAS for Scheduling（Hochbaum-Shmoys算法）：

def makespan_ptas(jobs, m, epsilon):
    """
    调度问题的PTAS
    
    时间复杂度: O(n^{O(1/epsilon)}) - 依赖于epsilon的多项式
    近似比: (1 + epsilon)
    
    核心思想：大作业"精确"处理，小作业用贪婪处理
    """
    n = len(jobs)
    
    # 定义阈值：处理时间大于T的为大作业
    T = epsilon * optimal_makespan_lower_bound(jobs, m)
    
    # 1. 识别大作业和小作业
    big_jobs = [j for j in jobs if j > T]
    small_jobs = [j for j in jobs if j <= T]
    
    # 2. 大作业数量有限：最多 n * epsilon 个
    # 使用分支定界枚举大作业的分配
    if len(big_jobs) <= 2 * m / epsilon:
        # 枚举所有分配方式（指数，但参数化于 m/epsilon）
        best_schedule = enumerate_big_jobs(big_jobs, m)
    else:
        # 大作业太多，使用随机化
        best_schedule = randomized_partition(big_jobs, m)
    
    # 3. 小作业贪婪分配到最小负载机器
    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)

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

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

def knapsack_fptas(items, W, epsilon):
    """
    背包问题的FPTAS
    
    时间复杂度: O(n^2 / epsilon) 朴素实现
                O(n^3 / epsilon) 优化版本
    近似比: (1 + epsilon)
    
    核心思想：
    1. 伪多项式DP可精确求解，但时间依赖权重和
    2. 缩放价值函数，将问题"压"到多项式规模
    3. 缩放后的DP仍是伪多项式，但规模可控
    """
    n = len(items)
    
    # Step 1: 计算价值上界
    V = sum(item.value for item in items)
    
    # Step 2: 确定缩放因子
    # 目标：使DP规模从 O(n*V) 降到 O(n^2/epsilon)
    K = epsilon * V / n
    
    if K == 0:
        return greedy_knapsack(items, W)  # 退化情况
    
    # Step 3: 缩放每个物品的价值
    scaled_items = []
    for item in items:
        scaled_value = int(item.value / K)
        scaled_items.append(Item(scaled_value, item.weight))
    
    # Step 4: 在缩放空间上运行伪多项式DP
    # 新价值上界: n * max_scaled_value ≈ n * V / K = n^2 / epsilon
    max_scaled_value = max(item.scaled_value for item in scaled_items)
    total_scaled = sum(item.scaled_value for item in scaled_items)
    
    # DP: dp[j][v] = 是否可以用前j个物品达到价值v
    dp = knapsack_dp(scaled_items, W, total_scaled)
    
    # Step 5: 反缩放得到原始解
    best_value = 0
    best_items = []
    
    for v in range(total_scaled + 1):
        if dp[n][v]:
            # v 是可达的最大缩放价值
            pass
    
    return reconstruct_solution(dp, scaled_items, K)

时间复杂度分析：

原始伪多项式DP： $O (n \cdot V)$
缩放后DP： $O (n \cdot V / K) = O (n \cdot V \cdot n / (ϵ \cdot V)) = O (n^{2} / ϵ)$
实际使用更精细的分析： $O (n^{3} / ϵ^{2})$ 在某些实现中

FPTAS存在性的深层含义：

FPTAS只对”价值可缩放”的问题有效。背包问题的关键在于价值是整数且可以线性缩放。

Warning

并非所有伪多项式时间可解的问题都有FPTAS。例如，子集和问题在数值上（位长度）是伪多项式可解的，但没有FPTAS（除非 $P = NP$ ）。

5. 随机近似算法

5.1 概率分析框架

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

一个随机化算法 $A$ 是 $α$ -近似，如果
$E [A L G (I)] \leq α \cdot OPT (I)$

随机近似 vs 确定性近似的比较：

特征	确定性近似	随机近似
保证强度	对所有实例	对期望值
最坏情况	始终受保护	可能很差
设计难度	通常更难	更灵活
典型技术	LP舍入	概率方法

5.2 随机化顶点覆盖

def randomized_vertex_cover(G):
    """
    顶点覆盖的随机化算法
    
    期望近似比: 2
    最坏情况: 可能达到 O(log n) * OPT
    """
    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

期望分析：

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

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

修复操作只在两端都未预选时执行，期望添加1个顶点。

每条边 $e$ 在期望中”消耗” $1/4$ 个修复顶点，加上 $1/2$ 的预选贡献，总期望代价与 $OPT$ 的比值为常数。

5.3 随机化平面图着色

平面图着色问题是NP完全的，但四色定理保证了4色即可着色。随机算法可以达到 $5/3$ -近似：

def randomized_planar_coloring(G):
    """
    平面图着色的随机近似算法
    期望使用 6 × (3/4) = 4.5 色（相对于4色的近似比 9/8）
    
    更精细的分析可以达到 4.5 色
    """
    import random
    
    colors = {}
    vertices = list(G.vertices)
    
    # 随机顺序处理
    random.shuffle(vertices)
    
    for v in vertices:
        # 获取邻居已使用的颜色
        used_colors = {colors[u] for u in G.neighbors(v) if u in colors}
        
        # 选择最小的未使用颜色
        color = 0
        while color in used_colors:
            color += 1
        
        colors[v] = color
    
    return colors

6. 近似算法的局限性

6.1 APX完全性

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

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

APX完全问题的判定：

若问题A是APX完全的，且问题A可以L-归约到问题B，则B也是APX完全的。

6.2 PCP定理与硬度

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

NP = PCP (lo g n, O (1))

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

Håstad的3-bit PCP：

对于Max-3SAT：

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

6.3 不可近似性的层级

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

7. 近似算法在AI与机器学习中的应用

7.1 神经网络剪枝

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

def neural_network_pruning(model, k, val_data):
    """
    网络剪枝的贪婪算法
    目标：删除k个参数，最大化保留的验证集性能
    
    基于子模函数：神经网络的损失函数通常是次模的
    """
    remaining_params = set(range(len(model.params)))
    selected = set()
    
    # 定义效用函数：保留selected参数后的验证准确率
    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  # 被剪枝的参数

次模性保证：在某些条件下，神经网络的损失函数满足次模性，贪婪算法给出 $(1 - 1/ e)$ -近似保证。

7.2 图神经网络的节点采样

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

def graph_sampling(gcn_layer, node_features, neighbors, num_samples):
    """
    图卷积的采样近似
    
    原始GCN: h_v^{(l+1)} = σ(W^{(l)} · sum_{u in N(v)} h_u^{(l)} / |N(v)|)
    采样版本: 只采样部分邻居进行近似
    """
    import random
    
    aggregated = {}
    
    for node in node_features:
        neighbor_list = list(neighbors[node])
        
        if len(neighbor_list) <= num_samples:
            sampled = neighbor_list
        else:
            sampled = random.sample(neighbor_list, num_samples)
        
        # 归一化因子考虑采样
        norm = len(neighbor_list) / num_samples if len(neighbor_list) > num_samples else 1
        
        # 聚合采样邻居的特征
        aggregated[node] = norm * sum(node_features[u] for u in sampled)
    
    # 应用线性变换和非线性
    return apply_layer(gcn_layer, aggregated)

7.3 强化学习的函数近似

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

def fitted_q_iteration(states, actions, rewards, next_states, 
                       gamma, num_iterations, basis_functions):
    """
    拟合Q迭代：强化学习的函数近似方法
    
    可以视为在连续状态空间上的近似优化
    """
    # 构建基函数（特征映射）
    phi = lambda s, a: basis_functions(s, a)
    
    # 初始化Q函数参数
    theta = initialize_parameters()
    
    for iteration in range(num_iterations):
        # 采样转移
        for s, a, r, s_prime in transition_samples:
            # 目标值：TD目标
            target = r + gamma * max(Q_network(theta, s_prime, a_prime) 
                                   for a_prime in actions)
            
            # 更新参数使Q(s,a)逼近target
            # 最小化 (Q(s,a; theta) - target)^2
            theta = update(theta, phi(s,a), target)
    
    return theta

7.4 大规模聚类的近似K-means

def kmeans_plus_plus_plus(data, k, num_init=10):
    """
    K-means++的改进版本：更小的近似比
    
    原始K-means++: O(log k)-近似
    改进版本: O(1)-近似（使用多次初始化）
    """
    import random
    import numpy as np
    
    best_centers = None
    best_cost = float('inf')
    
    for _ in range(num_init):
        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)
        
        # 评估当前初始化
        cost = evaluate_kmeans_cost(data, centers)
        
        if cost < best_cost:
            best_cost = cost
            best_centers = centers
    
    return best_centers

7.5 近似推理与变分方法

概率图模型中的近似推断（如变分推断、信念传播）可以理解为优化问题上的近似算法：

def mean_field_variational_inference(observations, model, num_iterations=100):
    """
    均值场变分推断
    
    目标：近似后验分布 P(Z|X) ≈ Q(Z) = ∏_i Q_i(Z_i)
    方法：坐标上升法，迭代优化每个因子
    """
    # 初始化变分分布
    variational_params = initialize_variational_params(model)
    
    for iteration in range(num_iterations):
        for i in model.latent_variables:
            # 固定其他因子，优化 Q_i
            # Q_i(z_i) ∝ exp(E_{~i}[log P(X, Z)])
            
            expected_sufficient_stats = compute_expected_stats(
                variational_params, i, observations
            )
            
            # 更新变分参数
            variational_params[i] = update_factor(
                expected_sufficient_stats, model, i
            )
    
    return variational_params

8. 现代近似算法前沿

8.1 容量受限设施选址的近似

设施选址问题（Facility Location）结合了位置优化与覆盖约束：

def facility_location_dualfitting(facilities, clients, opening_cost, service_cost):
    """
    设施选址的对偶拟合算法
    近似比: O(log n)
    
    问题：
    - 开启设施 i 成本: f_i
    - 客户 j 到设施 i 服务成本: c_ij
    - 目标: 最小化开启成本 + 服务成本
    """
    # 构建线性规划及其对偶
    # LP: min sum(f_i y_i) + sum(c_ij x_ij)
    #     s.t. sum_i x_ij = 1, x_ij <= y_i, x,y >= 0
    
    # 对偶: max sum(alpha_j)
    #       s.t. alpha_j - beta_ij <= c_ij, beta_ij >= 0
    
    # 使用对偶拟合策略
    alpha = [0] * len(clients)
    selected_facilities = []
    assigned_clients = {}
    
    # 迭代增加对偶变量
    while len(assigned_clients) < len(clients):
        # 找到当前最"贵"的未分配客户端
        unassigned = [j for j in range(len(clients)) if j not in assigned_clients]
        
        for j in unassigned:
            # 增加 alpha_j 直到某个设施的约束紧绑
            min_ratio = min((c_ij[j] for i in range(len(facilities))))
            alpha[j] += min_ratio
        
        # 选择紧绑的设施
        for i, f in enumerate(facilities):
            if sum(alpha[j] for j in unassigned if j not in assigned_clients) >= opening_cost[i]:
                selected_facilities.append(i)
    
    return selected_facilities

8.2 稀疏恢复与压缩感知

稀疏恢复问题（Sparse Recovery）可以用凸优化近似求解：

def compressive_sensing_recovery(y, A, s, epsilon=1e-5):
    """
    压缩感知的稀疏恢复
    问题: min ||x||_1 s.t. ||Ax - y||_2 <= epsilon
    
    L1范数促进稀疏性
    可以用内点法或贪婪算法求解
    """
    from scipy.optimize import linprog
    import numpy as np
    
    n = A.shape[1]
    
    # 转化为线性规划
    # min sum(t_i) s.t. -t <= x <= t, Ax = y
    c = np.concatenate([np.zeros(n), np.ones(n)])
    
    A_eq = A
    b_eq = y
    
    A_ub = np.vstack([
        np.hstack([np.eye(n), -np.eye(n)]),   # x - t <= 0
        np.hstack([-np.eye(n), -np.eye(n)])   # -x - t <= 0
    ])
    b_ub = np.zeros(2 * n)
    
    result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq)
    
    return result.x[:n]  # 返回稀疏解

8.3 张量分解的近似

高阶张量分解用于推荐系统和信号处理：

def tucker_decomposition(tensor, ranks, num_iterations=100):
    """
    Tucker分解的交替最小二乘（ALS）算法
    
    核心思想：用低秩张量近似原始张量
    X ≈ G ×_1 A ×_2 B ×_3 C
    
    其中 G 是核心张量，A,B,C 是因子矩阵
    """
    import numpy as np
    from scipy import sparse
    
    dims = tensor.shape
    num_modes = len(dims)
    
    # 初始化因子矩阵
    factors = [np.random.randn(dims[i], ranks[i]) for i in range(num_modes)]
    
    for iteration in range(num_iterations):
        for mode in range(num_modes):
            # 固定其他因子，优化当前因子
            # 使用Khatri-Rao积进行高效计算
            
            # 计算投影
            projection = tensor
            
            # 更新因子
            factors[mode] = update_factor_als(projection, factors, mode, ranks)
    
    return factors

9. 近似算法的实践指南

9.1 选择近似策略的决策树

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

9.2 近似比的验证方法

def verify_approximation_ratio(algorithm, problem_instances, 
                                optimal_values=None, num_samples=1000):
    """
    通过实验验证算法的近似比
    
    如果没有最优值，使用下界（如LP松弛值）
    """
    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)
    }

9.3 近似算法的效率-精度权衡

def approximate_knapsack_tradeoff(items, capacity):
    """
    展示效率-精度权衡的多种算法
    """
    algorithms = {
        # 精确算法（效率低）
        'dynamic_programming': {
            'algorithm': lambda: knapsack_dp(items, capacity),
            'time': 'O(nW)',
            'quality': '精确'
        },
        
        # FPTAS（效率取决于精度）
        'fptas_0.1': {
            'algorithm': lambda: knapsack_fptas(items, capacity, 0.1),
            'time': 'O(n^3 / 0.01)',
            'quality': '1.1-近似'
        },
        
        'fptas_0.01': {
            'algorithm': lambda: knapsack_fptas(items, capacity, 0.01),
            'time': 'O(n^3)',
            'quality': '1.01-近似'
        },
        
        # 贪婪算法（效率高，精度一般）
        'greedy_density': {
            'algorithm': lambda: greedy_by_density(items, capacity),
            'time': 'O(n log n)',
            'quality': '50% 近似'
        }
    }
    
    return algorithms

10. 近似算法的理论前沿与开放问题

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

核心问题：Christofides算法的3/2近似比是最优的吗？

已知结果：

下界：存在Ω(1.005…)-hardness（基于Unique Games猜想）
上界：3/2（Christofides, 1976）
间隙：约1.49倍

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

10.2 Unique Games猜想的近似推论

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

近似算法中的UGC应用：

最大切割：Goemans-Williamson的0.878近似是最优的（假设UGC）
Sparsest Cut： $O (lo g n)$ -近似是最优的
Vertex Cover：2-近似是最优的

10.3 半定规划的应用边界

Open Problem：对于某些问题（如3维匹配），半定规划是否比线性规划提供更强的松弛？

10.4 参数化近似算法

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

$k$ -团问题： $O (n^{1/2 + ϵ})$ 近似（固定参数近似）
$k$ -支配集： $O (lo g n)$ -近似在 $n$ 中， $O (1)$ 在 $k$ 中

11. 算法性能总结

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

参考来源

Vazirani, V. V. (2013). Approximation Algorithms. Springer.
Williamson, D. P., & Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press.
Christofides, N. (1976). Worst-case Analysis of a New Heuristic for the Travelling Salesman Problem. Technical Report.
Håstad, J. (1999). Some Optimal Inapproximability Results. JACM.
Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach.
Goemans, M. X., & Williamson, D. P. (1995). Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. JACM.
Feige, U. (1998). A Threshold of ln n for Approximating Set Cover. JACM.
Bar-Yehuda, R., & Even, S. (1981). A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problem. J. Algorithms.
Hochbaum, D. S., & Shmoys, D. B. (1987). Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results. JACM.
Sahni, S., & Gonzalez, T. (1976). P-Complete Approximation Problems. JACM.

人工智能知识库

探索

近似算法详解

近似算法详解

关键词速览

摘要

1. 近似算法的理论基础

1.1 近似比的形式定义

1.2 近似方案的层次结构

1.3 近似难度的层级：APX与PTAS层级

1.4 近似比与计算复杂度的深层联系

2. 近似算法的六大核心技术

2.1 贪心法（Greedy Method）

2.2 线性规划松弛与舍入（LP Relaxation and Rounding）

2.3 半定规划松弛（Semidefinite Programming Relaxation）

2.4 原始-对偶方法（Primal-Dual Method）

2.5 局部搜索（Local Search）

2.6 割平面法（Cut Generation）与分支定界

3. 经典近似算法详解

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

3.1.1 问题定义

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

3.1.3 顶点覆盖LP舍入的2-近似

3.1.4 Bar-Yehuda-Even算法：基于代价共享的1/2-近似

3.2 旅行商问题的近似

3.2.1 问题的计算复杂性

3.2.2 度量TSP的2-近似

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

3.2.4 一般TSP的不可近似性

3.3 集合覆盖问题

3.3.1 问题定义

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

3.3.3 加权集合覆盖的原始-对偶算法

3.4 负载均衡问题的近似

3.4.1 问题定义

3.4.2 List Scheduling：2-近似

3.4.3 LPT算法：更好的4/3-近似

4. PTAS与FPTAS的构造技术

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

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

5. 随机近似算法

5.1 概率分析框架

5.2 随机化顶点覆盖

5.3 随机化平面图着色

6. 近似算法的局限性

6.1 APX完全性

6.2 PCP定理与硬度

6.3 不可近似性的层级

7. 近似算法在AI与机器学习中的应用

7.1 神经网络剪枝

7.2 图神经网络的节点采样

7.3 强化学习的函数近似

7.4 大规模聚类的近似K-means

7.5 近似推理与变分方法

8. 现代近似算法前沿

8.1 容量受限设施选址的近似

8.2 稀疏恢复与压缩感知

8.3 张量分解的近似

9. 近似算法的实践指南

9.1 选择近似策略的决策树

9.2 近似比的验证方法

9.3 近似算法的效率-精度权衡

10. 近似算法的理论前沿与开放问题

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

10.2 Unique Games猜想的近似推论

10.3 半定规划的应用边界

10.4 参数化近似算法

11. 算法性能总结

参考来源

相关文档

关系图谱

目录

反向链接