算法設(shè)計(jì)與分析ch9

1、第九章 Approximation Algorithm駱吉洲計(jì)算機(jī)科學(xué)與工程系9.1 Introduction 9.2 The Vetex-cover Problem9.3 The Set-covering Problem 9.4 The Traveling-salesman Problem9.5 Randomization and Linear Programming 9.6 The Subset-sum Problem提要 參考資料Introduction to Algorithms 第35章網(wǎng)站資料 第9章9.1 Introdution近似算法的基本概念近似算法的性能分析近似算法的基本思

2、想很多實(shí)際應(yīng)用中問(wèn)題都是NP-完全問(wèn)題NP-完全問(wèn)題的多項(xiàng)式算法是難以得到的求解NP-完全問(wèn)題的方法:如果問(wèn)題的輸入很小, 可以使用指數(shù)級(jí)算法圓滿地解決該問(wèn)題否則使用多項(xiàng)式算法求解問(wèn)題的近似優(yōu)化解什么是近似算法能夠給出一個(gè)優(yōu)化問(wèn)題的近似優(yōu)化解的算法近似算法主要解決優(yōu)化問(wèn)題 近似算法的基本概念近似算法的時(shí)間復(fù)雜性分析目標(biāo)和方法與傳統(tǒng)算法相同近似算法解的近似度本節(jié)討論的問(wèn)題是優(yōu)化問(wèn)題問(wèn)題的每一個(gè)可能的解都具有一個(gè)正的代價(jià)問(wèn)題的優(yōu)化解可能具有最大或最小代價(jià)我們希望尋找問(wèn)題的一個(gè)近似優(yōu)化解我們需要分析近似解代價(jià)與優(yōu)化解代價(jià)的差距Ratio Bound 相對(duì)誤差 (1+)-近似近似算法的性能分析Rati

3、o Bound定義1(Ratio Bound) 設(shè)A是一個(gè)優(yōu)化問(wèn)題的近似 算法, A具有ratio bound p(n), 如果 其中n是輸入大小, C是A產(chǎn)生的解的代價(jià), C*是優(yōu)化解的代價(jià). 如果問(wèn)題是最大化問(wèn)題, maxC/C*, C*/C=C*/C如果問(wèn)題是最小化問(wèn)題, maxC/C*, C*/C=C/C*由于C/C*1, Ratio Bound不會(huì)小于1Ratio Bound越大, 近似解越壞相對(duì)誤差 定義2(相對(duì)誤差) 對(duì)于任意輸入, 近似算法的相對(duì) 誤差定義為|C-C*|/C*, 其中C是近似解的代 價(jià), C*是優(yōu)化解的代價(jià). 定義3(相對(duì)誤差界) 一個(gè)近似算法的相對(duì)誤差界 為(

4、n), 如果|C-C*|/C* (n).結(jié)論1. (n) p(n)-1. 證. 對(duì)于最小化問(wèn)題 (n)=|C-C*|/C*=(C-C*)/C*=C/C* -1=p(n)-1. 對(duì)于最大化問(wèn)題 (n)=|C-C*|/C*=(C*-C)/C*= (C*/C -1)/(C*/C) = (p(n)-1)/p(n) p(n)-1.對(duì)于某些問(wèn)題, (n)和p(n)獨(dú)立于n, 用p和表示之.某些NP-完全問(wèn)題的近似算法滿足: 當(dāng)運(yùn)行時(shí)間增 加時(shí)，Ratio Bound和相對(duì)誤差將減少.結(jié)論1表示, 只要求出了Ratio Bound就求出了(n)近似模式定義4 (近似模式) 一個(gè)優(yōu)化問(wèn)題的近似模式是一 個(gè)以問(wèn)

