算法設計與分析ch9

1、第九章 Approximation Algorithm駱吉洲計算機科學與工程系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、想很多實際應用中問題都是NP-完全問題NP-完全問題的多項式算法是難以得到的求解NP-完全問題的方法:如果問題的輸入很小, 可以使用指數(shù)級算法圓滿地解決該問題否則使用多項式算法求解問題的近似優(yōu)化解什么是近似算法能夠給出一個優(yōu)化問題的近似優(yōu)化解的算法近似算法主要解決優(yōu)化問題 近似算法的基本概念近似算法的時間復雜性分析目標和方法與傳統(tǒng)算法相同近似算法解的近似度本節(jié)討論的問題是優(yōu)化問題問題的每一個可能的解都具有一個正的代價問題的優(yōu)化解可能具有最大或最小代價我們希望尋找問題的一個近似優(yōu)化解我們需要分析近似解代價與優(yōu)化解代價的差距Ratio Bound 相對誤差 (1+)-近似近似算法的性能分析Rati

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

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

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

6、題. 算法的基本思想近似算法的設計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時間復雜性T(G)=O(|E|) Ratio Bound 定理. Approx-Vertex-Cover的Ratio Bound為2. 證. 令A=(u, v) | (u, v)是算法第4步選中的邊. 若(u,v)A, 則與(u, v)

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

8、題的定義S1S2S3S4S5S6X=12個黑點, F=S1, S2, S3, S4, S5, S6優(yōu)化解C=S3, S4, S5問題的實例 S1S2S3S4S5S6基本思想貪心選擇:選擇能覆蓋最多未被覆蓋元素的子集近似算法的設計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; /* 構造X的覆蓋 */7. Return C. 時間復雜性3-6的循環(huán)次數(shù)至多為min(X, F)計算SU需要時間O(X)第4步需要時間O(FX) T(X,F)=O(FXmin(x,F) 算法性能的分析Ration Bound定理1. 令H(d)=1id1/I . Greedy-Set-Covers是多項式 p(n)-近似算法, p(n)=H(maxS | SF). 證. 我們已經(jīng)算法是多項式算法, 僅需計算Ratio Bound. 設C*是優(yōu)化集合覆蓋, C*的代價是C*. 令Si是由Greedy-Set-C

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

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

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

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

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

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

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

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

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

19、件: x(u)+x(v)1 for vV x(v)0, 1 for vV 0-1整數(shù)規(guī)劃問題是NP-完全問題 我們需要設計近似算法用線性規(guī)劃問題的解近似0-1規(guī)劃問題的解對于vV, 定義 x(v)0, 1 P0-1對應的線性規(guī)劃問題LP優(yōu)化目標: 最小化 vV w(v)x(v)約束條件: x(u)+x(v)1 for vV x(v)0, 1 for vV 線性規(guī)劃問題具有多項式時間算法 P0-1的可能解是LP問題的可能解 P0-1解的代價LP的解的代價近似算法Approx-Min-VC(G, w) C=0; 計算LP問題的優(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是一個多項式時間2-近似算法 證. 由于求解LP需多項式時間, Approx-Min-VC的For循環(huán)需要多項式時間, 所以算法需要多項式時間. 下邊證明Approx-Min-VC的近似比是2. 往證算法產生的C是一個節(jié)點覆蓋. (u, v)E, 由約束條件可知 x(u)+x(v)1. 于是, x(u)和x(v)至少一個大于等于1/2, 即u、v或兩者在C中. C是一個覆蓋. 往證w(C)/w(C*) 2. 令C*是P0-1的優(yōu)化解, z*是LP優(yōu)化解的代價.

21、因為C*是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 問題的定義 指數(shù)時間算法 完全多項式時間近似模式 輸入: (S, t), S=x1, x2, ., xn, xi是整數(shù), t=正整數(shù)輸出: xA x, 滿足: AS, xAxt xA x =max xB x | BS 問

22、題定義算法 (設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ù)時間算法計算過程：L0=L1= /* 前一個元素所有子集的和(不大于t) */ L2= /* 前二個元素所有子集的和(不大于t) */L3= /* 前三個元素所有子集的和(不大于t) */Li=前i個元素所有子集的和(不大于t)對n作數(shù)學歸納法可以證

23、明:Ln=前n個元素所有子集的和(不大于t) 時間復雜性 第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, 對于多個相近元素, 只留一個代表, 盡量縮小每個L的長度設(01)是修剪參數(shù), 根據(jù)修剪L:(1). 從L中刪除盡可能多的元素,(2). 如果L是L修剪后的結果, 則對每個從L中刪除的元 素y,

24、L中存在一個元素zy, 使得 (1-)yzy如果y被修剪掉, 則存在一個代表y的z在L中, 而且z相對于y的相對誤差小于.完全多項式時間近似模式修剪算法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有序, 對yL, 不滿足(1-)yiyyi */ Then yi加入到L末尾; /* 因L中目前沒有能夠表示yi的元素 */ lastyi;Return L .復雜性: O(L)=O(m)完全多項式近似模式輸入: 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是子集求和問題的一個完 全多項式時間近似模式. 證.令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ù)學歸納法可以證明: Pi=Pi-1(Pi-1+xi). 使用數(shù)學歸納法可以證明Li是Pi中所有不大于t的元素 的有序表. Li經(jīng)第5步修剪以及第6步的大于t元素的刪除, 仍然有LiPi. 于是, 第8步返回的z是S的某個子集的和. 我們需證明 (1). C*(1-)z, 即(C*-z)/C*, C*是優(yōu)化解, z是近似解. 注意, 由于子集合求和問題是最大化問題, (C*-z)/C*是算法的相對誤差. (2). 算法是關于S和1/的多項式時間算法. (1). 往證C*