第11章-近似算法

2023/2/2DesignandAnalysisofAlgorithm1存在的问题迄今为止，所有的NP完全问题都还没有多项式时间算法回溯法与分支限界等算法可以相对有效地解决这类问题，但算法的时间性能无法保证近似算法放弃求最优解，而用近似最优解代替最优解，以换取算法设计上的简化和时间复杂性的降低。但有些问题不适合用近似算法求解，对这些问题求近似最优解几乎和求最优解一样难。第11章近似算法2023/2/2DesignandAnalysisofAlgorithm2近似算法的依据输入数据本身就是近似的，如测量数据很多问题的最优解，允许有一定程度的近似采用近似算法可以在很短的时间内得到问题的解（特别是与指数时间相比较）其思想是用近似最优解代替最优解，是在计算量和精确解间的一个折中近似算法性能的两个重要指标对于规模为n

的问题算法能在多项式时间内完成算法的近似解满足一定的精度，即近似最优解的近似程度11.1概述2023/2/2DesignandAnalysisofAlgorithm3近似算法的性能近似比若一个问题的最优值为c*，该问题的一个近似最优解的目标函数值为c，则近似算法的性能比可定义为： =在通常情况下，是问题输入规模n的一个函数ρ(n)，即：

≤ρ(n)11.1概述2023/2/2DesignandAnalysisofAlgorithm4与近似比率相关的问题对最小化问题，有：C≥C*对最大化问题，有：C≤C*近似算法C的近似比率ρ(n)总大于或等于1近似算法的近似比率越小，则算法的性能越好近似算法的近似比率越大，则算法的性能越差2023/2/2DesignandAnalysisofAlgorithm5近似算法的相对误差与相对误差界ε(n)

=

若对问题的输入规模n，有一函数ε(n)使得:

≤ε(n)

则称ε(n)为该近似算法的相对误差界。近似比ρ(n)与相对误差ε(n)间关系

ρ(n)与ε(n)之间显然有如下关系：

ε(n)≤ρ(n)-1

11.1概述2023/2/2DesignandAnalysisofAlgorithm6第11章近似算法11.1概

述

11.2图问题中的近似法11.3组合问题中的近似法*11.4

实验项目——TSP问题的近似法2023/2/2DesignandAnalysisofAlgorithm7第11章近似算法11.2.1顶点覆盖问题

11.2.2TSP问题2023/2/2DesignandAnalysisofAlgorithm811.2.1顶点覆盖问题

问题描述：无向图G=(V,E)的顶点覆盖问题：指是它的顶点集V的一个子集V’V，使得:若(u,v)是G的一条边，则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数

|V’|。

VertexSetapproxVertexCover(Graphg){cset=；

e1=g.e；

while(e1!=){

从e1中任取一条边(u,v)；

cset=cset∪{u,v}；从e1中删去与u和v相关联的所有边；

}

returnc}

cset用来存储顶点覆盖中的各顶点。初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset中，并将e1中已被u和v覆盖的边删去，直至cset已覆盖所有边。即e1为空。2023/2/2DesignandAnalysisofAlgorithm9

图(a)～(e)说明了算法的运行过程及结果。(e)表示算法产生的近似最优顶点覆盖cset，它由顶点b,c,d,e,f,g所组成。(f)是图G的一个最小顶点覆盖，它只含有3个顶点：b,d和e。算法approxVertexCover的性能比为2。11.2.1顶点覆盖问题2023/2/2DesignandAnalysisofAlgorithm10时间复杂性：cset可用数组来存储各顶点，则初始化cset需要执行n次，设图G含有n个顶点e条边，则算法的时间复杂性为O(n+e)近似比若用A表示算法在“从e1中任取一条边(u,v)”步骤中选取的边的集合，则A中任何两条边没公共顶点。算法结束时，cset中的顶点数|V’|=2|A|。图G的任一顶点覆盖一定包含A中各边的至少一个端点，因此，若最小顶点覆盖为V*，则|V*|>=|A|，即|V*|>=|V’|/2，即(|V’|/|V*|)<=211.2.1顶点覆盖问题2023/2/2DesignandAnalysisofAlgorithm11第11章近似算法11.2.1顶点覆盖问题11.2.2TSP问题2023/2/2DesignandAnalysisofAlgorithm1211.2.2旅行售货员问题问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。

比如，费用函数c往往具有三角不等式性质，即对任意的3个顶点u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数c就具有三角不等式性质。

TSP