5、題實(shí)例I和0為輸入的算法. 對(duì)于任 意固定, 近似模式是一個(gè)(1+)-近似算法.定義5 一個(gè)近似模式A(I, )稱為一個(gè)多項(xiàng)式時(shí)間 近似模式, 如果對(duì)于任意0, A(I, )的運(yùn)行 時(shí)間是|I|的多項(xiàng)式.定義 6 一個(gè)近似模式稱為完全多項(xiàng)式時(shí)間近似模 式, 如果它的運(yùn)行時(shí)間是關(guān)于1/和輸入實(shí) 例大小n的多項(xiàng)式. 9.2 The Vetex-cover Problem 問(wèn)題的定義近似算法的設(shè)計(jì)算法的性能分析問(wèn)題的定義輸入: 無(wú)向圖G=(V, E)輸出: CV, 滿足 (1). (u, v)E, uC或者vC (2). C是滿足條件(1)的最小集合。 理論上已經(jīng)證明優(yōu)化結(jié)點(diǎn) 覆蓋問(wèn)題是NP-完全問(wèn)

6、題. 算法的基本思想近似算法的設(shè)計(jì)bacfdegbacfdegbacfdegbcdgef算法解: b, c, e, f, d, gbacfdeg優(yōu)化解: b, e, d算法APPROX-Vertex-Cover (G)1. C=02. E=EG;3. While E0 DO 任取(u, v)E; C=Cu, v; 從E中刪除所有與u或v相連的邊;Roturn C時(shí)間復(fù)雜性T(G)=O(|E|) Ratio Bound 定理. Approx-Vertex-Cover的Ratio Bound為2. 證. 令A(yù)=(u, v) | (u, v)是算法第4步選中的邊. 若(u,v)A, 則與(u, v)

7、鄰接的邊皆從E中刪除. 于是, A中無(wú)相鄰接邊. 第5步的每次運(yùn)行增加兩個(gè)結(jié)點(diǎn)到C, C=2A. 設(shè)C*是優(yōu)化解, C*必須覆蓋A. 由于A中無(wú)鄰接邊, C*至少包含A中每條邊的一 個(gè)結(jié)點(diǎn). 于是, AC*, C=2|A|2C*, 即|C|/|C*|2. 算法的性能分析9.3 The Set-covering Problem 問(wèn)題的定義近似算法的設(shè)計(jì)算法的性能分析輸入: 有限集X, X的所有子集族F, X=SF S輸出: CF，滿足 (1). X=SC S , (2). C是滿足條件(1)的最小集族, 即|C|最小.*最小集合覆蓋問(wèn)題是很多實(shí)際問(wèn)題的抽象.*最小集合覆蓋問(wèn)題是NP-完全問(wèn)題.問(wèn)

8、題的定義S1S2S3S4S5S6X=12個(gè)黑點(diǎn), F=S1, S2, S3, S4, S5, S6優(yōu)化解C=S3, S4, S5問(wèn)題的實(shí)例 S1S2S3S4S5S6基本思想貪心選擇:選擇能覆蓋最多未被覆蓋元素的子集近似算法的設(shè)計(jì)S1S2S3S4S5S6C=S1, C=S1, S4, S1S2S3S4S5S6C=S1, S4, S5, S1S2S3S4S5S6C=S1, S4, S5, S3S1S2S3S4S5S6算法Greedy-Set-Cover(X, F)1. UX; /* U是X中尚未被覆蓋的元素集 */2. C;3. While U Do Select SF 使得SU最大; /* Gr

9、eedy選擇選擇能覆蓋最多U元素的子集S */5. U U-S;6. C CS; /* 構(gòu)造X的覆蓋 */7. Return C. 時(shí)間復(fù)雜性3-6的循環(huán)次數(shù)至多為min(X, F)計(jì)算SU需要時(shí)間O(X)第4步需要時(shí)間O(FX) T(X,F)=O(FXmin(x,F) 算法性能的分析Ration Bound定理1. 令H(d)=1id1/I . Greedy-Set-Covers是多項(xiàng)式 p(n)-近似算法, p(n)=H(maxS | SF). 證. 我們已經(jīng)算法是多項(xiàng)式算法, 僅需計(jì)算Ratio Bound. 設(shè)C*是優(yōu)化集合覆蓋, C*的代價(jià)是C*. 令Si是由Greedy-Set-C

10、over選中的第i個(gè)子集. 當(dāng)把Si加入C時(shí), C的代價(jià)加1. 我們把選擇Si增加的代 價(jià)均勻分配到由Si首次覆蓋的所有結(jié)點(diǎn). xX, 令cx是分配到x的代價(jià). 若x被Si首次覆蓋, 則 顯然, 算法給出的解C的代價(jià)為C, C平均地分布到X的所有點(diǎn). 由于C*也覆蓋X, 我們有 注意: 上式的小于成立是因?yàn)镃*中各子集可能相交, 某些cx被加了多次, 而左式每個(gè)cx只加一次. 如果SF, xS cxH(S)成立, 則 C SC* H(|S|)C*H(maxS | SF), 即|C|/|C*|H(maxS | SF), 定理成立. 下邊我們來(lái)證明: 對(duì)于SF, xS cxH(S). 對(duì)于SF和i

