算法設(shè)計與分析 王紅梅 第二版 第11章 近似算法

第11章近似算法

ApproximateAlgorithm算法設(shè)計與分析—本科生課程DesignandAnalysisofAlgorithm海南大學(xué)信息科學(xué)技術(shù)學(xué)院CollegeofInformationScienceandTechnology,HainanUniversity2023/2/1DesignandAnalysisofAlgorithm2存在的問題迄今為止，所有的NP完全問題都還沒有多項式時間算法回溯法與分支限界等算法可以相對有效地解決這類問題，但算法的時間性能無法保證近似算法放棄求最優(yōu)解，而用近似最優(yōu)解代替最優(yōu)解，以換取算法設(shè)計上的簡化和時間復(fù)雜性的降低。但有些問題不適合用近似算法求解，對這些問題求近似最優(yōu)解幾乎和求最優(yōu)解一樣難。第11章近似算法2023/2/1DesignandAnalysisofAlgorithm3近似算法的依據(jù)輸入數(shù)據(jù)本身就是近似的，如測量數(shù)據(jù)很多問題的最優(yōu)解，允許有一定程度的近似采用近似算法可以在很短的時間內(nèi)得到問題的解（特別是與指數(shù)時間相比較）其思想是用近似最優(yōu)解代替最優(yōu)解，是在計算量和精確解間的一個折中近似算法性能的兩個重要指標對于規(guī)模為n

的問題算法能以的多項式時間內(nèi)完成算法的近似解滿足一定的精度，即近似最優(yōu)解的近似程度11.1概述2023/2/1DesignandAnalysisofAlgorithm4近似算法的性能近似比若一個問題的最優(yōu)值為c*，該問題的一個近似最優(yōu)解的目標函數(shù)值為c，則近似算法的性能比可定義為： =在通常情況下，是問題輸入規(guī)模n的一個函數(shù)ρ(n)，即：

≤ρ(n)11.1概述2023/2/1DesignandAnalysisofAlgorithm5與近似比率相關(guān)的問題對最小化問題，有：C≥C*對最大化問題，有：C≤C*近似算法C的近似比率ρ(n)總大于或等于1近似算法的近似比率越小，則算法的性能越好近似算法的近似比率越大，則算法的性能越差2023/2/1DesignandAnalysisofAlgorithm6近似算法的相對誤差與相對誤差界ε(n)

=

若對問題的輸入規(guī)模n，有一函數(shù)ε(n)使得:

≤ε(n)

則稱ε(n)為該近似算法的相對誤差界。近似比ρ(n)與相對誤差ε(n)間關(guān)系

ρ(n)與ε(n)之間顯然有如下關(guān)系：

ε(n)≤ρ(n)-1

11.1概述2023/2/1DesignandAnalysisofAlgorithm7討論：一些問題的近似算法有固定的近似比ρ和誤差界ε，即不隨問題規(guī)模n變化另一些問題的近似算法的ρ(n)

和ε(n)

隨問題規(guī)模n變化，即n越大，近似算法求出的近似最優(yōu)解與最優(yōu)解相差得就越多有些難解問題，可以找到這樣的近似算法，其近似比可以通過增加計算量來改進，也就是說，較少的計算量得到較粗糙的近似解，而較多的計算得可以得到較精確的近似解

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

述

11.2圖問題中的近似法11.3組合問題中的近似法*11.4

實驗項目——TSP問題的近似法2023/2/1DesignandAnalysisofAlgorithm9第11章近似算法11.2.1頂點覆蓋問題

11.2.2TSP問題2023/2/1DesignandAnalysisofAlgorithm1011.2.1頂點覆蓋問題

問題描述：無向圖G=(V,E)的頂點覆蓋問題：指是它的頂點集V的一個子集V’V，使得:若(u,v)是G的一條邊，則v∈V’或u∈V’。頂點覆蓋V’的大小是它所包含的頂點個數(shù)

|V’|。

VertexSetapproxVertexCover(Graphg){cset=；

e1=g.e；

while(e1!=){

從e1中任取一條邊(u,v)；

cset=cset∪{u,v}；從e1中刪去與u和v相關(guān)聯(lián)的所有邊；

}

returnc}

