算法設(shè)計(jì)與分析課件：第9章 近似算法

1、第9章 近似算法2022-2-17算法設(shè)計(jì)與分析課件2第9章 近似算法 迄今為止，所有的NP完全問(wèn)題都還沒(méi)有多項(xiàng)式時(shí)間算法。對(duì)于這類問(wèn)題，通?？刹扇∫韵聨追N解題策略。(1)只對(duì)問(wèn)題的特殊實(shí)例求解(2)用動(dòng)態(tài)規(guī)劃法或分支限界法求解 (3)用概率算法求解 (4)只求近似解(5)用啟發(fā)式方法求解 本章主要討論解NP完全問(wèn)題的近似算法近似算法。2022-2-17算法設(shè)計(jì)與分析課件39.1 近似算法的性能 若一個(gè)最優(yōu)化問(wèn)題的最優(yōu)值為c*，求解該問(wèn)題的一個(gè)近似算法求得的近似最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值為c，則將該近似算法的性能比近似算法的性能比定義為= 。在通常情況下，該性能比是問(wèn)題輸入規(guī)模n的一個(gè)函數(shù)(n)，

2、即 (n)。cccc*,*maxcccc*,*max該近似算法的相對(duì)誤差近似算法的相對(duì)誤差定義為= 。若對(duì)問(wèn)題的輸入規(guī)模n，有一函數(shù)(n)使得 (n)，則稱(n)為該近似算法的相對(duì)誤差界近似算法的相對(duì)誤差界。近似算法的性能比(n)與相對(duì)誤差界(n)之間顯然有如下關(guān)系：(n)(n)(n)-1(n)-1。 *ccc *ccc 2022-2-17算法設(shè)計(jì)與分析課件49.2 頂點(diǎn)覆蓋問(wèn)題的近似算法 問(wèn)題描述：無(wú)向圖G=(V,E)的頂點(diǎn)覆蓋是它的頂點(diǎn)集V的一個(gè)子集VV，使得若(u,v)是G的一條邊，則vV或uV。頂點(diǎn)覆蓋V的大小是它所包含的頂點(diǎn)個(gè)數(shù)|V|。 VertexSet approxVertexC

3、overapproxVertexCover ( Graph g ) cset=； e1=g.e； while (e1 != ) 從e1中任取一條邊(u,v)； cset=csetu,v； 從e1中刪去與u和v相關(guān)聯(lián)的所有邊； return c CsetCset用來(lái)存儲(chǔ)頂點(diǎn)用來(lái)存儲(chǔ)頂點(diǎn)覆蓋中的各頂點(diǎn)。初覆蓋中的各頂點(diǎn)。初始為空，不斷從邊集始為空，不斷從邊集e1e1中選取一邊中選取一邊( (u,v)u,v)，將邊的端點(diǎn)加入將邊的端點(diǎn)加入csetcset中，并將中，并將e1e1中已被中已被u u和和v v覆蓋的邊刪去，覆蓋的邊刪去，直至直至csetcset已覆蓋所有已覆蓋所有邊。即邊。即e1e1為空

4、。為空。 2022-2-17算法設(shè)計(jì)與分析課件59.2 頂點(diǎn)覆蓋問(wèn)題的近似算法 圖圖( (a)a)(e)(e)說(shuō)明說(shuō)明了算法的運(yùn)行過(guò)程了算法的運(yùn)行過(guò)程及結(jié)果。及結(jié)果。( (e)e)表示表示算法產(chǎn)生的近似最算法產(chǎn)生的近似最優(yōu)頂點(diǎn)覆蓋優(yōu)頂點(diǎn)覆蓋csetcset，它由頂點(diǎn)它由頂點(diǎn)b,c,d,e,f,gb,c,d,e,f,g所組所組成。成。( (f)f)是圖是圖G G的一的一個(gè)最小頂點(diǎn)覆蓋，個(gè)最小頂點(diǎn)覆蓋，它只含有它只含有3 3個(gè)頂點(diǎn)：個(gè)頂點(diǎn)：b,db,d和和e e。 算法approxVertexCoverapproxVertexCover的性能比為2。 2022-2-17算法設(shè)計(jì)與分析課件69.3