11、=1,2,.C, 令ui=S-(S1S2.Si)是S1、S2、.、Si被選中后, S中未被覆蓋的點(diǎn)數(shù). Si先于S被選中. 令u0=S, k是滿足下列條件的最小數(shù): uk=0, 即S中每個(gè)元素被S1、S2、.、Sk中至少一個(gè)覆蓋. 顯然, ui-1ui, ui-1-ui是S中由Si第一次覆蓋的元素?cái)?shù).于是, 注意: Si-(S1S2.Si-1)S-(S1S2.Si-1=ui-1, 因?yàn)镚reed算法保證: S不能覆蓋多于Si覆蓋的新結(jié)點(diǎn)數(shù), 否則S將在Si之前被選中. 于是,推論1. Greedy-Set-Cover是一個(gè)多項(xiàng)式ln(x+1)-近 似算法. 證. 由不等式H(n)ln(n+1)

12、可知 H(maxS | SF)H(X)lnX+1.復(fù)雜性分析9.4 The Traveling-salesman Problem問(wèn)題的定義近似算法設(shè)計(jì)算法的性能分析問(wèn)題的定義 輸入 完全無(wú)向圖G=(V,E); 代價(jià)函數(shù)C: E非負(fù)整數(shù)集合 C滿足三角不等式: C(u,w)C(u,v)+C(v,w). 輸出 具有最小代價(jià)的Hamilton環(huán) Hamilton環(huán)是一個(gè)包含V中每個(gè)結(jié)點(diǎn)一次的簡(jiǎn)單環(huán). 代價(jià)函數(shù)的擴(kuò)展: 設(shè)AE, C(A)=(u,v)E C(u, v). 不滿足三角不等式的TSP問(wèn)題無(wú)具有常數(shù)Ration Bound的近似算法, 除非NP=P.基本思想首先構(gòu)造最小生成樹(shù)(可以使用第五章

13、的算法)先序遍歷最小生成樹(shù), 構(gòu)造TSP的解近似算法的設(shè)計(jì)adebfghc先序遍歷: abchdefgaadebfghc先序遍歷解優(yōu)化解debcgfha 近似算法 APPROX-TSP-TOUR(G,C) 1. 選擇一個(gè)rVG作為生成樹(shù)的根; 2. 調(diào)用MST-Prim(G, C, r)生成一個(gè)最小生成樹(shù)T; 3. 先序遍歷T, 形成有序結(jié)點(diǎn)表L; 4. 按照L中的順序訪問(wèn)各結(jié)點(diǎn), 形成哈密頓環(huán).算法的性能分析 時(shí)間復(fù)雜性 第2步: O(|E|+|V|log|V|)=O(|V|2+|V|log|V|)=O(|V|2) 第3步: O(|E|)=O(|V|2), 因?yàn)镚是完全圖, 第4步: O(|

14、V|) T(G)=O(|V|2)解的精確度 定理1. APPROX-TSP-TOUR具有Ratio Bound 2. 證. 設(shè)H*是TSP問(wèn)題的優(yōu)化解, H是算法產(chǎn)生的近似解.我們需要證明C(H)2C(H*). 從H*中刪除任意一條邊, 可以得到G的一個(gè)生成樹(shù)T. 設(shè)T是算法第2步產(chǎn)生的導(dǎo)致H的最小生成樹(shù), 則 C(T)C(T)C(H*). T的一個(gè)full walk W列出了所有結(jié)點(diǎn)(第一次訪問(wèn)的和 以后從一個(gè)子樹(shù)返回時(shí)再訪問(wèn)的). 前面例子的full walk給 出順序: a,b,c,b,h,b,a,d,e,f,e,g,e,d,a 由于W通過(guò)每條邊兩次, C(W)=2C(T), 進(jìn)而C(W

15、)2C(H*). W不是哈密頓環(huán), 因?yàn)樗ㄟ^(guò)某些結(jié)點(diǎn)多于一次. 根據(jù)三角不等式, 我們可以從W中刪除對(duì)一個(gè)結(jié)點(diǎn)的任何 訪問(wèn), 而不增加代價(jià). (例如：從uvw 刪除v得uw) 反復(fù)地應(yīng)用上述操作, 我們可以從W中刪除所有對(duì)任何結(jié)點(diǎn)的非第一次訪問(wèn), 得到一個(gè)算法中的preoder walk. 在我們的例子中, 操作結(jié)果是: a, b, c, h, d, e, f, g. 由于T的preoder walk導(dǎo)致H, 我們有C(H)C(W), 即 C(H)2C(H*), 明所欲證.9.5 Randomization and Linear Programming求解Max-3-CNF問(wèn)題隨機(jī)近似算法求

