10 · 近似算法

← 返回课程目录
本文目录

本文最后更新于 2026年11月5日 晚上

北京大学信息科学技术学院
算法设计与分析(2026春)的课程笔记

第十章:近似算法

经过第九章的学习,我们知道许多组合优化问题对应的判定问题是NPC,在P=NP没被证明出的前提下,根本无法找到多项式时间内的最优算法
但我们显然又不能置之不理,摆烂到底,这些问题还是有许多现实意义的,所以我们退而求其次,找一个足够好的可行解,因此寻找近似算法就顺理成章

近似算法及其近似比

假设组合优化问题为Π\Pi,AA是一个多项式时间算法,如果对于Π\Pi的每一个实例II,算法AA都能输出II的一个可行解σ\sigma,那么我们就称AA为Π\Pi的近似算法
记作A(I)=c(σ)A(I)=c(\sigma),其中c(σ)c(\sigma)为σ\sigma的值
如果A(I)=OPT(I)A(I)=OPT(I)恒成立,即AA总是输出II最优解,则称AA是Π\Pi的最优化算法

当Π\Pi为最小化问题时,记rA(I)=A(I)OPT(I)r_A(I)=\frac{A(I)}{OPT(I)}
当Π\Pi为最大化问题时,记rA(I)=OPT(I)A(I)r_A(I)=\frac{OPT(I)}{A(I)}
如果对Π\Pi的每个实例II,都有rA(I)≤rr_A(I) \le r,则称近似算法近似比为rr,AA为r-近似算法
如果rr为常数,称AA具有常数比

显然r≥1r\ge 1,并且越接近1越好
对于NP难的组合优化问题,可以按照可近似性分为以下3类:

  • 对于任意小的ϵ>0\epsilon >0,存在(1+ϵ)(1+\epsilon)-近似算法,该问题为完全可近似的
  • 存在具有常数比的近似算法,该问题为可近似的
  • 只要P=NP不成立,就不存在具有常数比的近似算法,该问题为不可近似的

当然分类大前提是P≠NPP \neq NP
并且不可近似的算法并非没有近似算法,而是没有常数比近似算法,可能有近似比为$n,log n $的算法

下面我们看一个简单例子:最小顶点覆盖问题
任给G=<V,E>G=<V,E>,求GG顶点数最少的顶点覆盖
我们采用MVC近似算法:开始令V′V'为空集,任取一条边(u,v)(u,v),将u,vu,v加入V′V'并删去u,vu,v及其关联的边,重复上述过程直至所有的边都被删去为止,则V′V'即为所求
时间复杂度O(∣E∣)O(|E|)

近似比:
设∣V′∣=2k|V'|=2k,V′V'由kk条互不关联的边的端点组成,为了覆盖这kk条边需要kk个顶点从而OPT(I)≥kOPT(I) \ge k,因此
MVC(I)OPT(I)≤2kk=2\frac{MVC(I)}{OPT(I)} \le \frac{2k}{k} =2
当GG刚好由kk条互不关联的边构成时,取到等号
这表明MVC近似比不可能小于2,故MVC为2-近似算法

多机调度问题

任给有穷作业集AA,mm台相同机器,作业aa的处理时间为正整数t(a)t(a),每一项作业都可以在任意机器上处理
问如何把作业合理分配给机器,使得完成所有作业时间最短
即如何把AA划分为mm个不相交子集AiA_i,使得
max[Σa∈Ait(a)∣i=1,2,...,m]max[\Sigma_{a \in A_i}t(a)|i=1,2,...,m]最小

贪心法

定义负载为:分配给一台机器的作业 处理时间之和
我们采用G-MPS贪心:
按照输入顺序分配作业,把每一项作业都分配给当前负载最小的机器,如果当前负载最小的机器不止一台,则随机分配(或者就分给序号最小的也可)

上面是一个实例,可以看到这种贪心不一定最优

对于每一个有mm台机器的实例II
我们可以证明:G−MPS(I)≤(2−1m)OPT(I)G-MPS(I) \le (2-\frac{1}{m})OPT(I)

