第11章-近似算法

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

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

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

=

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

≤ε(n)

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

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

ε(n)≤ρ(n)-1

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

述

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

實(shí)驗(yàn)項(xiàng)目——TSP問題的近似法2023/2/2DesignandAnalysisofAlgorithm7第11章近似算法11.2.1頂點(diǎn)覆蓋問題

11.2.2TSP問題2023/2/2DesignandAnalysisofAlgorithm811.2.1頂點(diǎn)覆蓋問題

問題描述：無向圖G=(V,E)的頂點(diǎn)覆蓋問題：指是它的頂點(diǎn)集V的一個(gè)子集V’V，使得:若(u,v)是G的一條邊，則v∈V’或u∈V’。頂點(diǎn)覆蓋V’的大小是它所包含的頂點(diǎn)個(gè)數(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用來存儲(chǔ)頂點(diǎn)覆蓋中的各頂點(diǎn)。初始為空，不斷從邊集e1中選取一邊(u,v)，將邊的端點(diǎn)加入cset中，并將e1中已被u和v覆蓋的邊刪去，直至cset已覆蓋所有邊。即e1為空。2023/2/2DesignandAnalysisofAlgorithm9

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

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

TSP

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

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

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

旅行售貨員問題

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

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

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

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

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

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

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

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

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

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

述

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

實(shí)驗(yàn)項(xiàng)目——TSP問題的近似法2023/2/2DesignandAnalysisofAlgorithm2011.3.1裝箱問題裝箱問題描述

給定n個(gè)物體u1,u2,…,un

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

，容量為C的箱子b1,b2,…,bk,…，滿足si≤C,i=1,2,…,n。要求物體不能分割，把所有物體裝進(jìn)箱子，使所裝入的箱子盡可能少。裝箱問題的四種算法FirstFit（首次適宜FF）算法把箱子按下標(biāo)標(biāo)記，所有的箱子初始化為空；按物體順序裝入箱子。裝入過程如下：把第一個(gè)物體u1裝入第一個(gè)箱子如果b1還容納得下第二個(gè)物體u2，繼續(xù)把u2裝入b1；2023/2/2DesignandAnalysisofAlgorithm2111.3.1裝箱問題否則，把u2裝入b2。一般地，為了裝入物體ui，先找出能容納得下si的下標(biāo)最小的箱子bk，再把物體ui裝入箱子bk，重復(fù)這些步驟，直到把所有物體裝入箱子為止。FF算法算法12.3裝箱問題的首次適宜算法輸入：n個(gè)物體的體積s[],箱子的容量C輸出：裝入箱子的個(gè)數(shù)k,每個(gè)箱子中裝入的物體累計(jì)體積b[]例如，有10個(gè)物品，其體積分別為S＝(4,2,7,3,5,4,2,3,6,2)，若干個(gè)容量為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/2DesignandAnalysisofAlgorithm2311.3.1裝箱問題算法11.3——FF算法

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

3.inti,j;

4.k=0; /*裝入物體的箱子下標(biāo)*/

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的下標(biāo)最小的箱子j*/10.j++;11.b[j]+=s[i];12.k=max(k,j); /*已裝入物體的箱子最大下標(biāo)*/13.}14.k++; /*箱子的最大下標(biāo)轉(zhuǎn)換為箱子的個(gè)數(shù)*/15.}偽代碼2023/2/2DesignandAnalysisofAlgorithm2411.3.1裝箱問題FF算法的分析時(shí)間復(fù)雜性：O(n^2)時(shí)間。近似比假定，C為一個(gè)單位體積，si≤1,i=1,2,…,n令FF(I)表示在實(shí)例I下，使用算法FF裝入物體時(shí)，所使用的箱子總?cè)萘?；令OPT(I)為最優(yōu)裝入時(shí)所使用的箱子總?cè)萘俊Ｖ炼嘤幸粋€(gè)非空的箱子所裝的物體體積小于1/2。否則，如果有兩個(gè)以上的箱子所裝的物體體積小于1/2，假設(shè)這兩個(gè)箱子是bi及bj，并且i<j，裝入bi及bj中物體的體積均小于1/22023/2/2DesignandAnalysisofAlgorithm2511.3.1裝箱問題按照算法的裝入規(guī)則，必然把bj中的物體繼續(xù)裝入bi，而不會(huì)裝入bj箱子則裝入箱子的物體如下圖所示：:為箱子中的空余體積:為箱子中裝入的物體體積。有:2023/2/2DesignandAnalysisofAlgorithm2611.3.1裝箱問題對(duì)第k個(gè)箱子，或者是，或者是對(duì)后一情況，有：，，所以：對(duì)這兩種情況都有：

，

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