问题的一些特殊性质：但是，可以设计一个近似算法，其近似比为2。图11.2(a)给出了一个满足三角不等式的无向图，图中方格的边长为1。求解TSP问题的近似算法首先采用Prim算法生成图的最小生成树T，如图(b)所示，图中粗线表示最小生成树中的边，然后对T进行深度优先遍历，经过的路线为a→b→c→b→h→b→a→d→e→f→e→g→e→d→a，得到遍历序列L=(a,b,c,h,d,e,f,g)，由序列L得到哈密顿回路，即近似最优解，如图(d)所示，其路径长度约为19.074，图(e)所示是(a)的最优解，其路径长度约为16.084。2023/2/2DesignandAnalysisofAlgorithm1411.2.2具有三角不等式性质的

旅行售货员问题举例(b)表示找到的最小生成树T；(c)表示对T作深度优先遍历的次序；(d)表示L产生的哈密顿回路H；(e)是G的一个最小费用旅行售货员回路。

2023/2/2DesignandAnalysisofAlgorithm1511.2.2具有三角不等式性质的

旅行售货员问题

对于给定的无向图G，可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。voidapproxTSP(Graphg){(1)选择G的任一顶点r；

(2)用Prim算法找出带权图G的一棵以r为根的最小生成树T；

(3)对生成树T从顶点r出发进行深度优先遍历，得遍历序列L；

(4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；}

当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。

2023/2/2DesignandAnalysisofAlgorithm16时间复杂性：算法的时间主要耗费在采用Prim算法构造最小生成树，因此，其时间复杂性为O(n2)。近似比设最短哈密尔顿回路为H*，W(H*)是代价和；T是由Prim算法求得的最小生成树，W(T)是T的代价和；H是由算法得到的近似解，也是一个哈密尔顿回路，W(H)是H的代价和。因哈密尔顿回路删去一条边可得G的一个生成树，故：W(T)≤W(H*)。设算法中深度优先遍历生成树T得到的路线为R，则R中对于T的每条边都经过两次，故有：W(R)=2W(T)。算法得到的近似解H是R删除若干中间点（非第一次出现的点）得到的，每删除一个顶点恰好是用三角形的一边取代另外两边。如…c→b→h…，删b。11.2.2具有三角不等式性质的

旅行售货员问题2023/2/2DesignandAnalysisofAlgorithm17近似比（续）由三角不等式可知，这种取代不会增加总代价，所以有：W(H)≤W(R)。从而得：W(H)≤2W(H*)。由此可得算法的近似比为2。11.2.2具有三角不等式性质的

旅行售货员问题2023/2/2DesignandAnalysisofAlgorithm1811.2.2一般的旅行售货员问题

在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多项式时间近似算法，除非P=NP。换句话说，若P≠NP，则对任意常数ρ>1，不存在性能比为ρ的解旅行售货员问题的多项式时间近似算法。

2023/2/2DesignandAnalysisofAlgorithm19第11章近似算法11.1概

述

11.2图问题中的近似法11.3组合问题中的近似法*11.4

实验项目——TSP问题的近似法2023/2/2DesignandAnalysisofAlgorithm2011.3.1装箱问题装箱问题描述

给定n个物体u1,u2,…,un

，体积分别为s1,s2,…,sn

，容量为C的箱子b1,b2,…,bk,…，满足si≤C,i=1,2,…,n。要求物体不能分割，把所有物体装进箱子，使所装入的箱子尽可能少。装箱问题的四种算法FirstFit（首次适宜FF）算法把箱子按下标标记，所有的箱子初始化为空；按物体顺序装入箱子。装入过程如下：把第一个物体u1装入第一个箱子如果b1还容纳得下第二个物体u2，继续把u2装入b1；2023/2/2DesignandAnalysisofAlgorithm2111.3.1装箱问题否则，把u2装入b2。一般地，为了装入物体ui，先找出能容纳得下si的下标最小的箱子bk，再把物体ui装入箱子bk，重复这些步骤，直到把所有物体装入箱子为止。FF算法算法12.3装箱问题的首次适宜算法输入：n个物体的体积s[],箱子的容量C输出：装入箱子的个数k,每个箱子中装入的物体累计体积b[]例如，有10个物品，其体积分别为S＝(4,2,7,3,5,4,2,3,6,2)，若干个容量为10的箱子，采用首次适宜法得到的装箱结果如图11.3所示。

0.3(s4)0.2(s2)0.4(s1)0.2(s7)0.7(s3)0.4(s6)0.5(s5)0.6(s9)0.3(s8)0.2(s10)(a)箱子1(b)箱子2(c)箱子3(d)箱子4(e)箱子5图11.3首次适宜法求解装箱问题示例（阴影表示闲置部分）

首次适宜法求解装箱问题的算法如下：2023/2/2DesignandAnalysisofAlgorithm2311.3.1装箱问题算法11.3——FF算法

1.voidfirst_fit(floats[],intn,floatC,floatb[],int&k)2.{

3.inti,j;

4.k=0; /*装入物体的箱子下标*/

5.for(i=0;i<n;i++) /*箱子初始化为空*/

6.b[i]=0;7.for(i=0;i<n;i++){ /*按物体顺序装入*/

8.j=0;

9.while((C-b[j])<s[i]))/*检索能容纳物体i的下标最小的箱子j*/10.j++;11.b[j]+=s[i];12.k=max(k,j); /*已装入物体的箱子最大下标*/13.}14.k++; /*箱子的最大下标转换为箱子的个数*/15.}伪代码2023/2/2DesignandAnalysisofAlgorithm2411.3.1装箱问题FF算法的分析时间复杂性：O(n^2)时间。近似比假定，C为一个单位体积，si≤1,i=1,2,…,n令FF(I)表示在实例I下，使用算法FF装入物体时，所使用的箱子总容量；令OPT(I)为最优装入时所使用的箱子总容量。至多有一个非空的箱子所装的物体体积小于1/2。否则，如果有两个以上的箱子所装的物体体积小于1/2，假设这两个箱子是bi及bj，并且i<j，装入bi及bj中物体的体积均小于1/22023/2/2DesignandAnalysisofAlgorithm2511.3.1装箱问题按照算法的装入规则，必然把bj中的物体继续装入bi，而不会装入bj箱子则装入箱子的物体如下图所示：:为箱子中的空余体积:为箱子中装入的物体体积。有:2023/2/2DesignandAnalysisofAlgorithm2611.3.1装箱问题对第k个箱子，或者是，或者是对后一情况，有：，，所以：对这两种情况都有：

