第6章近似算法

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

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

3、的算法為(n)-近似算法.對(duì)于最大化問(wèn)題而言,0CC*,而對(duì)于最小化問(wèn)題而言, 00為輸入,使得對(duì)于任給正數(shù)的1+近似算法.多項(xiàng)式時(shí)間近似模式(PTAS):我們稱一個(gè)近似模式是一個(gè)多項(xiàng)式時(shí)間近似模式(PTAS),如果對(duì)于任給的正數(shù),該模式的執(zhí)行時(shí)間不超過(guò)關(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ì)以超過(guò)常數(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)覆蓋問(wè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中沒(méi)有兩條邊被來(lái)自最小頂點(diǎn)覆蓋的同一頂點(diǎn)覆蓋.由此可得,|C|C* *|A|A|.由于在第4步所選的邊的兩個(gè)頂點(diǎn)事先并不出現(xiàn)在C中,因此,|C|=2|A|2|C*|.二. 旅行商問(wèn)題的近似算法(The traveling-salesman problem)給定

6、完全無(wú)向圖G=(V,E),成本函數(shù)c:VV N, A E. c(A)= .實(shí)際中,很多場(chǎng)合是指從一個(gè)地方到另一個(gè)地方最便宜的開(kāi)銷.三角不等式:對(duì)于任意三個(gè)頂點(diǎn)u,v,wV,c(u,w)c(u,v)+c(v,w).Avuvuc),(),(1. 滿足三角不等式的旅行商問(wèn)題的近似算法1. 滿足三角不等式的旅行商問(wèn)題的近似算法 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. 一般的旅行商問(wèn)題(The general traveling-salesman problem) 定理: 如果PNP,則對(duì)于任一常數(shù)1,一般旅行商問(wèn)題不存在近似比為的多項(xiàng)式時(shí)間近似算法.證明過(guò)程中考慮構(gòu)造以下成本函數(shù):c(u,v)=otherwiseVEvuif , 1|,),(1，三. 集合覆蓋問(wèn)題(The set-covering problem)F=S1,S2,S3,S4,S5,S6,貪心解:C=S1,S4,S5,S3.集合覆蓋問(wèn)題的近似算法 GREEDY-SET-COVER(X,F)1 U X2 C 3 While U 4 do select a SF t