1.voidBest_fit(floats[],intn,floatC,floatb[],int&k)2.{//假設(shè)物品體積為整數(shù)，b[j]為第j個(gè)箱子已裝入物品的體積，數(shù)組下標(biāo)均從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個(gè)物品*/

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

9.for(j=1;j<=k;j++){//查找容納物品i并且目前最滿的編號(hào)最小的箱子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); /*已裝入物體的箱子最大下標(biāo)*/14.}15.returnk; /*已裝入物品的箱子個(gè)數(shù)*/16.}偽代碼2023/2/2DesignandAnalysisofAlgorithm3111.3.1裝箱問題FirstFitDecreasing(首次適宜降序FFD)算法首先把物體按體積大小遞減的順序排序然后用FF算法裝入物體BestFitDecreasing（最適宜降序BFD）算法首先把物體按體積大小遞減的順序排序然后用BF算法裝入物體11.3.2子集和問題

令S={s1,s2,…,sn}是一個(gè)正整數(shù)的集合，子集和問題要求在這個(gè)正整數(shù)集合中，找出其和不超過正整數(shù)C的最大和數(shù)的子集?？紤]蠻力法求解子集和問題，為了求得集合{s1,s2,…,sn}的所有子集和，先將所有子集和的集合初始化為L(zhǎng)0={0}，然后求得子集和中包含s1的情況，即L0中的每一個(gè)元素加上s1，用L0+s1表示對(duì)集合L0中的每個(gè)元素加上s1后得到的新集合，則所有子集和的集合為L(zhǎng)1=L0+(L0+s1)={0,s1}；再求得子集和中包含s2的情況，即L1中的每一個(gè)元素加上s2，所有子集和的集合為L(zhǎng)2=L1+(L1+s2)={0,s1,s2,s1+s2}；依此類推，一般情況下，為求得子集和中包含si（1≤i≤n）的情況，即Li-1中的每一個(gè)元素加上si，所有子集和的集合為L(zhǎng)i=Li-1+(Li-1+si)。因?yàn)樽蛹蛦栴}要求不超過正整數(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]的形式存儲(chǔ)，n個(gè)元素的正整數(shù)集合S用數(shù)組s[n]存儲(chǔ)且下標(biāo)從1開始，兩個(gè)集合的合并操作與4.3.1中介紹的歸并排序的合并算法類似，蠻力法求解子集和問題的算法如下：

算法11.5——子集和問題

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

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

}returnmax(L[n])；

}偽代碼

算法SubsetSum1中的數(shù)組L[i]是一個(gè)包含了不超過C的所有可能的(s1,s2,…,si)的子集和，在最壞情況下（即L[i]中的元素各不相同），L[i]中的元素個(gè)數(shù)為2i，所以，算法SubsetSum1的時(shí)間復(fù)雜性為O(2n)基于算法SubsetSum1的近似算法的基本思想是，在迭代過程中，對(duì)數(shù)組L[i]進(jìn)行適當(dāng)?shù)男拚沟迷谧蛹筒怀^一定誤差的前提下，盡可能減少數(shù)組L[i]中的元素個(gè)數(shù)，從而獲得算法時(shí)間性能的提高。具體方法是：用一個(gè)修整參數(shù)δ（0＜δ＜1），從數(shù)組L[i]中刪去盡可能多的元素，得到一個(gè)數(shù)組L1[i]，使得每一個(gè)從L[i]中刪去的元素y，在數(shù)組L1[i]中都有一個(gè)修整后的元素z滿足(1-δ)×y≤z≤y，可以將z看作是被刪去元素y在修整后的數(shù)組L1[i]中的代表。例如，若δ=0.1，且L={10,11,12,15,20,21,22,23,24,29}，則用δ對(duì)L進(jìn)行修整后得到L1={10,12,15,20,23,29}。其中被刪去的元素11由10來代表，21和22由20來代表，24由23來代表。給定一個(gè)修整參數(shù)δ，對(duì)有序數(shù)組L的修整算法如下：算法11.6——有序數(shù)組的修整

int[]Trim(int

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

//對(duì)數(shù)組L修整后存儲(chǔ)在數(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的基本語(yǔ)句是for循環(huán)中的條件語(yǔ)句，顯然，其時(shí)間復(fù)雜性為O(m)。子集和問題的近似算法與蠻力法求解子集和問題的算法類似。不同的是，近似算法在每次合并結(jié)束并且刪除所有大于C的元素后，在子集和不超過近似誤差ε的前提下，以δ=ε/n作為修整參數(shù)對(duì)合并結(jié)果Li進(jìn)行修整，盡可能減少下次參與迭代的元素個(gè)數(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，所以，近似解的相對(duì)誤差不超過預(yù)先給定的近似參數(shù)0.02。

L0={0}L1=L0+(L0+104)={0}+{104}={0,104}對(duì)L1進(jìn)行修整：L1={0,104}L2=L1+(L1+102)={0,104}+{102,206}={0,102,104,206}對(duì)L2進(jìn)行修整：L2={0,102,206}L3=L2+(L2+201)={0,102,206}+{201,303,407}={0,102,201,206,303}對(duì)L3進(jìn)行修整：L3={0,102,201,303}L4=L3+(L2+101)={0,102,201,303}+{101,203,302,404}={0,101,102,201,203,