16、解最小節(jié)點(diǎn)覆蓋問(wèn)題的線性規(guī)劃算法基本概念定義1. 設(shè)C是隨機(jī)近似算法RAS產(chǎn)生的問(wèn)題P的近似 解的代價(jià), C*是問(wèn)題P的準(zhǔn)確解的代價(jià), n是P 的大小. 若max(C/C*, C*/C)p(n), 則稱RSA 具有近似比p(n). 我們也稱RAS是一個(gè)隨機(jī) p(n)-近似算法.求解Max-3-CNF問(wèn)題隨機(jī)近似算法Max-3-CNF問(wèn)題的定義輸入: 合取范式CNF, 每個(gè)析取式具有三個(gè)變量, 沒(méi)有任何變量和它的非在同一個(gè)析取式中輸出: 一個(gè)變量賦值,最大化值為1的析取式個(gè)數(shù)隨機(jī)算法 Random-Max-3-CNF(CNF)For 對(duì)于CNF中的每個(gè)變量x Do 隨機(jī)地為x賦值: x =0的概

17、率為1/2, x =1的概率為1/2;Return. 性能分析 定理. Random-Max-3-CNF是一個(gè)隨機(jī)8/7-近似算法. 證. 假定輸入CNF中具有n個(gè)變量, m個(gè)析取式, 第i個(gè)析取式的形式為 xi1xi2xi3. 對(duì)i=1, 2, m, 定義隨機(jī)變量: Yi=1 如果第i個(gè)析取式為1, 否則Yi=0. Pr(第i個(gè)析取式為0)=Pr(xi1=0)Pr(xi2=0)Pr(xi3=0)=(1/2)3=1/8. Pr(第i個(gè)析取式為1)=1- 1/8 = 7/8. EYi=7/8. 令Y=Y1+Y2+Ym. Y是CNF中值為1的析取式的個(gè)數(shù). EY=1imEYi=1im7/8=m7/