显然有OPT(I)≥1mΣa∈At(a)OPT(I) \ge \frac{1}{m} \Sigma_{a \in A}t(a)
最大负载不小于平均负载
OPT(I)≥max⁡a∈At(a)OPT(I) \ge \max_{a \in A}t(a)
最大负载不小于单个任务负载

假设机器MM负载最大,为t(M)t(M),bb为最后被分配给MM的作业,根据算法,在分配bb时MM负载最小,最小负载不大于平均负载,我们有
t(M)−t(b)≤1m(Σa∈At(a)−t(b))t(M)-t(b) \le \frac{1}{m}(\Sigma_{a \in A}t(a)-t(b))
LHS为该机器在bb之前的负载,RHS为除去bb剩下作业时间的平均值,也即在分配bb之前所有机器平均负载
于是G−MPS(I)=t(M)G-MPS(I)=t(M)
≤1m(Σa∈At(a)−t(b))+t(b)\le \frac{1}{m}(\Sigma_{a \in A}t(a)-t(b))+t(b)
=1mΣa∈At(a)+(1−1m)t(b)=\frac{1}{m}\Sigma_{a \in A}t(a)+(1-\frac{1}{m})t(b)
≤OPT(I)+(1−1m)OPT(I)\le OPT(I)+(1-\frac{1}{m})OPT(I)
=(2−1m)OPT(I)=(2-\frac{1}{m})OPT(I)
得证

上面是一个取等的实例,故G-MPS也是2-近似算法

贪心法的改进

递降贪心法DG-MPS:先对数据按照处理时间由大到小进行排序,再运用G-MPS
增加了排序时间O(nlogn)O(nlogn),依旧是多项式算法

对于每一个有mm台机器的实例II
我们可以证明:DG−MPS(I)≤(32−12m)OPT(I)DG-MPS(I) \le (\frac{3}{2}-\frac{1}{2m})OPT(I)

假设作业处理时间由大到小进行排序之后为a1,a2,...,ana_1,a_2,...,a_n,仍然假设负载最大的机器为MM,最后分配给MM的机器为aia_i
假如MM只有一个作业,i=1i=1,必为最优解
否则MM有大于等于两个作业,则i≥m+1i \ge m+1,从而OPT(I)≥2t(am+1)OPT(I) \ge 2t(a_{m+1})
类似上面的证法,我们有:
DG−MPS(I)=t(M)≤1m(Σk=1nt(ak)−t(ai))+t(ai)DG-MPS(I)=t(M) \le \frac{1}{m}(\Sigma_{k=1}^{n}t(a_k)-t(a_i))+t(a_i)
=1mΣk=1nt(ak)+(1−1m)t(ai)=\frac{1}{m}\Sigma_{k=1}^{n}t(a_k)+(1-\frac{1}{m})t(a_i)
≤OPT(I)+(1−1m)⋅12OPT(I)\le OPT(I)+(1-\frac{1}{m})\cdot \frac{1}{2} OPT(I)
=(32−12m)OPT(I)=(\frac{3}{2}-\frac{1}{2m})OPT(I)

从而DG-MPS为32\frac{3}{2}-近似算法

货郎问题

本章中考虑的货郎问题默认满足三角不等式
即对于任意三个城市i,j,ki,j,k,他们之间距离满足d(i,j)+d(j,k)≥d(i,k)d(i,j)+d(j,k) \ge d(i,k)

最邻近法(NN)

从任意城市开始,每一步取 离当前城市最近的 尚未到过的城市 作为下一个城市,如果这样的城市不止一个,就任取一个,直至走遍所有城市回到出发点
我们可以证明NN(I)≤12(⌈logn⌉+1)OPT(I)NN(I) \le \frac{1}{2}(\lceil logn \rceil+1)OPT(I)
并且对于任意充分大的nn,存在满足三角不等式的nn个城市的实例II,使得
NN(I)>13(log(n+1)+43)OPT(I)NN(I) > \frac{1}{3}(log(n+1)+\frac{4}{3})OPT(I)
定理证明从略,该定理表明了NN法的近似比可以取到正无穷
因此无法实际应用