5、旅行售貨員問(wèn)題近似算法 問(wèn)題描述：給定一個(gè)完全無(wú)向圖G=(V,E)，其每一邊(u,v)E有一非負(fù)整數(shù)費(fèi)用c(u,v)。要找出G的最小費(fèi)用哈密頓回路。 比如，費(fèi)用函數(shù)c往往具有三角不等式性質(zhì)三角不等式性質(zhì)，即對(duì)任意的3個(gè)頂點(diǎn)u,v,wV，有：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ì)。 旅行售貨員問(wèn)題的一些特殊性質(zhì)特殊性質(zhì)：2022-2-17算法設(shè)計(jì)與分析課件79.3.1 具有三角不等式性質(zhì)的旅行售貨員問(wèn)題 對(duì)于給定的無(wú)向圖G，可以利用找圖圖G G的最小生成樹(shù)的最小生成樹(shù)的算法設(shè)計(jì)找近似最優(yōu)的旅

6、行售貨員回路的算法。 void approxTSPapproxTSP (Graph g) (1)選擇g的任一頂點(diǎn)r； (2)用Prim算法找出帶權(quán)圖g的一棵以r為根的最小生成樹(shù)T； (3)前序遍歷樹(shù)T得到的頂點(diǎn)表L； (4)將r加到表L的末尾，按表L中頂點(diǎn)次序組成回路H，作為計(jì)算結(jié)果返回； 當(dāng)費(fèi)用函數(shù)滿足三角不等式時(shí)，算法找出的旅行售貨員回路的費(fèi)用不會(huì)超過(guò)最優(yōu)旅行售貨員回路費(fèi)用的2倍。 2022-2-17算法設(shè)計(jì)與分析課件89.3.1 具有三角不等式性質(zhì)的旅行售貨員問(wèn)題舉例( (b)b)表示找到的最小生成表示找到的最小生成樹(shù)樹(shù)T T；( (c)c)表示對(duì)表示對(duì)T T作前序作前序遍歷的次序；遍歷

7、的次序；(d)(d)表示表示L L產(chǎn)產(chǎn)生的哈密頓回路生的哈密頓回路H H；(e)(e)是是G G的一個(gè)最小費(fèi)用旅的一個(gè)最小費(fèi)用旅行售貨員回路。行售貨員回路。 2022-2-17算法設(shè)計(jì)與分析課件99.3.2 一般的旅行售貨員問(wèn)題 在費(fèi)用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問(wèn)題的多項(xiàng)式時(shí)間近似算法，除非P=NPP=NP。換句話說(shuō)，若PNP，則對(duì)任意常數(shù)1，不存在性能比為的解旅行售貨員問(wèn)題的多項(xiàng)式時(shí)間近似算法。 2022-2-17算法設(shè)計(jì)與分析課件109.4 集合覆蓋問(wèn)題的近似算法 集合覆蓋問(wèn)題的一個(gè)實(shí)例X,F由一個(gè)有限集X及X的一個(gè)子集族F組成。子集族F覆蓋了有限

8、集X。也就是說(shuō)X中每一元素至少屬于F中的一個(gè)子集，即X= 。對(duì)于F中的一個(gè)子集CF，若C中的X的子集覆蓋了X，即X= ，則稱C覆蓋了X。集合覆蓋問(wèn)題就是要找出F中覆蓋X的最小子集C*，使得 |C*|=min|C|CF且C覆蓋X FSSCSS2022-2-17算法設(shè)計(jì)與分析課件119.4 集合覆蓋問(wèn)題的近似算法集合覆蓋問(wèn)題舉例：用用1212個(gè)黑點(diǎn)表示集個(gè)黑點(diǎn)表示集合合X X。F=S1,S2,S3,S4,SF=S1,S2,S3,S4,S5,S6,5,S6,，如圖所示。如圖所示。容易看出，對(duì)于這容易看出，對(duì)于這個(gè)例子，最小集合個(gè)例子，最小集合覆蓋為：覆蓋為：C=S3,S4,S5,C=S3,S4,S5