，

所以，及2023/2/2DesignandAnalysisofAlgorithm2711.3.1装箱问题FF算法的性近似比小于2。实际上，经过复杂而冗长的证明，可以得到：对装箱物体的所有实例I，FF算法的性能为：在最优化装入时，所有的箱子恰好装入全部物体，即：FF算法的性能比率2023/2/2DesignandAnalysisofAlgorithm2811.3.1装箱问题BestFit（最适宜BF）算法：与FF算法类似不同点：为了装入物体ui，首先检索能容纳得下si、剩余容量最小的箱子bk，再把物体ui装入箱子bk，重复这些步骤，直到把所有物体装入箱子为止。2．最适宜法最适宜法的物品装入过程与首次适宜法类似，不同的是，总是把物品装到能够容纳它并且目前最满的箱子中，使得该箱子装入物品后闲置空间最小。例如，有10个物品，其体积分别为S＝(4,2,7,3,5,4,2,3,6,2)，若干个容量为10的箱子，采用最适宜法得到的装箱结果如图11.4所示。

0.4(s6)0.2(s2)0.4(s1)0.3(s4)0.7(s3)0.3(s8)0.2(s7)0.5(s5)0.2(s10)0.6(s9)(a)箱子1(b)箱子2(c)箱子3(d)箱子4图11.4最适宜法求解装箱问题示例（阴影表示闲置部分）2023/2/2DesignandAnalysisofAlgorithm3011.3.1装箱问题算法11.4——BF算法