最小生成树法(MST)

首先求图的一棵最小生成树T,然后,沿着 T 走两遍得到图的一条欧拉回路,最后,顺着这条欧拉回路,跳过已走过的顶点,抄近路得到一条哈密顿回路
求最小生成树和欧拉回路都可以在多项式时间内完成,故算法是多项式时间的,下面是一个例子

对于所有满足三角不等式实例II,MST(I)<2OPT(I)MST(I) < 2OPT(I)
这是由于从HC中删去一条边就得到一棵生成树,故TT的权小于OPT(I)OPT(I),沿着TT走两遍的长度自然小于2OPT(I)2OPT(I),并且由于满足三角不等式,所以抄近道不会增加长度

故MST为2-近似算法,下面是一个取等实例

最小权匹配法(MM)

  • 求图的一棵最小生成树T
  • 记T所有奇数度顶点在原图中导出子图H,H有偶数个顶点
  • 求 H 的最小匹配 M
  • 把 M 加入 T 得到一个欧拉图,求这个欧拉图的欧拉回路;
  • 沿着这条欧拉回路,跳过已走过的顶点,抄近路得到一条哈密顿回路

求任意图最小权匹配的算法是多项式时间的,因此 MM 是多项式时间的

对于所有满足三角不等式实例II,MM(I)<32OPT(I)MM(I) < \frac{3}{2}OPT(I)
这是由于满足三角不等式,记H中最短HC为C,C的长度不超过原图中最短HC的长度OPT(I)OPT(I),沿着C隔一条边取一条边,得到H的一个匹配,总能使这个匹配的权不超过C长的一半,因此M的权不超过OPT(I)2\frac{OPT(I)}{2},又因为T的权小于OPT(I)OPT(I),所以求得欧拉回路的长小于3OPT(I)2\frac{3OPT(I)}{2},抄近路不会增加长度,得证

故MM为32\frac{3}{2}-近似算法,取等实例略去

货郎问题的难度

只要P≠NPP \neq NP,不满足三角不等式要求的货郎问题就是不可近似的
我们证明逆否命题:
若不然,假设近似算法为AA,近似比r≤Kr \le K,KK为正整数
任给图G=<V,E>G=<V,E>,如下构造实例IGI_G:
城市集VV,∣V∣=n|V|=n,每一对城市u,v∈Vu,v \in V的距离为
d(u,v)=1,if(u,v)∈E;Kn,elsed(u,v)=1,if (u,v) \in E;Kn,else

如果GG有HC,则OPT(IG)=n,A(IG)≤rOPT(IG)≤KnOPT(I_G)=n,A(I_G) \le rOPT(I_G) \le Kn
否则OPT(IG)≥Kn,A(IG)≥OPT(IG)>KnOPT(I_G) \ge Kn,A(I_G) \ge OPT(I_G) >Kn
故GG有HC   ⟺  A(IG)≤Kn\iff A(I_G) \le Kn

于是下面的算法可以判断GG是否有HC:

  • 对II构造货郎问题实例IGI_G
  • 对IGI_G运用近似算法AA
  • 如果A(IG)≤KnA(I_G) \le Kn则输出Yes,否则输出No

由于KK为固定常数,构造IGI_G可在O(N2)O(N^2)内完成,∣IG∣=O(n2)|I_G|=O(n^2)
AA是多项式时间,且AA对IGI_G可在nn的多项式时间内完成计算
从而上述算法为HC的多项式时间算法,又因为HC是NP完全,所以P=NP,得证

背包问题

任给nn件物品和一个背包,物品ii重量wiw_i,价值viv_i,i≤i≤ni \le i \le n,背包重量限制为BB,wi,vi,Bw_i,v_i,B均为正整数,问把哪些物品装入背包才能在不超过重量限制的条件下使价值最大
即求子集S∗⊆[1,2,...,n]S^{\ast} \subseteq [1,2,...,n]使得
Σi∈S∗vi=max[Σi∈Svi∣Σi∈Swi≤B,S⊆[1,2,...,n]]\Sigma_{i \in S^{\ast}}v_i = max[\Sigma_{i \in S }v_i | \Sigma_{i \in S }w_i \le B,S \subseteq [1,2,...,n]]