cset用來存儲頂點覆蓋中的各頂點。初始為空，不斷從邊集e1中選取一邊(u,v)，將邊的端點加入cset中，并將e1中已被u和v覆蓋的邊刪去，直至cset已覆蓋所有邊。即e1為空。2023/2/1DesignandAnalysisofAlgorithm11

圖(a)～(e)說明了算法的運行過程及結(jié)果。(e)表示算法產(chǎn)生的近似最優(yōu)頂點覆蓋cset，它由頂點b,c,d,e,f,g所組成。(f)是圖G的一個最小頂點覆蓋，它只含有3個頂點：b,d和e。算法approxVertexCover的性能比為2。11.2.1頂點覆蓋問題2023/2/1DesignandAnalysisofAlgorithm12時間復(fù)雜性：cset可用數(shù)組來存儲各頂點，則初始化cset需要執(zhí)行n次，設(shè)圖G含有n個頂點e條邊，則算法的時間復(fù)雜性為O(n+e)近似比若用A表示算法在“從e1中任取一條邊(u,v)”步驟中選取的邊的集合，則A中任何兩條邊沒公共頂點。算法結(jié)束時，cset中的頂點數(shù)|V’|=2|A|。圖G的任一頂點覆蓋一定包含A中各邊的至少一個端點，因此，若最小頂點覆蓋為V*，則|V*|>=|A|，即|V*|>=|V’|/2，即(|V’|/|V*|)<=211.2.1頂點覆蓋問題2023/2/1DesignandAnalysisofAlgorithm13第11章近似算法11.2.1頂點覆蓋問題11.2.2TSP問題2023/2/1DesignandAnalysisofAlgorithm1411.2.2旅行售貨員問題問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數(shù)費用c(u,v)。要找出G的最小費用哈密頓回路。

比如，費用函數(shù)c往往具有三角不等式性質(zhì)，即對任意的3個頂點u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。當(dāng)圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函數(shù)c就具有三角不等式性質(zhì)。

TSP

問題的一些特殊性質(zhì)：但是，可以設(shè)計一個近似算法，其近似比為2。圖11.2(a)給出了一個滿足三角不等式的無向圖，圖中方格的邊長為1。求解TSP問題的近似算法首先采用Prim算法生成圖的最小生成樹T，如圖(b)所示，圖中粗線表示最小生成樹中的邊，然后對T進行深度優(yōu)先遍歷，經(jīng)過的路線為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得到哈密頓回路，即近似最優(yōu)解，如圖(d)所示，其路徑長度約為19.074，圖(e)所示是(a)的最優(yōu)解，其路徑長度約為16.084。2023/2/1DesignandAnalysisofAlgorithm1611.2.2具有三角不等式性質(zhì)的

旅行售貨員問題舉例(b)表示找到的最小生成樹T；(c)表示對T作深度優(yōu)先遍歷的次序；(d)表示L產(chǎn)生的哈密頓回路H；(e)是G的一個最小費用旅行售貨員回路。

2023/2/1DesignandAnalysisofAlgorithm1711.2.2具有三角不等式性質(zhì)的

旅行售貨員問題

對于給定的無向圖G，可以利用找圖G的最小生成樹的算法設(shè)計找近似最優(yōu)的旅行售貨員回路的算法。voidapproxTSP(Graphg){(1)選擇G的任一頂點r；

(2)用Prim算法找出帶權(quán)圖G的一棵以r為根的最小生成樹T；

(3)對生成樹T從頂點r出發(fā)進行深度優(yōu)先遍歷，得遍歷序列L；

(4)將r加到表L的末尾，按表L中頂點次序組成回路H，作為計算結(jié)果返回；}

當(dāng)費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。

2023/2/1DesignandAnalysisofAlgorithm18時間復(fù)雜性：算法的時間主要耗費在采用Prim算法構(gòu)造最小生成樹，因此，其時間復(fù)雜性為O(n2)。近似比設(shè)最短哈密爾頓回路為H*，W(H*)是代價和；T是由Prim算法求得的最小生成樹，W(T)是T的代價和；H是由算法得到的近似解，也是一個哈密爾頓回路，W(H)是H的代價和。因哈密爾頓回路刪去一條邊可得G的一個生成樹，故：W(T)≤W(H*)。設(shè)算法中深度優(yōu)先遍歷生成樹T得到的路線為R，則R中對于T的每條邊都經(jīng)過兩次，故有：W(R)=2W(T)。算法得到的近似解H是R刪除若干中間點（非第一次出現(xiàn)的點）得到的，每刪除一個頂點恰好是用三角形的一邊取代另外兩邊。如…c→b→h…，刪b。11.2.2具有三角不等式性質(zhì)的

