近似算法課件

第11章

近似算法

11.1概

述

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

實驗項目——TSP問題的近似算法11.1概

述

11.1.1近似算法的設(shè)計思想

11.1.2近似算法的性能許多難解問題實質(zhì)上是最優(yōu)化問題，即要求在滿足約束條件的前提下，使某個目標函數(shù)達到最大值或最小值的解。在這類問題中，求得最優(yōu)解往往需要付出極大的代價。在現(xiàn)實世界中，很多問題的輸入數(shù)據(jù)是用測量方法獲得的，而測量的數(shù)據(jù)本身就存在著一定程度的誤差，因此，輸入數(shù)據(jù)是近似的。同時，很多問題的解允許有一定程度的誤差，只要給出的解是合理的、可接受的，近似最優(yōu)解常常就能滿足實際問題的需要。此外，采用近似算法可以在很短的時間內(nèi)得到問題的近似解，所以，近似算法是求解難解問題的一個可行的方法。

11.1.1近似算法的設(shè)計思想

11.1.2近似算法的性能

衡量近似算法性能最重要的標準有兩個：（1）算法的時間復(fù)雜性：近似算法的時間復(fù)雜性必須是多項式階的，這是設(shè)計近似算法的基本目標；（2）解的近似程度：近似最優(yōu)解的近似程度也是設(shè)計近似算法的重要目標。近似程度可能與近似算法本身、問題規(guī)模，乃至不同的輸入實例都有關(guān)。不失一般性，假設(shè)近似算法求解的是最優(yōu)化問題，且對于一個確定的最優(yōu)化問題，每一個可行解所對應(yīng)的目標函數(shù)值均為正數(shù)。若一個最優(yōu)化問題的最優(yōu)值為c*，求解該問題的一個近似算法求得的近似最優(yōu)值為c，則將該近似算法的近似比（ApproximateRatio）η定義為：

在通常情況下，該性能比是問題輸入規(guī)模n的一個函數(shù)ρ(n)，即：這個定義對于最大化問題和最小化問題都是適用的。對于一個最大化問題，c≤c*，此時近似算法的近似比表示最優(yōu)值c*比近似最優(yōu)值c大多少倍；對于一個最小化問題，c*≤c，此時近似算法的近似比表示近似最優(yōu)值c比最優(yōu)值c*大多少倍。所以，近似算法的近似比η不會小于1，近似算法的近似比越大，它求出的近似解就越差。顯然，一個能求得最優(yōu)解的近似算法，其近似比為1。有時用相對誤差表示一個近似算法的近似程度會更方便些。若一個最優(yōu)化問題的最優(yōu)值為c*，求解該問題的一個近似算法求得的近似最優(yōu)值為c，則該近似算法的相對誤差（RelativeError）λ定義為：近似算法的相對誤差總是非負的，它表示一個近似最優(yōu)解與最優(yōu)解相差的程度。若問題的輸入規(guī)模為n，存在一個函數(shù)ε(n)，使得則稱ε(n)為該近似算法的相對誤差界（RelativeErrorBound）。近似算法的近似比ρ(n)與相對誤差界ε(n)之間顯然有如下關(guān)系：

有許多問題的近似算法具有固定的近似比和相對誤差界，即ρ(n)和ε(n)不隨著問題規(guī)模n的變化而變化，在這種情況下，用ρ和ε來表示近似比和相對誤差界。還有許多問題的近似算法沒有固定的近似比，即近似比ρ(n)隨著問題規(guī)模n的增長而增長，換言之，問題規(guī)模n越大，近似算法求出的近似最優(yōu)解與最優(yōu)解相差得就越多。對有些難解問題，可以找到這樣的近似算法，其近似比可以通過增加計算量來改進，也就是說，在計算量和解的精確度之間有一個折衷，較少的計算量得到較粗糙的近似解，而較多的計算量可以得到較精確的近似解。

11.2圖問題中的近似算法

11.2.1頂點覆蓋問題

11.2.2TSP問題中刪除，可以期望V'中的頂點數(shù)盡量少，但不能保證V'中的頂點數(shù)最少。圖11.1中給出了一個頂點覆蓋問題的近似算法求解過程。abcedfgabcedfgabcedfgabcedfgabcedfgabcedfg(a)一個無向圖(b)V'={a,b}(c)V'={a,b,c,f}刪除與a或b相關(guān)聯(lián)的邊刪除與c或f相關(guān)聯(lián)的邊(d)V'={a,b,c,f,d,e}(e)近似最小頂點覆蓋(f)最小頂點覆蓋刪除與d或e相關(guān)聯(lián)的邊V'={a,b,c,f,d,e}V'={a,b,c,e}圖11.1最小覆蓋問題的近似算法求解過程下面考察算法11.1的近似比。若用A表示算法在步驟3.1中選取的邊的集合，則A中任何兩條邊沒有公共頂點。因為算法選取了一條邊，并在將其頂點加入頂點覆蓋后，就將E'中與該邊的兩個頂點相關(guān)聯(lián)的所有邊從E'中刪除，因此，下一次再選取的邊就與該邊沒有公共頂點。由數(shù)學歸納法易知，A中的所有邊均沒有公共頂點。算法結(jié)束時，頂點覆蓋中的頂點數(shù)|V'|=2|A|。另一方面，圖G的任一頂點覆蓋一定包含A中各邊的至少一個端點，因此，若最小頂點覆蓋為V*，則|V*|≥|A|。由此可得，|V'|≤2|V*|，即算法11.1的近似比為2。但是，可以設(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。2adbchfegadbchfegadbchfeg1345678adbchfegadbchfeg(a)圖G的頂點(b)生成最小生成樹T(c)對T進行深度優(yōu)先遍歷(d)由遍歷序列產(chǎn)生哈密頓回路(e)TSP問題的最優(yōu)解圖11.2TSP問題的近似算法求解示例算法11.2——滿足三角不等式的TSP問題1．在圖中任選一個頂點v；2．采用Prim算法生成以頂點v為根結(jié)點的最小生成樹T；3．對生成樹T從頂點v出發(fā)進行深度優(yōu)先遍歷，得到遍歷序列L；4．根據(jù)L得到圖G的哈密頓回路；算法11.2的時間主要耗費在采用Prim算法構(gòu)造最小生成樹，因此，其時間復(fù)雜性為O(n2)。下面考察算法11.2的近似比。設(shè)滿足三角不等式的無向圖G的最短哈密頓回路為H*，W(H*)是H*的代價之和；T是由Prim算法求得的最小生成樹，W(T)是T的代價之和；H是由算法11.2得到的近似解，也是圖G的一個哈密頓回路，W(H)是H的代價之和。因為圖G的任意一個哈密頓回路刪去一條邊，構(gòu)成圖G的一個生成樹，所以，有W(T)≤W(H*)設(shè)算法11.2中深度優(yōu)先遍歷生成樹T得到的路線為R，則R中對于T的每條邊都經(jīng)過兩次，所以，有：