9、,。 2022-2-17算法設(shè)計(jì)與分析課件129.4 集合覆蓋問(wèn)題的近似算法集合覆蓋問(wèn)題近似算法貪心算法 算法的循環(huán)體最多算法的循環(huán)體最多執(zhí)行執(zhí)行min|X|min|X|，|F|F|次。次。而循環(huán)體內(nèi)的計(jì)算顯然而循環(huán)體內(nèi)的計(jì)算顯然可在可在O(|X|F|)O(|X|F|)時(shí)間內(nèi)完時(shí)間內(nèi)完成。因此，算法的計(jì)算成。因此，算法的計(jì)算時(shí)間為時(shí)間為O(|X|F|min|X|O(|X|F|min|X|，|F|)|F|)。由此即知，該算由此即知，該算法是一個(gè)多項(xiàng)式時(shí)間算法是一個(gè)多項(xiàng)式時(shí)間算法。法。 Set greedySetCovergreedySetCover (X,F) U=X； C=； while (U

10、 !=) 選擇F中使|SU|最大的子集S； U=U-S； C=CS； return C； 2022-2-17算法設(shè)計(jì)與分析課件139.5 子集合問(wèn)題的近似算法 問(wèn)題描述：設(shè)子集和問(wèn)題的一個(gè)實(shí)例為S,t。其中，S=x1，x2，xn是一個(gè)正整數(shù)的集合，t是一個(gè)正整數(shù)。子集和問(wèn)題判定是否存在S的一個(gè)子集S1，使得 。txSx 12022-2-17算法設(shè)計(jì)與分析課件149.5.1 子集合問(wèn)題的指數(shù)時(shí)間算法int exactSubsetSumexactSubsetSum (S,t) int n=|S|； L0=0； for (int i=1；i=n；i+) Li=mergeLists(Li-1,Li-1

11、+Si)； 刪去Li中超過(guò)t的元素； return max(Ln)；算法以集合算法以集合S=xS=x1 1，x x2 2，x xn n 和目標(biāo)和目標(biāo)值值t t作為輸入。算法作為輸入。算法中用到將中用到將2 2個(gè)有序表個(gè)有序表L1L1和和L2L2合并成為一合并成為一個(gè)新的有序表的算個(gè)新的有序表的算法法mergeListsmergeLists(L1,L2)(L1,L2)。 2022-2-17算法設(shè)計(jì)與分析課件159.5.2 子集合問(wèn)題的完全多項(xiàng)式時(shí)間近似格式 基于算法exactSubsetSum，通過(guò)對(duì)表Li作適當(dāng)?shù)男拚⒁粋€(gè)子集和問(wèn)題的完全多項(xiàng)式時(shí)間近似格式完全多項(xiàng)式時(shí)間近似格式。 在對(duì)表Li

12、進(jìn)行修整時(shí)，用到一個(gè)修整參數(shù)，01。用參數(shù)修整一個(gè)表L是指從L中刪去盡可能多的元素，使得每一個(gè)從L中刪去的元素y，都有一個(gè)修整后的表L1中的元素z滿足(1-)yzy。可以將z看作是被刪去元素y在修整后的新表L1中的代表。 舉例：舉例：若=0.1，且L=10,11,12,15,20,21,22,23,24,29，則用對(duì)L進(jìn)行修整后得到L1=10，12，15，20，23，29。其中被刪去的數(shù)11由10來(lái)代表，21和22由20來(lái)代表，24由23來(lái)代表。 2022-2-17算法設(shè)計(jì)與分析課件169.5.2 子集合問(wèn)題的完全多項(xiàng)式時(shí)間近似格式對(duì)有序表L修整算法List trimtrim(L,) int m=|L|； L1=L1； int last=L1； for (int i=2；i=m；i+) if (last(1-)*Li)