旅行售貨員問題2023/2/1DesignandAnalysisofAlgorithm19近似比（續(xù)）由三角不等式可知，這種取代不會增加總代價，所以有：W(H)≤W(R)。從而得：W(H)≤2W(H*)。由此可得算法的近似比為2。11.2.2具有三角不等式性質(zhì)的

旅行售貨員問題2023/2/1DesignandAnalysisofAlgorithm2011.2.2一般的旅行售貨員問題

在費用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多項式時間近似算法，除非P=NP。換句話說，若P≠NP，則對任意常數(shù)ρ>1，不存在性能比為ρ的解旅行售貨員問題的多項式時間近似算法。

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

述

11.2圖問題中的近似法11.3組合問題中的近似法*11.4

實驗項目——TSP問題的近似法2023/2/1DesignandAnalysisofAlgorithm2211.3.1裝箱問題裝箱問題描述

給定n個物體u1,u2,…,un

，體積分別為s1,s2,…,sn

，容量為C的箱子b1,b2,…,bk,…，滿足si≤C,i=1,2,…,n。要求物體不能分割，把所有物體裝進箱子，使所裝入的箱子盡可能少。裝箱問題的四種算法FirstFit（首次適宜FF）算法把箱子按下標標記，所有的箱子初始化為空；按物體順序裝入箱子。裝入過程如下：把第一個物體u1裝入第一個箱子如果b1還容納得下第二個物體u2，繼續(xù)把u2裝入b1；2023/2/1DesignandAnalysisofAlgorithm2311.3.1裝箱問題否則，把u2裝入b2。一般地，為了裝入物體ui，先找出能容納得下si的下標最小的箱子bk，再把物體ui裝入箱子bk，重復(fù)這些步驟，直到把所有物體裝入箱子為止。FF算法算法12.3裝箱問題的首次適宜算法輸入：n個物體的體積s[],箱子的容量C輸出：裝入箱子的個數(shù)k,每個箱子中裝入的物體累計體積b[]例如，有10個物品，其體積分別為S＝(4,2,7,3,5,4,2,3,6,2)，若干個容量為10的箱子，采用首次適宜法得到的裝箱結(jié)果如圖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/1DesignandAnalysisofAlgorithm2511.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++; /*箱子的最大下標轉(zhuǎn)換為箱子的個數(shù)*/15.}偽代碼2023/2/1DesignandAnalysisofAlgorithm2611.3.1裝箱問題FF算法的分析時間復(fù)雜性：O(n^2)時間。近似比假定，C為一個單位體積，si≤1,i=1,2,…,n令FF(I)表示在實例I下，使用算法FF裝入物體時，所使用的箱子總?cè)萘?；令OPT(I)為最優(yōu)裝入時所使用的箱子總?cè)萘俊Ｖ炼嘤幸粋€非空的箱子所裝的物體體積小于1/2。否則，如果有兩個以上的箱子所裝的物體體積小于1/2，假設(shè)這兩個箱子是bi及bj，并且i<j，裝入bi及bj中物體的體積均小于1/22023/2/1DesignandAnalysisofAlgorithm2711.3.1裝箱問題按照算法的裝入規(guī)則，必然把bj中的物體繼續(xù)裝入bi，而不會裝入bj箱子則裝入箱子的物體如下圖所示：:為箱子中的空余體積:為箱子中裝入的物體體積。有:2023/2/1DesignandAnalysisofAlgorithm2811.3.1裝箱問題對第k個箱子，或者是，或者是對后一情況，有：，，所以：對這兩種情況都有：

，

