課件lecture11近似算法

1近似算法A是一個多項式時間算法且對組合優(yōu)化問題PI輸出一個可行解s.記A(I)=c(sc(s)是sA(I)=OPT(I即AI的最優(yōu)解當P是最小化問題時,記rA(I 當P是最大化問題時,I,rA(I￡ 23V并刪去u和v及其關(guān)聯(lián)的邊.重復上述過程,直至刪去所有的邊為止.V￠為所求的頂點覆蓋. {1, {1,2,3, 12345 一個最優(yōu)解：{1369}MVC的解：{123454算法時間復雜度為O(m),kk個頂點,OPT(Ik.MVC(I)￡2k=2OPT(I) Gk條互不關(guān)聯(lián)的邊構(gòu)成,MVC(I)=2k,OPT(I)=k,這表明MVC的近似比不會小于2. 構(gòu)造使算法產(chǎn)生最壞的解的實例.如果這個解的值與最優(yōu)值的比達到或者可以任意的接近得到的近似比(這樣不可改進的了;否則說明還有進一步的研究余地下,該問題近似算法的近似比的下界Am臺相同的機器,a的處理時間t(a),每項作業(yè)可以在任一臺機器上處理.如何把作業(yè)分配給機器才能使完成所有作業(yè)的時間最短?即,如何AmAiTTT

t(a)|i=1,2, ,

按輸入的順序分配作業(yè)把每一項作業(yè)分配給當前負載最小的機器.22臺以上,則分7 3+6=9,4+3+8=15,3+3+6=12,4+5+3=12,8mG-MPS(I)￡2-1OPT(Im1

ma?

Mj的負載最大t(Mjb是最后被分配給 1 mt(Mj)-t(b)￡t(a)-t(b).m G-MPS(I)=t(Mj 1 ￡ t(a)

t(b)

t(a)+1-1

m￡OPT(I)+1-1OPT(I m=2-1OPT(I mM臺機器, m(m-1)+1項作業(yè),前m(m-1)項作業(yè)的處理時間都為1,最后一項作業(yè)的處理時間為m.器,m項,最后一項分配給留下的機器,16162738495遞降貪心法DG-MPS:首先按處理時間從大到小重新排列作業(yè),然后運用G-MPS.865443338+3=116+4+3=13 DG-PMS(I)￡

1OPT(Im 2mMjMjai.Mj只有一個作業(yè)i1必為最優(yōu)解Mj22個以上作業(yè),im+1,OPT(I-nt(M)￡1 t(a t(a t(a t(a)+ t(a-n) 1n

m

1

1

m

. NN(I)=21,OPT(I)=15

2 1 11 1 1 I￡NN(I 1￡

1OPT(,城市的實例I使得3NN(I)>13

232MST:首先,求圖的一棵最小生成樹T.然后,T走兩遍得到圖的一條歐拉回路.最后,順著這條歐拉回路,跳過已走過的頂點,抄近路得到一條哈密頓回路.例求最小生成樹和歐拉回路都可以在多項式時間內(nèi)完成故<故T的權(quán)小于OPT(I).T走兩遍的長小于2OPT(I).因為滿足三角不等式,抄近路不會增加長度,故MST(I)<

HMT得到一個歐拉圖,求這個歐拉圖的歐拉回路最后,沿著這條歐拉回路,跳過已走過的頂點,抄近路得到一求任意圖最小權(quán)匹配的算法是多項式時間的,MM是多MM(I)MM(I)2H中的最短哈密頓回路C的長度不超過原圖中最短哈密頓回路的長度OPT(I).沿著C隔一條邊取一條邊,H的一個匹配.總可以使這個匹配的權(quán)不超過C長的一半.因此,H的最小匹配M的權(quán)不超過OPT(I)/2求得的歐拉回路的長小于(3/2)OPT(I).抄近路不會增加長度,于 MM(I)<3OPT(I2 定理貨郎問題(不要求滿足三角不等式是不可近似的證假設不然 設A是近似算法,近似比r￡K,K是常數(shù)城市集V,u,v?V,若(u,v)?E則d(u,v)=1G有哈密頓回路 OPT(IG)=n,A(IG)￡rOPT(IG)￡Kn調(diào)用算法A.若A(IG)￡Kn,則輸出“Yes”;否則輸出“No”.構(gòu)造IG用O(n2)時間，A運行是多項式時間，上述算法是HC的多項式時間算法.而HC是NP完全的, 任給n件物品和一個背包,物品i的重量為wi,價值為vi,1￡i￡n,背包的重量限制為B,其中wi,vi以及B都是正整數(shù). 即求子集S*?{1,2,…,n}使得

=max

￡B,S?

,順序檢查每一件物品只要能裝得下就將它裝入背包設裝vkmax{vi|i=1,2,n若vk>V,則將背包內(nèi)的物品換成物品k.例如(wi,vi):(3,7),(4,9),(5,9), G-KK給出的解是裝入(3,7)和(2,2總價值為9.若把第3件物品改為(5,10),則裝入第3件,總價值為10.定理對0-1I,OPT(I)<2G-量的價值從大到小排列,故有OPT(I)<G-KK(I)+vl￡G-KK(I)+vmax￡2G- sjsj 輸入>0和實例mv1/w1?v2/w2? ?t=1,2,mt件物品t件物品的重量之和.若它們的重量之和不超過B,則接著用G-KK把剩余,PTAS是一簇算法對每一個固定的e0,PTAS是一個算法e>0和0-1證設最優(yōu)解為S*不妨設考慮以S*中m件價值最大的物品為基礎用G-KKS.l是S*中第一件不在S中的物品,在此之前G-KK裝入不屬于S*的物品,于是OPT(I)<i?Svi+ vl￡i?Svi/m.OPT(I)<i?Svi+vl￡i?Svi