1.voidBest_fit(floats[],intn,floatC,floatb[],int&k)2.{//假设物品体积为整数，b[j]为第j个箱子已装入物品的体积，数组下标均从1开始

3.inti,j;

4.k=0; /*初始化*/

5.for(j=0;j<n;j++)

6.b[j]=0;7.for(i=0;i<n;i++){ /*装入第i个物品*/

8.min=C;m=k+1;

9.for(j=1;j<=k;j++){//查找容纳物品i并且目前最满的编号最小的箱子10.temp=C-b[j]-s[i];11. if(temp>0&&temp<min{min=temp;m=j;}12.}13.b[m]+=s[i];k=max(k,m); /*已装入物体的箱子最大下标*/14.}15.returnk; /*已装入物品的箱子个数*/16.}伪代码2023/2/2DesignandAnalysisofAlgorithm3111.3.1装箱问题FirstFitDecreasing(首次适宜降序FFD)算法首先把物体按体积大小递减的顺序排序然后用FF算法装入物体BestFitDecreasing（最适宜降序BFD）算法首先把物体按体积大小递减的顺序排序然后用BF算法装入物体11.3.2子集和问题

令S={s1,s2,…,sn}是一个正整数的集合，子集和问题要求在这个正整数集合中，找出其和不超过正整数C的最大和数的子集。考虑蛮力法求解子集和问题，为了求得集合{s1,s2,…,sn}的所有子集和，先将所有子集和的集合初始化为L0={0}，然后求得子集和中包含s1的情况，即L0中的每一个元素加上s1，用L0+s1表示对集合L0中的每个元素加上s1后得到的新集合，则所有子集和的集合为L1=L0+(L0+s1)={0,s1}；再求得子集和中包含s2的情况，即L1中的每一个元素加上s2，所有子集和的集合为L2=L1+(L1+s2)={0,s1,s2,s1+s2}；依此类推，一般情况下，为求得子集和中包含si（1≤i≤n）的情况，即Li-1中的每一个元素加上si，所有子集和的集合为Li=Li-1+(Li-1+si)。因为子集和问题要求不超过正整数C，所以，每次合并后都要在Li中删除所有大于C的元素。例如，若S={104,102,201,101}，C=308，利用上述算法求解子集和问题的过程如图11.7所示L0={0}L1=L0+(L0+104)={0}+{104}={0,104}L2=L1+(L1+102)={0,104}+{102,206}={0,102,104,206}L3=L2+(L2+201)={0,102,104,206}+{201,303,305,407}={0,102,104,201,206,303,305}L4=L3+(L2+101)={0,102,104,201,206,303,305}+{101,203,205,302,307,404,406}={0,101,102,104,201,203,205,206,302,303,305,307}图11.7蛮力法求解子集和问题示例

集合Li以数组L[i]的形式存储，n个元素的正整数集合S用数组s[n]存储且下标从1开始，两个集合的合并操作与4.3.1中介绍的归并排序的合并算法类似，蛮力法求解子集和问题的算法如下：

算法11.5——子集和问题

intSubsetSum1(intn,ints[],intC){L[0]={0}；

for(i=1;i<=n;i++)//依次计算子集和中包含元素s[i]{L[i]=Merge(L[i-1],L[i-1]+s[i])；删去L[i]中超过C的元素；

}returnmax(L[n])；

}伪代码

算法SubsetSum1中的数组L[i]是一个包含了不超过C的所有可能的(s1,s2,…,si)的子集和，在最坏情况下（即L[i]中的元素各不相同），L[i]中的元素个数为2i，所以，算法SubsetSum1的时间复杂性为O(2n)基于算法SubsetSum1的近似算法的基本思想是，在迭代过程中，对数组L[i]进行适当的修整，使得在子集和不超过一定误差的前提下，尽可能减少数组L[i]中的元素个数，从而获得算法时间性能的提高。具体方法是：用一个修整参数δ（0＜δ＜1），从数组L[i]中删去尽可能多的元素，得到一个数组L1[i]，使得每一个从L[i]中删去的元素y，在数组L1[i]中都有一个修整后的元素z满足(1-δ)×y≤z≤y，可以将z看作是被删去元素y在修整后的数组L1[i]中的代表。例如，若δ=0.1，且L={10,11,12,15,20,21,22,23,24,29}，则用δ对L进行修整后得到L1={10,12,15,20,23,29}。其中被删去的元素11由10来代表，21和22由20来代表，24由23来代表。给定一个修整参数δ，对有序数组L的修整算法如下：算法11.6——有序数组的修整

int[]Trim(int

m,intL[],intL1[],doubleδ){//数组L的长度为m，下标从1开始，

//对数组L修整后存储在数组L1中

L1[1]=L[1];//数组L1中一定包含数组L的最小元素，并作为修整的基础

last=L[1]；

for(i=2;i<=m;i++){if(last<(1-δ)*L[i]){//将所有与last相差δ的元素删去将L[i]加入表L1的尾部；

last=L[i]；

}}returnL1;}伪代码

算法Trim的基本语句是for循环中的条件语句，显然，其时间复杂性为O(m)。子集和问题的近似算法与蛮力法求解子集和问题的算法类似。不同的是，近似算法在每次合并结束并且删除所有大于C的元素后，在子集和不超过近似误差ε的前提下，以δ=ε/n作为修整参数对合并结果Li进行修整，尽可能减少下次参与迭代的元素个数。例如，设正整数的集合S={104,102,201,101}，C=308，给定近似参数ε=0.2，则修整参数为δ=ε/n=0.05，利用近似算法求解子集和问题的过程如图11.8所示。算法最后返回302作为子集和问题的近似解，而最优解为104+102+101=307，所以，近似解的相对误差不超过预先给定的近似参数0.02。

L0={0}L1=L0+(L0+104)={0}+{104}={0,104}对L1进行修整：L1={0,104}L2=L1+(L1+102)={0,104}+{102,206}={0,102,104,206}对L2进行修整：L2={0,102,206}L3=L2+(L2+201)={0,102,206}+{201,303,407}={0,102,201,206,303}对L3进行修整：L3={0,102,201,303}L4=L3+(L2+101)={0,102,201,303}+{101,203,302,404}={0,101,102,201,203,