算法設(shè)計與分析第9章 近似算法

《算法設(shè)計與分析第9章 近似算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

2、≤ε(n)，則稱ε(n)為該近似算法的相對誤差界。近似算法的性能比ρ(n)與相對誤差界ε(n)之間顯然有如下關(guān)系：ε(n)≤ρ(n)-1。39.2頂點覆蓋問題的近似算法問題描述：無向圖G=(V,E)的頂點覆蓋是它的頂點集V的一個子集V’?V，使得若(u,v)是G的一條邊，則v∈V’或u∈V’。頂點覆蓋V’的大小是它所包含的頂點個數(shù)

3、V’

4、。VertexSetapproxVertexCover(Graphg){cset=?；e1=g.e；while(e1!=?){從e1中任取一條邊(u,v)；cset=cset∪{u,v}；從e1中刪去與u和v相關(guān)聯(lián)的所有邊；}return

5、c}Cset用來存儲頂點覆蓋中的各頂點。初始為空，不斷從邊集e1中選取一邊(u,v)，將邊的端點加入cset中，并將e1中已被u和v覆蓋的邊刪去，直至cset已覆蓋所有邊。即e1為空。49.2頂點覆蓋問題的近似算法圖(a)～(e)說明了算法的運行過程及結(jié)果。(e)表示算法產(chǎn)生的近似最優(yōu)頂點覆蓋cset，它由頂點b,c,d,e,f,g所組成。(f)是圖G的一個最小頂點覆蓋，它只含有3個頂點：b,d和e。算法approxVertexCover的性能比為2。59.3旅行售貨員問題近似算法問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數(shù)費用c(u,v

6、)。要找出G的最小費用哈密頓回路。比如，費用函數(shù)c往往具有三角不等式性質(zhì)，即對任意的3個頂點u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。當(dāng)圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函數(shù)c就具有三角不等式性質(zhì)。旅行售貨員問題的一些特殊性質(zhì)：69.3.1具有三角不等式性質(zhì)的旅行售貨員問題對于給定的無向圖G，可以利用找圖G的最小生成樹的算法設(shè)計找近似最優(yōu)的旅行售貨員回路的算法。voidapproxTSP(Graphg){(1)選擇g的任一頂點r；(2)用Prim算法找出帶權(quán)圖g的一棵以r為根的最小生成樹T；(3)前序遍歷樹T得

7、到的頂點表L；(4)將r加到表L的末尾，按表L中頂點次序組成回路H，作為計算結(jié)果返回；}當(dāng)費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。79.3.1具有三角不等式性質(zhì)的旅行售貨員問題舉例(b)表示找到的最小生成樹T；(c)表示對T作前序遍歷的次序；(d)表示L產(chǎn)生的哈密頓回路H；(e)是G的一個最小費用旅行售貨員回路。89.3.2一般的旅行售貨員問題在費用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多項式時間近似算法，除非P=NP。換句話說，若P≠NP，則對任意常數(shù)ρ>1，不存在性能比為ρ的解旅

8、行售貨員問題的多項式時間近似算法。99.4集合覆蓋問題的近似算法問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數(shù)費用c(u,v)。要找出G的最小費用哈密頓回路。集合覆蓋問題的一個實例〈X,F〉由一個有限集X及X的一個子集族F組成。子集族F覆蓋了有限集X。也就是說X中每一元素至少屬于F中的一個子集，即X=。對于F中的一個子集C?F，若C中的X的子集覆蓋了X，即X=，則稱C覆蓋了X。集合覆蓋問題就是要找出F中覆蓋X的最小子集C*，使得

9、C*

10、=min{

11、C

12、

13、C?F且C覆蓋X}109.4集合覆蓋問題的近似算法集合覆蓋問題舉例：用12個黑點表示集合

14、X。F={S1,S2,S3,S4,S5,S6,}，如圖所示。容易看出，對于這個例子，最小集合覆蓋為：C={S3,S4,S5,}。119.4集合覆蓋問題的近似算法集合覆蓋問題近似算法——貪心算法算法的循環(huán)體最多執(zhí)行min{

15、X

16、，

17、F

18、}次。而循環(huán)體內(nèi)的計算顯然可在O(

19、X

20、

21、F

22、)時間內(nèi)完成。因此，算法的計算時間為O(

23、X

24、

25、F

26、min{

27、X

28、，

29、F

30、})。由此即知，該算法是一個多項式時間算法。SetgreedySetCover(X,F){U=X；C=?；while(U!=?){選擇F中使

31、S∩U

32、最大的子集S；U=U-S；C