下面不妨设所有物品重量wi≤Bw_i \le B,否则将该物品排除在外即可

一个简单的贪心算法(G-KK)

  • 按单位重量价值从大到小排列物品 $\frac{v_1}{w_1} \ge \frac{v_2}{w_2} \ge … \ge \frac{v_n}{w_n} $
  • 顺序检查每一件物品,只要能装得下就装,设装入背包总价值VV
  • 求vk=max[vi∣i=1,2,...,n]v_k=max[v_i|i=1,2,...,n],若vk>Vv_k >V,则将背包里物品换成物品kk

设物品ll为第一件未装入背包的物品,由于按照单位重量价值从大到小排列物品,故
OPT(I)<G−KK(I)+vlOPT(I) <G-KK(I) +v_l
≤G−KK(I)+vmax\le G-KK(I)+v_{max}
≤2G−KK(I)\le 2G-KK(I)
故OPT(I)<2G−KK(I)OPT(I) <2G-KK(I),G-KK为2-近似算法

多项式时间近似算法(PTAS)

输入ϵ>0\epsilon >0,实例II

  • 令m=⌈1ϵ⌉m=\lceil \frac{1}{\epsilon} \rceil
  • 按单位重量价值从大到小排列物品 $\frac{v_1}{w_1} \ge \frac{v_2}{w_2} \ge … \ge \frac{v_n}{w_n} $
  • 对每一个t=1,2,...,mt=1,2,...,m和tt件物品,检查这tt件物品重量和,如果和不超过BB,则接着用G-KK把剩余物品装进背包
  • 比较得到的所有装法,取其中价值最大的作为近似解

核心思想:枚举前mm个关键物品,对剩余部分再用贪心

PTAS其实是一簇算法,对固定的ϵ>0\epsilon>0,PTAS为一个算法,记作PTASϵPTAS_{\epsilon}
定理:对每一个ϵ>0\epsilon>0的0-1背包实例II
OPT(I)<(1+ϵ)PTASϵ(I)OPT(I)<(1+\epsilon)PTAS_{\epsilon}(I)
且PTASϵPTAS_{\epsilon}时间复杂度为O(n1ϵ+2)O(n^{\frac{1}{\epsilon}+2})
证明从略,可知该算法是(1+ϵ)(1+\epsilon)-近似

伪多项式时间算法

其实就是我们最常用的dp
一开始我在想着为什么dp不是多项式时间算法,必须加上伪字
这里放一个deepseek的解释

完全多项式时间算法(FPTAS)

输入ϵ>0\epsilon>0,实例II

  • 令b=max[⌊vmax(1+1ϵ)n⌋,1]b=max[\lfloor \frac{v_{max}}{(1+\frac{1}{\epsilon})n}\rfloor,1]
  • 令vi′=⌈vib⌉,1≤i≤nv'_i=\lceil \frac{v_i}{b} \rceil,1\le i\le n,把所有viv_i换成vi′v'_i,记新实例为I′I'
  • 对I′I'应用算法AA得到解SS,把SS取为实例II的解

核心思想:把价值缩小,从而dp的状态数减少

则满足定理:
OPT(I)<(1+ϵ)FPTAS(I)OPT(I) <(1+\epsilon)FPTAS(I)
并且FPTAS时间复杂度为O(n3(1+1ϵ))O(n^3(1+\frac{1}{\epsilon})),证明从略

笔者按:这一章相比前两章来说还是简单了不少,没有太多抽象概念,主要就是数学推导和复杂度分析,不过笔者还是在分析背包问题时适当略去了一些证明过程……

近似算法
https://yjyxfcy.github.io/2026/05/27/sf3/
作者
Yjy
发布于
2026年5月27日
更新于
2026年11月5日
许可协议