【算法分析与设计】第27篇：近似算法设计：贪心近似与局部搜索

在第24篇中，我们借助线性规划松弛和随机化舍入，为集合覆盖问题给出了 O(log⁡n)O(logn) 的近似比。那套方法的威力在于通用性——只要能把问题写成整数规划，就有机会套用“先松弛后舍入”的流程。但它也有明显的软肋：线性规划求解本身有一定计算成本，舍入策略需要针对具体约束精细设计。本篇介绍的两种方法——贪心近似与局部搜索——则更为朴素，几乎不需要高等数学工具，却同样能在诸多NP困难问题上取得非平凡的近似保证。

一、贪心近似的设计逻辑

贪心策略的核心思想极为直观：在每一步，从所有可选动作中选择那个在当前状态下“边际收益最大”或“边际成本最小”的动作，永不反悔。这一策略在可精确求解的问题上（如最小生成树的Kruskal算法）之所以成立，是因为问题本身具备拟阵结构（第8篇）。但对于NP困难问题，贪心不再保证精确最优，却能以较低的计算代价给出有理论保证的近似解。

贪心近似算法的分析通常依赖一个核心不等式：算法在第 tt 步的边际成本，与剩余部分的最优解成本之间存在某种关联。通过累加这些边际成本，并将其与最优解的总成本比较，即可导出近似比。

二、集合覆盖的贪心近似

集合覆盖问题我们在第24篇中已形式化：全集 UU 含 nn 个元素，S={S1,…,Sm}S={S1​,…,Sm​} 是子集族，每个 SjSj​ 有成本 cjcj​，目标是用最小总成本覆盖所有元素。

贪心策略：每一步选择“单位成本覆盖最多未覆盖元素”的子集。即定义子集 SjSj​ 的成本效益为 cj∣Sj∩C∣∣Sj​∩C∣cj​​，其中 CC 为当前尚未被覆盖的元素集合。每轮选取成本效益最小的子集，将其加入解中并更新 CC，直到 C=∅C=∅。

近似比分析：设算法依次选出的子集为 Si1,Si2,…,SitSi1​​,Si2​​,…,Sit​​。考虑第 kk 步时，剩余未覆盖元素集为 CkCk​，算法选择了 SikSik​​。设最优解 OPTOPT 的总成本为 OPTOPT。关键观察是：最优解中的那些子集，在仅考虑 CkCk​ 中元素时，其总成本仍不超过 OPTOPT，且它们共同覆盖了 CkCk​。因此，必存在最优解中的某个子集 S∗S∗，其覆盖 CkCk​ 中元素的单位成本 ≤OPT∣Ck∣≤∣Ck​∣OPT​。贪心算法挑选了成本效益最优的子集，故：

cik∣Sik∩Ck∣≤OPT∣Ck∣∣Sik​​∩Ck​∣cik​​​≤∣Ck​∣OPT​

这给出了第 kk 步的边际成本不等式。将其改写为：

cik≤OPT⋅∣Sik∩Ck∣∣Ck∣cik​​≤OPT⋅∣Ck​∣∣Sik​​∩Ck​∣​

令 nk=∣Ck∣nk​=∣Ck​∣。从 n0=nn0​=n 开始，每步 nk=nk−1−∣Sik∩Ck−1∣nk​=nk−1​−∣Sik​​∩Ck−1​∣。对所有步求和：

∑cik≤OPT⋅∑knk−1−nknk−1≤OPT⋅∑k(1nk−1+1nk−1−1+⋯+1nk+1)∑cik​​≤OPT⋅k∑​nk−1​nk−1​−nk​​≤OPT⋅k∑​(nk−1​1​+nk−1​−11​+⋯+nk​+11​)

右侧括号内恰为从 nk+1nk​+1 到 nk−1nk−1​ 的调和级数部分和。将所有步累加，每个整数至多在一次“跨越”中出现，总和 ≤∑i=1n1i=Hn=Θ(log⁡n)≤∑i=1n​i1​=Hn​=Θ(logn)。因此总成本 ≤Hn⋅OPT=O(log⁡n)⋅OPT≤Hn​⋅OPT=O(logn)⋅OPT。

这就证明了贪心算法的 O(log⁡n)O(logn) 近似比。与第24篇的随机化舍入相比，这个证明完全不需要线性规划，仅依赖调和级数的放缩——但两者的近似比恰好相同，且都与问题匹配的下界一致。这种“不同路径、同一彼岸”的巧合，正是近似算法理论的美感所在。

三、局部搜索的基本范式

如果说贪心算法是“从零开始逐步构造”，那么局部搜索就是“从粗糙解出发逐步打磨”。局部搜索的通用框架如下：

1. 从某个初始可行解 SS 出发（可以是随机生成或贪心构造）。

2. 定义解的邻域N(S)N(S)，即通过某种局部修改能从 SS 得到的所有解的集合。