18、8. 顯然, 優(yōu)化解的代價(jià)為m. 于是近似比=m/(m7/8)=8/7 .問(wèn)題的定義輸入: 無(wú)向圖G=(V, E), 每個(gè)節(jié)點(diǎn)具有權(quán)w(v).輸出: CV, 滿足 (1). (u, v)E, uC或者vC (2). w(C)最小, w(C)=cCw(c).以前的節(jié)點(diǎn)覆蓋算法不再適用!求解節(jié)最小點(diǎn)覆蓋問(wèn)題的線性規(guī)劃算法問(wèn)題轉(zhuǎn)化為0-1線性規(guī)劃問(wèn)題P0-1對(duì)于vV, 定義 x(v)0, 1如下:若v在節(jié)點(diǎn)覆蓋中, 則x(v)=1, 否則x(v)=0.(u, v)E, 若u、v或兩者在覆蓋中, 則x(u)+x(v)1. 對(duì)應(yīng)的0-1整數(shù)規(guī)劃問(wèn)題P0-1優(yōu)化目標(biāo): 最小化 vV w(v)x(v)約束條

19、件: x(u)+x(v)1 for vV x(v)0, 1 for vV 0-1整數(shù)規(guī)劃問(wèn)題是NP-完全問(wèn)題 我們需要設(shè)計(jì)近似算法用線性規(guī)劃問(wèn)題的解近似0-1規(guī)劃問(wèn)題的解對(duì)于vV, 定義 x(v)0, 1 P0-1對(duì)應(yīng)的線性規(guī)劃問(wèn)題LP優(yōu)化目標(biāo): 最小化 vV w(v)x(v)約束條件: x(u)+x(v)1 for vV x(v)0, 1 for vV 線性規(guī)劃問(wèn)題具有多項(xiàng)式時(shí)間算法 P0-1的可能解是LP問(wèn)題的可能解 P0-1解的代價(jià)LP的解的代價(jià)近似算法Approx-Min-VC(G, w) C=0; 計(jì)算LP問(wèn)題的優(yōu)化解y; For each vV Do If x(v)1/2 Then

20、 C=Cv; /* 用四舍五入法把LP的解近似為P0-1的解 */5. Return C.算法的性能定理. Approx-Min-VC是一個(gè)多項(xiàng)式時(shí)間2-近似算法 證. 由于求解LP需多項(xiàng)式時(shí)間, Approx-Min-VC的For循環(huán)需要多項(xiàng)式時(shí)間, 所以算法需要多項(xiàng)式時(shí)間. 下邊證明Approx-Min-VC的近似比是2. 往證算法產(chǎn)生的C是一個(gè)節(jié)點(diǎn)覆蓋. (u, v)E, 由約束條件可知 x(u)+x(v)1. 于是, x(u)和x(v)至少一個(gè)大于等于1/2, 即u、v或兩者在C中. C是一個(gè)覆蓋. 往證w(C)/w(C*) 2. 令C*是P0-1的優(yōu)化解, z*是LP優(yōu)化解的代價(jià).

21、因?yàn)镃*是LP的可能解, w(C*)z*. z* = vV w(v)x(v) vV: x(v)1/2 w(v)x(v) vV: x(v)1/2 w(v)1/2 = vC w(v)1/2 = (1/2) vC w(v) = (1/2)w(C). 由w(C*)z*, w(C*)(1/2)w(C), 即 w(C)/w(c*)2. 9.6 The Subset-sum Problem 問(wèn)題的定義 指數(shù)時(shí)間算法 完全多項(xiàng)式時(shí)間近似模式 輸入: (S, t), S=x1, x2, ., xn, xi是整數(shù), t=正整數(shù)輸出: xA x, 滿足: AS, xAxt xA x =max xB x | BS 問(wèn)