W(R)=2W(T)算法11.2得到的近似解H是R刪除了若干中間點（不是第一次出現(xiàn)的頂點）得到的，每刪除一個頂點恰好是用三角形的一條邊取代另外兩條邊。例如，在圖11.2中，遍歷生成樹的路線為a→b→c→b→h→b→a→d→e→f→e→g→e→d→a，刪除第2次出現(xiàn)的頂點b，相當于用邊(c,h)取代另外兩條邊(c,b)和(b,h)。由三角不等式可知，這種取代不會增加總代價，所以，有W(H)≤W(R)從而W(H)≤2W(H*)由此，算法11.2的近似比為2。11.3組合問題中的近似算法11.3.1裝箱問題11.3.2子集和問題取每一個物品，將該物品裝入第一個能容納它的箱子中。例如，有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首次適宜法求解裝箱問題示例（陰影表示閑置部分）首次適宜法求解裝箱問題的算法如下：算法11.3——首次適宜法intFirstFit(intn,intC,ints[],intb[]){//假設(shè)物品體積均為整數(shù)，b[j]為第j個箱子已裝入物品的體積，數(shù)組下標均從1開始k=0;for(j=1;j<=n;j++)//初始化b[j]=0;for(i=1;i<=n;i++)//裝入第i個物品{j=1;while(C-b[j]<s[i])//查找第1個能容納物品i的箱子j++;b[j]=b[j]+s[i];k=max(j,k);//已裝入物品的箱子個數(shù)}returnk;}C++描述所以，有：即由此，算法FirstFit的近似比小于2。

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最適宜法求解裝箱問題示例（陰影表示閑置部分）3．首次適宜降序法

首次適宜降序法首先將物品按體積從大到小排序，然后用首次適宜法裝箱。例如，有10個物品，其體積分別為S＝(4,2,7,3,5,4,2,3,6,2)，若干個容量為10的箱子，采用首次適宜降序法得到的裝箱結(jié)果如圖11.5所示。

0.3(s4)0.7(s3)0.4(s6)0.5(s5)0.2(s10)0.2(s7)0.2(s2)0.3(s8)(a)箱子1(b)箱子2(c)箱子3(d)箱子4圖11.5首次適宜降序法求解裝箱問題示例（陰影表示閑置部分）0.4(s1)0.6(s9)4．最適宜降序法最適宜降序法將物品按體積從大到小排序，然后用最適宜法裝箱。例如，有10個物品，其體積分別為S＝(4,2,7,3,5,4,2,3,6,2)，若干個容量為10的箱子，采用首次適宜降序法得到的裝箱結(jié)果如圖11.6所示。

0.3(s4)0.7(s3)0.4(s6)0.5(s5)0.2(s10)0.2(s7)0.2(s2)0.3(s8)(a)箱子1(b)箱子2(c)箱子3(d)箱子4圖11.6首次適宜降序法求解裝箱問題示例（陰影表示閑置部分）0.4(s1)0.6(s9)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,算法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)?；谒惴⊿ubsetSum1的近似算法的基本思想是，在迭代過程中，對數(shù)組L[i]進行適當?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,203,302,404}={0,101,102,201,203,302,303}對L4進行修整：L4={0,101,201,302}圖11.8近似算法求解子集和問題示例給定一個近似參數(shù)ε，子集和問題的近似算法如下：算法11.7——子集和問題int

SubsetSum2(intn,ints[],intC,doubleε){L[0]={0};for(i=1;i<=n;i++){L[i]=Merge(L[i-1],L[i-1]+s[i])；刪去L[i]中超過C的元素；L[i]=Trim(L[i],ε/n)；}returnmax(L[n])；}偽代碼在算法SubsetSum2中，每次對數(shù)組L[i]進行合并、刪除超過C的元素和修整操作的計算時間為O(|L[i]|)。因此，整個算法的計算時間不會超過O(n×|L[i]|)。注意到，算法對數(shù)組L[i]進行修整后，L[i]中相繼的兩個元素a和b滿足：

也就是說，數(shù)組L[i]中相繼的元素之間至少相差一個比例因子，而數(shù)組L[i]中的最大元素不會超過C，因此，算法