3. 在 N(S)N(S) 中寻找比 SS 更优的解。若存在，则移动到该解并重复步骤2；若不存在，则当前解为局部最优解，算法终止。

局部搜索的输出是局部最优解——在它的邻域内无更优者。真正的问题在于：局部最优解与全局最优解之间的差距有多大？近似比分析的核心，正是建立局部最优的“停滞条件”与全局最优的结构关系。

四、最大割问题的局部搜索分析

最大割问题：给定无向图 G=(V,E)G=(V,E)，将顶点划分为两个集合 AA 和 BB，使得跨越 AA 与 BB 的边数最大。该问题是NP困难的，且不存在任意接近1的近似比（Håstad基于PCP定理证明近似比下界约为 16/1716/17）。

局部搜索策略：从任意初始划分 (A,B)(A,B) 出发。邻域定义为“将单个顶点从一侧移到另一侧”所得到的新划分。若存在这样的移动使得割边数严格增加，则执行移动并继续搜索；否则终止。

近似比证明：算法终止时，(A,B)(A,B) 是局部最优划分。这意味着对任意顶点 vv，将其移到对面不会增加割边数。设 d(v)d(v) 为 vv 的度数，dcross(v)dcross​(v) 为 vv 在当前划分中跨越割的邻边数，dsame(v)dsame​(v) 为 vv 与同侧顶点的连边数。d(v)=dcross(v)+dsame(v)d(v)=dcross​(v)+dsame​(v)。

将 vv 移到对面后，原来跨越割的边变为同侧边（贡献- dcross(v)dcross​(v)），原来同侧的边变为跨越割的边（贡献+ dsame(v)dsame​(v)）。局部最优意味着 dsame(v)≤dcross(v)dsame​(v)≤dcross​(v)，即 dcross(v)≥d(v)/2dcross​(v)≥d(v)/2。

当前割的大小为 12∑v∈Vdcross(v)21​∑v∈V​dcross​(v)（每条跨割边被两端各计一次）。由局部最优条件：

ALG=12∑vdcross(v)≥12∑vd(v)2=∣E∣2ALG=21​v∑​dcross​(v)≥21​v∑​2d(v)​=2∣E∣​

而全局最大割不可能超过总边数 ∣E∣∣E∣，因此 ALG≥12OPTALG≥21​OPT。这个 1221​ 近似比证明极其简洁——仅用了度数的基本等式和局部最优的定义。

事实上，通过更精细的局部搜索（如允许同时移动两个顶点），可以将近似比提升至约 0.7960.796。而利用半定规划松弛的Goemans-Williamson算法更是达到了约 0.8780.878 的近似比——目前仍是最大割问题的最佳近似比，其是否可被超越是理论计算机科学的重要开放问题。

五、贪心与局部搜索的比较

贪心近似和局部搜索代表了近似算法设计的两种不同哲学。

贪心算法的优势在于构造快速——通常只需对元素做一次排序然后逐个决策，时间复杂度低，适合大规模数据和在线场景。其分析往往依赖某种“边际收益递减”或“调和级数”的组合放缩。但贪心分析通常只能证明一个固定的近似比，很难通过微调策略获得改进。

局部搜索的优势在于灵活可调——可以通过扩大邻域来获得更好的近似比，代价是每次迭代的搜索时间增加。其分析通常将局部最优条件转化为结构不等式，进而导出近似比。局部搜索的一个独特优势是实践中往往远超理论保证，因为初始解和邻域结构可以结合领域知识进行针对性设计。

两者的共同局限在于：对于某些问题，贪心或局部搜索的简单策略的近似比与问题的已知下界之间存在无法弥合的差距。此时需要引入更复杂的数学工具——如线性规划、半定规划、谱方法——才能获得更优的近似比。

六、总结与展望

贪心近似和局部搜索是近似算法设计师最朴素也最常用的两件工具。前者通过贪心选择逐步构造解，后者通过局部调整持续改进解。它们的近似比分析不需要高深的数学工具，却能在集合覆盖、最大割、设施选址、调度等众多NP困难问题上给出非平凡的保证。

然而，本文讨论的两个案例——集合覆盖的 O(log⁡n)O(logn) 和最大割的 1/21/2 ——揭示了简单策略的理论极限。对于集合覆盖，o(log⁡n)o(logn) 的近似比是不可能的；对于最大割，半定规划能将 1/21/2 推至 0.8780.878。这提醒我们，在某些问题上，要实现最优的近似比，必须诉诸更强的数学工具。

下一篇，我们将进入多项式时间近似方案（PTAS）的世界——对于那些“比较容易近似”的NP困难问题，如何通过精心构造的算法，对任意指定的 ε>0ε>0，在多项式时间内达到 (1+ε)(1+ε) 的近似比。背包问题的DP缩放与平面图上的PTAS构造，将为我们打开这扇精细近似的大门。