第6章近似算法

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

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

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

4、項(xiàng)式.例如,(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)行時(shí)間是(|V|+|E|).算法APPROX-VERTEX-COVER是多項(xiàng)式時(shí)間2-近似算法.證明:

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

6、完全無(wú)向圖G=(V,E),成本函數(shù)c:VV N, A E. c(A)= .實(shí)際中,很多場(chǎng)合是指從一個(gè)地方到另一個(gè)地方最便宜的開銷.三角不等式:對(duì)于任意三個(gè)頂點(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,則對(duì)于任一常數(shù)1,一般旅行商問題不存在近似比為的多項(xiàng)式時(shí)間近似算法.證明過程中考慮構(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