第6章近似算法

1、第六章 近似算法 內(nèi)容提要 近似算法,近似比頂點(diǎn)覆蓋問題的近似算法旅行商問題的近似算法集合覆蓋問題的近似算法重點(diǎn)與難點(diǎn) 重點(diǎn):近似算法,近似比頂點(diǎn)覆蓋問題的近似算法旅行商問題的近似算法集合覆蓋問題的近似算法難點(diǎn):近似比的證明.學(xué)習(xí)目的與要求 理解近似算法,近似比的概念.通過學(xué)習(xí)頂點(diǎn)覆蓋問題的近似算法,旅行商問題的近似算法,集合覆蓋問題的近似算法的設(shè)計與分析,掌握近似比的分析與證明方法.近似算法的定義許多NP-完全問題都有著非常重要的實(shí)際意義.但求精確解卻非常困難而且不太可能求得最優(yōu)解.但我們可以從下面三方面來考慮NP-完全問題的求解:(1)由于任一個NP-完全問題都有指數(shù)時間算法,當(dāng)輸入實(shí)例規(guī)

2、模很小時,用其指數(shù)時間算法就可以求得滿意解;(2)可以單獨(dú)考慮問題的某些特殊場合,在這些場合中,問題有多項式時間算法求解;(3)考慮求問題的近似最優(yōu)解.用于求問題近似最優(yōu)解的算法稱為近似算法.下面討論若干個NP-完全問題的多項式時間近似算法.近似算法的性能比最大化問題與最小化問題:設(shè)每個最優(yōu)化問題的可行解有有個相關(guān)聯(lián)的正成本.最大化問題就是求具有最大成本的解.而最小化問題就是求具有最小成本的解.近似比(n):我們說一個問題的算法具有一個近似比(n),如果對于任一規(guī)模為n的輸入實(shí)例,算法的解所具有的成本C是最優(yōu)解所具有的成本C*的(n)倍以內(nèi).).(),max(*nCCCC我們稱達(dá)到近似比(n)

3、的算法為(n)-近似算法.對于最大化問題而言,0CC*,而對于最小化問題而言, 00為輸入,使得對于任給正數(shù)的1+近似算法.多項式時間近似模式(PTAS):我們稱一個近似模式是一個多項式時間近似模式(PTAS),如果對于任給的正數(shù),該模式的執(zhí)行時間不超過關(guān)于輸入實(shí)例n的多項式. 多項式時間近似模式的執(zhí)行時間可能隨正數(shù)的變小而增長非常迅速.例如,PTAS的執(zhí)行時間可能是(n2/).如果以常數(shù)倍減小,達(dá)到所希望的近似程度的解所花費(fèi)的執(zhí)行時間將不會以超過常數(shù)倍的速度增加.換句話說,我們希望執(zhí)行時間是關(guān)于1/和n的多項式.全多項式時間近似模式(FPTAS):如果一個近似模式的運(yùn)行時間是關(guān)于1/和n的多

4、項式.例如,(1/)2n3).一.頂點(diǎn)覆蓋問題(Vertex-cover)的近似算法頂點(diǎn)覆蓋,頂點(diǎn)覆蓋規(guī)模,最優(yōu)頂點(diǎn)覆蓋雖然要求最優(yōu)頂點(diǎn)覆蓋是困難的,但求近似最優(yōu)頂點(diǎn)覆蓋并不困難.APPROX-VERTEX-COVER(G)1 C 2 E EG3 While E 4 Do let (u,v) be an arbitrary edge of E5 C C u,v6 Remove from Eevery edge incident on either u or v 7 Return C上述算法的運(yùn)行時間是(|V|+|E|).算法APPROX-VERTEX-COVER是多項式時間2-近似算法.證明:

5、(1)算法APPROX-VERTEX-COVER是多項式時間算法;(易證)(2)由于算法循環(huán)執(zhí)行至G中的每條邊被C中的某頂點(diǎn)覆蓋為止,因此C是一個頂點(diǎn)覆蓋.下面證明C中的頂點(diǎn)至多是最小頂點(diǎn)覆蓋的兩倍.令A(yù)記算法第4步所選的邊集.為了覆蓋A中的邊,每個頂點(diǎn)覆蓋(包括最小頂點(diǎn)覆蓋)必包含A中每條邊至少一個端點(diǎn).而A中無兩邊有公共端點(diǎn).因此,A中沒有兩條邊被來自最小頂點(diǎn)覆蓋的同一頂點(diǎn)覆蓋.由此可得,|C|C* *|A|A|.由于在第4步所選的邊的兩個頂點(diǎn)事先并不出現(xiàn)在C中,因此,|C|=2|A|2|C*|.二. 旅行商問題的近似算法(The traveling-salesman problem)給定

6、完全無向圖G=(V,E),成本函數(shù)c:VV N, A E. c(A)= .實(shí)際中,很多場合是指從一個地方到另一個地方最便宜的開銷.三角不等式:對于任意三個頂點(diǎn)u,v,wV,c(u,w)c(u,v)+c(v,w).Avuvuc),(),(1. 滿足三角不等式的旅行商問題的近似算法1. 滿足三角不等式的旅行商問題的近似算法 APPROX-TSP-TOUR-WITHTRIAN(G,c)1. Select a vertex rV to be a root”vertex2. Compute a minimum spanning tree T for G from r using MST-PRIM(G,c

7、,r)3. Let L be the list of vertices visited in a preorder tree walk of T4. Return the Hamiltonian cycle H that visits the vertices in the order L2. 一般的旅行商問題(The general traveling-salesman problem) 定理: 如果PNP,則對于任一常數(shù)1,一般旅行商問題不存在近似比為的多項式時間近似算法.證明過程中考慮構(gòu)造以下成本函數(shù):c(u,v)=otherwiseVEvuif , 1|,),(1，三. 集合覆蓋問題(The set-covering problem)F=S1,S2,S3,S4,S5,S6,貪心解:C=S1,S4,S5,S3.集合覆蓋問題的近似算法 GREEDY-SET-COVER(X,F)1 U X2 C 3 While U 4 do select a SF t