課件lecture11近似算法

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

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

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

ma?

Mj的負(fù)載最大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臺(tái)機(jī)器, m(m-1)+1項(xiàng)作業(yè),前m(m-1)項(xiàng)作業(yè)的處理時(shí)間都為1,最后一項(xiàng)作業(yè)的處理時(shí)間為m.器,m項(xiàng),最后一項(xiàng)分配給留下的機(jī)器,16162738495遞降貪心法DG-MPS:首先按處理時(shí)間從大到小重新排列作業(yè),然后運(yùn)用G-MPS.865443338+3=116+4+3=13 DG-PMS(I)￡

1OPT(Im 2mMjMjai.Mj只有一個(gè)作業(yè)i1必為最優(yōu)解Mj22個(gè)以上作業(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(,城市的實(shí)例I使得3NN(I)>13

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

HMT得到一個(gè)歐拉圖,求這個(gè)歐拉圖的歐拉回路最后,沿著這條歐拉回路,跳過(guò)已走過(guò)的頂點(diǎn),抄近路得到一求任意圖最小權(quán)匹配的算法是多項(xiàng)式時(shí)間的,MM是多MM(I)MM(I)2H中的最短哈密頓回路C的長(zhǎng)度不超過(guò)原圖中最短哈密頓回路的長(zhǎng)度OPT(I).沿著C隔一條邊取一條邊,H的一個(gè)匹配.總可以使這個(gè)匹配的權(quán)不超過(guò)C長(zhǎng)的一半.因此,H的最小匹配M的權(quán)不超過(guò)OPT(I)/2求得的歐拉回路的長(zhǎng)小于(3/2)OPT(I).抄近路不會(huì)增加長(zhǎng)度,于 MM(I)<3OPT(I2 定理貨郎問(wèn)題(不要求滿足三角不等式是不可近似的證假設(shè)不然 設(shè)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)時(shí)間，A運(yùn)行是多項(xiàng)式時(shí)間，上述算法是HC的多項(xiàng)式時(shí)間算法.而HC是NP完全的, 任給n件物品和一個(gè)背包,物品i的重量為wi,價(jià)值為vi,1￡i￡n,背包的重量限制為B,其中wi,vi以及B都是正整數(shù). 即求子集S*?{1,2,…,n}使得

=max

￡B,S?

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