22、題定義算法 (設(shè)S是集合, x是正整數(shù), 定義S+x=s+x sS) Exact-Subset-Sum(S =x1, x2, ., xn, t) 1. nS; 2. L0; 3. For i1 To n Do 4. LiMerge-List(Li-1, Li-1+xi); 5. 刪除Li中所有大于t的元素; 6. Return Ln中最大元素.指數(shù)時(shí)間算法計(jì)算過(guò)程：L0=L1= /* 前一個(gè)元素所有子集的和(不大于t) */ L2= /* 前二個(gè)元素所有子集的和(不大于t) */L3= /* 前三個(gè)元素所有子集的和(不大于t) */Li=前i個(gè)元素所有子集的和(不大于t)對(duì)n作數(shù)學(xué)歸納法可以證

23、明:Ln=前n個(gè)元素所有子集的和(不大于t) 時(shí)間復(fù)雜性 第4步: |Li|=2|Li-1|+12|Li-1|22|Li-2|2i|L0|=2i T(n)=O(2n) 如果t比較大 1. nS; 2. L0; 3. For i1 To n Do 4. LiMerge-List(Li-1, Li-1+xi); 5. 刪除Li中所有大于t的元素; 6. Return Ln中最大元素.基本思想: 修剪L, 對(duì)于多個(gè)相近元素, 只留一個(gè)代表, 盡量縮小每個(gè)L的長(zhǎng)度設(shè)(01)是修剪參數(shù), 根據(jù)修剪L:(1). 從L中刪除盡可能多的元素,(2). 如果L是L修剪后的結(jié)果, 則對(duì)每個(gè)從L中刪除的元 素y,

24、L中存在一個(gè)元素zy, 使得 (1-)yzy如果y被修剪掉, 則存在一個(gè)代表y的z在L中, 而且z相對(duì)于y的相對(duì)誤差小于.完全多項(xiàng)式時(shí)間近似模式修剪算法Trim(L=y1, y2, ., ym,) /* yiyi+1, 01, 輸出縮小的表L. */mL; L;lasty1;For i2 To m Do If last(1-)yi /*即yi-1(1-)yi, 由L和L有序, 對(duì)yL, 不滿足(1-)yiyyi */ Then yi加入到L末尾; /* 因L中目前沒(méi)有能夠表示yi的元素 */ lastyi;Return L .復(fù)雜性: O(L)=O(m)完全多項(xiàng)式近似模式輸入: S=x1, x

25、2, ., xn, t 0, 0 1輸出: 近似解zApprox-Subset-Sum(S, t, )1. nS;2. L03. For i1 To n Do4. LiMerge-List(Li-1, Li-1+xi);5. LiTrim(Li, /n) /* 修剪參數(shù)= /n */6. 從Li中刪除大于t的元素;7. 令z是Ln中最大值;8. Return z . 性能分析定理1. Approx-Subset-Sum是子集求和問(wèn)題的一個(gè)完 全多項(xiàng)式時(shí)間近似模式. 證.令P0=0, Pi=x x=yA y, Ax1, x2, ., xi. 例如, 令S=1, 4, 5, 則 P1=0, 1, P2=0, 1, 4, 5, P3=0, 1, 4, 5, 6, 9, 10. 使用數(shù)學(xué)歸納法可以證明: Pi=Pi-1(Pi-1+xi). 使用數(shù)學(xué)歸納法可以證明Li是Pi中所有不大于t的元素 的有序表. Li經(jīng)第5步修剪以及第6步的大于t元素的刪除, 仍然有LiPi. 于是, 第8步返回的z是S的某個(gè)子集的和. 我們需證明 (1). C*(1-)z, 即(C*-z)/C*, C*是優(yōu)化解, z是近似解. 注意, 由于子集合求和問(wèn)題是最大化問(wèn)題, (C*-z)/C*是算法的相對(duì)誤差. (2). 算法是關(guān)于S和1/的多項(xiàng)式時(shí)間算法. (1). 往證C*