所以，及2023/2/1DesignandAnalysisofAlgorithm2911.3.1裝箱問題FF算法的性近似比小于2。實際上，經(jīng)過復(fù)雜而冗長的證明，可以得到：對裝箱物體的所有實例I，F(xiàn)F算法的性能為：在最優(yōu)化裝入時，所有的箱子恰好裝入全部物體，即：FF算法的性能比率2023/2/1DesignandAnalysisofAlgorithm3011.3.1裝箱問題BestFit（最適宜BF）算法：與FF算法類似不同點：為了裝入物體ui，首先檢索能容納得下si、剩余容量最小的箱子bk，再把物體ui裝入箱子bk，重復(fù)這些步驟，直到把所有物體裝入箱子為止。2．最適宜法最適宜法的物品裝入過程與首次適宜法類似，不同的是，總是把物品裝到能夠容納它并且目前最滿的箱子中，使得該箱子裝入物品后閑置空間最小。例如，有10個物品，其體積分別為S＝(4,2,7,3,5,4,2,3,6,2)，若干個容量為10的箱子，采用最適宜法得到的裝箱結(jié)果如圖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/1DesignandAnalysisofAlgorithm3211.3.1裝箱問題算法11.4——BF算法

1.voidBest_fit(floats[],intn,floatC,floatb[],int&k)2.{//假設(shè)物品體積為整數(shù)，b[j]為第j個箱子已裝入物品的體積，數(shù)組下標均從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; /*已裝入物品的箱子個數(shù)*/16.}偽代碼2023/2/1DesignandAnalysisofAlgorithm3311.3.1裝箱問題FirstFitDecreasing(首次適宜降序FFD)算法首先把物體按體積大小遞減的順序排序然后用FF算法裝入物體BestFitDecreasing（最適宜降序BFD）算法首先把物體按體積大小遞減的順序排序然后用BF算法裝入物體11.3.2子集和問題

令S={s1,s2,…,sn}是一個正整數(shù)的集合，子集和問題要求在這個正整數(shù)集合中，找出其和不超過正整數(shù)C的最大和數(shù)的子集?？紤]蠻力法求解子集和問題，為了求得集合{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)。因為子集和問題要求不超過正整數(shù)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以數(shù)組L[i]的形式存儲，n個元素的正整數(shù)集合S用數(shù)組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中的數(shù)組L[i]是一個包含了不超過C的所有可能的(s1,s2,…,si)的子集和，在最壞情況下（即L[i]中的元素各不相同），L[i]中的元素個數(shù)為2i，所以，算法SubsetSum1的時間復(fù)雜性為O(2n)基于算法SubsetSum1的近似算法的基本思想是，在迭代過程中，對數(shù)組L[i]進行適當(dāng)?shù)男拚?，使得在子集和不超過一定誤差的前提下，盡可能減少數(shù)組L[i]中的元素個數(shù)，從而獲得算法時間性能的提高。具體方法是：用一個修整參數(shù)δ（0＜δ＜1），從數(shù)組L[i]中刪去盡可能多的元素，得到一個數(shù)組L1[i]，使得每一個從L[i]中刪去的元素y，在數(shù)組L1[i]中都有一個修整后的元素z滿足(1-δ)×y≤z≤y，可以將z看作是被刪去元素y在修整后的數(shù)組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來代表。給定一個修整參數(shù)δ，對有序數(shù)組L的修整算法如下：算法11.6——有序數(shù)組的修整

int[]Trim(int

m,intL[],intL1[],doubleδ){//數(shù)組L的長度為m，下標從1開始，

//對數(shù)組L修整后存儲在數(shù)組L1中

L1[1]=L[1];//數(shù)組L1中一定包含數(shù)組L的最小元素，并作為修整的基礎(chǔ)

last=L[1]；

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

last=L[i]；

}}returnL1;}偽代碼

算法Trim的基本語句是for循環(huán)中的條件語句，顯然，其時間復(fù)雜性為O(m)。子集和問題的近似算法與蠻力法求解子集和問題的算法類似。不同的是，近似算法在每次合并結(jié)束并且刪除所有大于C的元素后，在子集和不超過近似誤差ε的前提下，以δ=ε/n作為修整參數(shù)對合并結(jié)果Li進行修整，盡可能減少下次參與迭代的元素個數(shù)。例如，設(shè)正整數(shù)的集合S={104,102,201,101}，C=308，給定近似參數(shù)ε=0.2，則修整參數(shù)為δ=ε/n=0.05，利用近似算法求解子集和問題的過程如圖11.8所示。算法最后返回302作為子集和問題的近似解，而最優(yōu)解為104+102+101=307，所以，近似解的相對誤差不超過預(yù)先給定的近似參數(shù)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