Chap9 近似算法

返回：0400 算法设计与分析总目录 · 上一章：0408 Chap8 NP 与计算困难性 · 下一章：0410 Chap10 局部搜索

1、学习目标

当问题很可能不存在通用多项式精确算法时，近似算法尝试在可接受时间内给出有保证的近似解。

模块	要掌握的内容
近似比	解的质量保证
下界	用来比较算法结果有多差
负载均衡	list scheduling
中心选择	farthest-first traversal
顶点覆盖	定价法、线性规划松弛
背包	FPTAS 直觉

2、近似比

最小化问题中，算法 A 的近似比为 α，表示：

cost(A) <= α * OPT

最大化问题中常写成：

value(A) >= OPT / α

其中 OPT 是最优解。近似算法的价值在于：即使不是最优，也知道离最优不会太远。

3、下界的重要性

很多近似证明不是直接知道 OPT，而是找一个容易计算的下界 LB：

LB <= OPT

如果能证明：

cost(A) <= α * LB

就有：

cost(A) <= α * OPT

所以近似算法证明常常围绕“找下界”展开。

4、负载均衡

问题：把 n 个任务分配到 m 台机器，使最大负载最小。

贪心策略：

每次把下一个任务分给当前负载最小的机器。

下界：

1. 最大任务时间：OPT >= max t_i
2. 平均负载：OPT >= sum(t_i) / m

该算法可证明有常数近似比。若先按任务时间从大到小排序，再做贪心，实际效果更好。

5、中心选择

问题：在一组点中选择 k 个中心，使每个点到最近中心的最大距离最小。

Farthest-first 策略：

1. 任取第一个中心。
2. 每次选择离当前中心集合最远的点作为新中心。
3. 直到选出 k 个中心。

这个算法有 2-近似保证。

直觉：如果某个点离所有已选中心都很远，它代表一个尚未覆盖好的区域。

6、顶点覆盖

顶点覆盖：给定无向图，选择尽量少的点，使每条边至少有一个端点被选。

简单 2-近似：

while 还有未覆盖边:
    取一条未覆盖边 (u, v)
    把 u 和 v 都加入解
    删除所有被 u 或 v 覆盖的边

证明：

1. 选出的边两两不共享端点。
2. 任意顶点覆盖至少要覆盖这些边，每条边至少选一个端点。
3. 算法每条边选两个端点。
4. 所以算法解大小至多 2 * OPT。

7、LP Rounding

把整数规划放松成线性规划：

x_v ∈ {0,1}

放松为：

0 <= x_v <= 1

对顶点覆盖：

min sum x_v
s.t. x_u + x_v >= 1, for each edge (u,v)

求得分数解后，采用舍入：

若 x_v >= 1/2，则选择 v。

因为每条边 x_u + x_v >= 1，至少有一个端点被舍入选中，因此得到合法顶点覆盖，并可证明 2-近似。

8、背包近似

0/1 背包有伪多项式 DP O(nW)，当 W 很大时不合适。

一种近似思路是对价值缩放：

1. 把价值按比例缩小并取整。
2. 对缩小后的价值做 DP。
3. 换取多项式时间和可控误差。

这类方案叫 FPTAS：

Fully Polynomial-Time Approximation Scheme

意思是时间对输入规模和 1/ε 都是多项式，并能得到 (1-ε) 级别的解。

9、近似算法设计套路

套路	说明
找下界	用平均值、最大值、松弛问题给 OPT 下界
贪心构造	快速得到一个可行解
松弛再舍入	先解容易的连续问题，再转成整数解
局部改进	从一个解出发不断优化
缩放	牺牲精度换时间

10、易错点

易错点	修正
只给启发式没有保证	近似算法要给近似比
用算法结果当下界	下界必须不超过 OPT
最小化和最大化近似比混淆	注意方向不同
顶点覆盖只选一端	简单 2-近似是一条边选两个端点
FPTAS 当成精确算法	它是可控误差的近似

11、复盘清单

检查项	状态
能定义最小化问题的近似比	待复盘
能为负载均衡写两个下界	待复盘
能解释中心选择的 farthest-first 思路	待复盘
能证明顶点覆盖 2-近似	待复盘
能说明 LP rounding 的基本流程	待复盘
能解释 FPTAS 的含义	待复盘