近似算法概述課件

1近似算法ApproximationAlgorithms1近似算法ApproximationAlgorithms2近似算法迄今為止，所有的NP完全問題都還沒有多項式時間算法。對于這類問題，通?？刹扇∫韵聨追N解題策略。(1)只對問題的特殊實例求解(2)用動態(tài)規(guī)劃法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用啟發(fā)式方法求解本章主要討論解NP完全問題的近似算法。2近似算法迄今為止，所有的NP完全問題都還沒有多項式時間主要內(nèi)容近似算法的性能定義頂點覆蓋問題旅行售貨商(TSP)問題子集和問題近似方案：(完全)多項式近似方案3主要內(nèi)容近似算法的性能定義341近似算法的性能若一個最優(yōu)化問題的最優(yōu)值為c*，求解該問題的一個近似算法求得的近似最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值為c，則將該近似算法的性能比定義為=。在通常情況下，該性能比是問題輸入規(guī)模n的一個函數(shù)ρ(n)。該近似算法的相對誤差定義為=。若對問題的輸入規(guī)模n，有一函數(shù)ε(n)使得≤ε(n)，則稱ε(n)為該近似算法的相對誤差界。近似算法的性能比ρ(n)與相對誤差界ε(n)之間有如下關(guān)系：ε(n)≤ρ(n)-1。41近似算法的性能若一個最優(yōu)化問題的最優(yōu)值為c*，求解該問52頂點覆蓋問題的近似算法問題描述：無向圖G=(V,E)的頂點覆蓋是它的頂點集V的一個子集V’V，使得若(u,v)是G的一條邊，則v∈V’或u∈V’。頂點覆蓋V’的大小是它所包含的頂點個數(shù)|V’|。頂點覆蓋問題：找最小頂點覆蓋。

VertexSetApproxVertexCover(GraphG){Cset=；E1=E；while(E1!=){

從E1中任取一條邊e=(u,v)；Cset=Cset∪{u,v}；

從E1中刪去與u和v相關(guān)聯(lián)的所有邊；}

returnCset}Cset用來存儲頂點覆蓋中的各頂點。初始為空，不斷從邊集E1中選取一邊(u,v)，將邊的端點加入Cset中，并將E1中已被u和v覆蓋的邊刪去，直至Cset已覆蓋所有邊。即E1為空。52頂點覆蓋問題的近似算法問題描述：無向圖G=(V,E)62頂點覆蓋問題的近似算法圖(a)～(e)說明了算法的運行過程及結(jié)果。(e)表示算法產(chǎn)生的近似最優(yōu)頂點覆蓋Cset，它由頂點b,c,d,e,f,g所組成。(f)是圖G的一個最小頂點覆蓋，它只含有3個頂點：b,d和e。

算法approxVertexCover的性能比為2。（c=6，c*=3）62頂點覆蓋問題的近似算法圖(a)～(e)說明了算法的運行7近似比:2-ApproximationTheorem.AlgorithmApproxVertexCoverisa2-approximationalgorithm.Pf.

LetAdenotethesetofedgesthatwerepickedbyAlgorithmApproxVertexCover.LetC*beanoptimalvertexcover.Then,C*mustincludeatleastoneendpointofeachedgeinA.SincenotwoedgesinAshareanendpoint,notwoedgesinAarecoveredbythesamevertexfromC*.HencewehavethelowerboundC*≥|A|.Ontheotherhand,thealgorithmpicksanedgeforwhichneitherofitsendpointsisalreadyinC.Then|C|=2|A|Hence,|C|=2|A|

≤2|C*|.

7近似比:2-ApproximationTheorem.8Vertexcover:summaryNobetterconstant-factorapproximationisknown!!Moreprecisely,minimumvertexcoverisknowntobeapproximablewithin(foragiven|V|≥2)(ADM85)

butcannotbeapproximatedwithin7/6(HastadSTOC97)foranysufficientlylargevertexdegree,DinurSafra(STOC02)1.360678Vertexcover:summaryNobette9Vertexcover:summaryEranHalperin,ImprovedApproximationAlgorithmsfortheVertexCoverProbleminGraphsandHypergraphs,SIAMJournalonComputing,31/5

(2002):1608-1623

.TomokazuImamura,KazuoIwama,Approximatingvertexcoverondensegraphs,ProceedingsofthesixteenthannualACM-SIAMsymposiumonDiscretealgorithms20059Vertexcover:summaryEranHal103旅行售貨員問題近似算法問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有非負整數(shù)費用c(u,v)。要找出G的最小費用哈密頓回路。比如，費用函數(shù)c往往具有三角不等式性質(zhì)，即對任意的3個頂點u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。當(dāng)圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函數(shù)c就具有三角不等式性質(zhì)。

旅行售貨員問題的一些特殊性質(zhì)：103旅行售貨員問題近似算法問題描述：給定一個完全無向圖113.1旅行售貨員問題近似算法對于給定的無向圖G，可以利用找圖G的最小生成樹的算法設(shè)計找近似最優(yōu)的旅行售貨員回路的算法。voidApproxTSP(GraphG){(1)選擇G的任一頂點r；(2)用Prim算法找出帶權(quán)圖G的一棵以r為根的最小生成樹T；(3)前序遍歷樹T得到的頂點表L；(4)將r加到表L的末尾，按表L中頂點次序組成回路H，作為計 算結(jié)果返回；}當(dāng)費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。

113.1旅行售貨員問題近似算法對于給定的無向圖G，可以12

PreorderTraversalPreorder:(root-left-right)Visittherootfirst;andthentraversetheleftsubtree;andthentraversetherightsubtree.Example:Order:A,B,C,D,E,F,G,H,I12PreorderTraversalPreord133.1

旅行售貨員問題舉例(b)表示找到的最小生成樹T；(c)表示對T作前序遍歷的次序；(d)表示L產(chǎn)生的哈密頓回路H，作為近似解；(e)是G的一個最小費用旅行售貨員回路的最優(yōu)解。

133.1 旅行售貨員問題舉例(b)表示找到的最小生成樹143.2一般的旅行售貨員問題在費用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多項式時間近似算法，除非P=NP。換句話說，若P≠NP，則對任意常數(shù)ρ>1，不存在性能比為ρ的解旅行售貨員問題的多項式時間近似算法。

143.2一般的旅行售貨員問題在費用函數(shù)不一定滿足三角不152-approximationTheorem.

ApproxTSPisapolynomial-time2-approximationalgorithmforthetraveling-salesmanproblemwiththetriangleinequality.

Pf.

LetCOPTbetheoptimalcycle

Cost(T)≤Cost(COPT)

RemovinganedgefromHgivesaspanningtree,Tisaspanningtreeofminimumcost

Cost(W)=2Cost(T)

Eachedgevisitedtwice

Cost(H)≤Cost(W)

TriangleinequalityCost(H)≤2Cost(COPT)152-approximationTheorem.Appr164子集和問題問題描述：設(shè)子集和問題的一個實例為〈S,t〉。其中，S={x1，x2，…，xn}是一個正整數(shù)的集合，t是一個正整數(shù)。子集和問題判定是否存在S的一個子集S1，使得。164子集和問題問題描述：設(shè)子集和問題的一個實例為〈S,174.1子集和問題的指數(shù)時間算法intExactSubsetSum(S,t){intn=|S|；L[0]={0}；for(inti=1；i<=n；i++){L[i]=MergeLists(L[i-1],L[i-1]+S[i])；

刪去L[i]中超過t的元素；}

returnmax(L[n])；}算法以集合S={x1，x2，…，xn}和目標(biāo)值t作為輸入。算法中用到將2個有序表L1和L2合并成為一個新的有序表的算法MergeLists(L1,L2)。174.1子集和問題的指數(shù)時間算法intExactSu185.2子集和問題的近似算法基于算法ExactSubsetSum，通過對表L[i]作適當(dāng)?shù)男拚⒁粋€子集和問題的完全多項式時間近似格式。在對表L[i]進行修整時，用到一個修整參數(shù)δ，0＜δ＜1。用參數(shù)δ修整一個表L是指從L中刪去盡可能多的元素，使得每一個從L中刪去的元素y，都有一個修整后的表L1中的元素z滿足(1-δ)y≤z≤y?？梢詫看作是被刪去元素y在修整后的新表L1中的代表。舉例：若δ=0.1，且L=〈10,11,12,15,20,21,22,23,24,29〉，則用δ對L進行修整后得到L1=〈10，12，15，20，23，29〉。其中被刪去的數(shù)11由10來代表，21和22由20來代表，24由23來代表。185.2子集和問題的近似算法基于算法ExactSubs195.2子集合問題的近似算法對有序表L修整算法ListTrim(L,δ){intm=|L|；L1=〈L[1]〉；intlast=L[1]；for(inti=2；i<=m；i++){if(last<(1-δ)*L[i]){

將L[i]加入表L1的尾部；

last=L[i]；}returnL1；}

子集和問題的近似算法intApproxSubsetSum(S,t,ε){n=|S|；L[0]=〈0〉；for(inti=1；i<=n；i++){L[i]=MergeLists(L[i-1], L[i-1]+S[i])；

L[i]=Trim(L[i],ε/n)；

刪去L[i]中超過t的元素；}

returnmax(L[n])；}195.2子集合問題的近似算法對有序表L修整算法List205ApproximationSchemeNP-completeproblemsallowpolynomial-timeapproximationalgorithmsthatcanachieveincreasinglysmallerapproximationratiosbyusingmoreandmorecomputationtime

Tradeoffbetweencomputationtimeandthequalityoftheapproximation

Foranyfixed∈>0,Anapproximationschemeforanoptimizationproblemisan(1+∈)-approximationalgorithm.205ApproximationSchemeNP-com215.1PTASandFPTASWesaythatanapproximationschemeisapolynomial-timeapproximationscheme(PTAS)ifforanyfixed∈>0,theschemerunsintimepolynomialinthesizenofitsinputinstance.

Example:O(n2/∈).

anapproximationschemeisafullypolynomial-timeapproximationscheme(FPTAS)ifitisanapproximationschemeanditsrunningtimeispolynomialbothin1/∈andinthesizenoftheinputinstanceExample:O((1/∈)2n3).

215.1PTASandFPTASWesayth22FPTAS：SUBSET-SUMTheorem.

APPROX-SUBSET-SUMisafullypolynomial-timeapproximationschemeforthesubset-sumproblem.TheoperationsoftrimmingLiandremovingfromLieveryelementthatisgreaterthantmaintainthepropertythateveryelementofLiisalsoamemberofPi.Therefore,thevaluez*returnedisindeedthesumofsomesubsetofS.

22FPTAS：SUBSET-SUMTheorem.APP23Pi,i=1,2,…,nForexample,ifS={1,4,5},thenP1={0,1},P2={0,1,4,5},P3={0,1,4,5,6,9,10}.Giventheidentity23Pi,i=1,2,…,nForexample,i24ProofofTheoremPf.Lety*denoteanoptimalsolutiontothesubset-sumproblem.weknowthatz*≤y*.Weneedtoshowthaty*/z*≤1+∈.Byinductiononi,itcanbeshownthatforeveryelementyinPithatisatmostt,thereisaz∈LisuchthatThus,thereisaz∈Ln,suchthat24ProofofTheoremPf.Lety*d25Pf.Con.Andthus,Hence,25Pf.Con.Andthus,26Pf.Con.ToshowFPTAS,weneedtoboundLi.Aftertrimming,successiveelementszandz′ofLimusthavetherelationshipz′/z>1+∈/2n

Eachlist,therefore,containsthevalue0,possiblythevalue1,andupto?log1+∈/2n

t?additionalvalues

26Pf.Con.ToshowFPTAS,weneTheEnd.

27TheEnd.

2728近似算法ApproximationAlgorithms1近似算法ApproximationAlgorithms29近似算法迄今為止，所有的NP完全問題都還沒有多項式時間算法。對于這類問題，通?？刹扇∫韵聨追N解題策略。(1)只對問題的特殊實例求解(2)用動態(tài)規(guī)劃法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用啟發(fā)式方法求解本章主要討論解NP完全問題的近似算法。2近似算法迄今為止，所有的NP完全問題都還沒有多項式時間主要內(nèi)容近似算法的性能定義頂點覆蓋問題旅行售貨商(TSP)問題子集和問題近似方案：(完全)多項式近似方案30主要內(nèi)容近似算法的性能定義3311近似算法的性能若一個最優(yōu)化問題的最優(yōu)值為c*，求解該問題的一個近似算法求得的近似最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值為c，則將該近似算法的性能比定義為=。在通常情況下，該性能比是問題輸入規(guī)模n的一個函數(shù)ρ(n)。該近似算法的相對誤差定義為=。若對問題的輸入規(guī)模n，有一函數(shù)ε(n)使得≤ε(n)，則稱ε(n)為該近似算法的相對誤差界。近似算法的性能比ρ(n)與相對誤差界ε(n)之間有如下關(guān)系：ε(n)≤ρ(n)-1。41近似算法的性能若一個最優(yōu)化問題的最優(yōu)值為c*，求解該問322頂點覆蓋問題的近似算法問題描述：無向圖G=(V,E)的頂點覆蓋是它的頂點集V的一個子集V’V，使得若(u,v)是G的一條邊，則v∈V’或u∈V’。頂點覆蓋V’的大小是它所包含的頂點個數(shù)|V’|。頂點覆蓋問題：找最小頂點覆蓋。

VertexSetApproxVertexCover(GraphG){Cset=；E1=E；while(E1!=){

從E1中任取一條邊e=(u,v)；Cset=Cset∪{u,v}；

從E1中刪去與u和v相關(guān)聯(lián)的所有邊；}

returnCset}Cset用來存儲頂點覆蓋中的各頂點。初始為空，不斷從邊集E1中選取一邊(u,v)，將邊的端點加入Cset中，并將E1中已被u和v覆蓋的邊刪去，直至Cset已覆蓋所有邊。即E1為空。52頂點覆蓋問題的近似算法問題描述：無向圖G=(V,E)332頂點覆蓋問題的近似算法圖(a)～(e)說明了算法的運行過程及結(jié)果。(e)表示算法產(chǎn)生的近似最優(yōu)頂點覆蓋Cset，它由頂點b,c,d,e,f,g所組成。(f)是圖G的一個最小頂點覆蓋，它只含有3個頂點：b,d和e。

算法approxVertexCover的性能比為2。（c=6，c*=3）62頂點覆蓋問題的近似算法圖(a)～(e)說明了算法的運行34近似比:2-ApproximationTheorem.AlgorithmApproxVertexCoverisa2-approximationalgorithm.Pf.

LetAdenotethesetofedgesthatwerepickedbyAlgorithmApproxVertexCover.LetC*beanoptimalvertexcover.Then,C*mustincludeatleastoneendpointofeachedgeinA.SincenotwoedgesinAshareanendpoint,notwoedgesinAarecoveredbythesamevertexfromC*.HencewehavethelowerboundC*≥|A|.Ontheotherhand,thealgorithmpicksanedgeforwhichneitherofitsendpointsisalreadyinC.Then|C|=2|A|Hence,|C|=2|A|

≤2|C*|.

7近似比:2-ApproximationTheorem.35Vertexcover:summaryNobetterconstant-factorapproximationisknown!!Moreprecisely,minimumvertexcoverisknowntobeapproximablewithin(foragiven|V|≥2)(ADM85)

butcannotbeapproximatedwithin7/6(HastadSTOC97)foranysufficientlylargevertexdegree,DinurSafra(STOC02)1.360678Vertexcover:summaryNobette36Vertexcover:summaryEranHalperin,ImprovedApproximationAlgorithmsfortheVertexCoverProbleminGraphsandHypergraphs,SIAMJournalonComputing,31/5

(2002):1608-1623

.TomokazuImamura,KazuoIwama,Approximatingvertexcoverondensegraphs,ProceedingsofthesixteenthannualACM-SIAMsymposiumonDiscretealgorithms20059Vertexcover:summaryEranHal373旅行售貨員問題近似算法問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有非負整數(shù)費用c(u,v)。要找出G的最小費用哈密頓回路。比如，費用函數(shù)c往往具有三角不等式性質(zhì)，即對任意的3個頂點u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。當(dāng)圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函數(shù)c就具有三角不等式性質(zhì)。

旅行售貨員問題的一些特殊性質(zhì)：103旅行售貨員問題近似算法問題描述：給定一個完全無向圖383.1旅行售貨員問題近似算法對于給定的無向圖G，可以利用找圖G的最小生成樹的算法設(shè)計找近似最優(yōu)的旅行售貨員回路的算法。voidApproxTSP(GraphG){(1)選擇G的任一頂點r；(2)用Prim算法找出帶權(quán)圖G的一棵以r為根的最小生成樹T；(3)前序遍歷樹T得到的頂點表L；(4)將r加到表L的末尾，按表L中頂點次序組成回路H，作為計 算結(jié)果返回；}當(dāng)費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。

113.1旅行售貨員問題近似算法對于給定的無向圖G，可以39

PreorderTraversalPreorder:(root-left-right)Visittherootfirst;andthentraversetheleftsubtree;andthentraversetherightsubtree.Example:Order:A,B,C,D,E,F,G,H,I12PreorderTraversalPreord403.1

旅行售貨員問題舉例(b)表示找到的最小生成樹T；(c)表示對T作前序遍歷的次序；(d)表示L產(chǎn)生的哈密頓回路H，作為近似解；(e)是G的一個最小費用旅行售貨員回路的最優(yōu)解。

133.1 旅行售貨員問題舉例(b)表示找到的最小生成樹413.2一般的旅行售貨員問題在費用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多項式時間近似算法，除非P=NP。換句話說，若P≠NP，則對任意常數(shù)ρ>1，不存在性能比為ρ的解旅行售貨員問題的多項式時間近似算法。

143.2一般的旅行售貨員問題在費用函數(shù)不一定滿足三角不422-approximationTheorem.

ApproxTSPisapolynomial-time2-approximationalgorithmforthetraveling-salesmanproblemwiththetriangleinequality.

Pf.

LetCOPTbetheoptimalcycle

Cost(T)≤Cost(COPT)

RemovinganedgefromHgivesaspanningtree,Tisaspanningtreeofminimumcost

Cost(W)=2Cost(T)

Eachedgevisitedtwice

Cost(H)≤Cost(W)

TriangleinequalityCost(H)≤2Cost(COPT)152-approximationTheorem.Appr434子集和問題問題描述：設(shè)子集和問題的一個實例為〈S,t〉。其中，S={x1，x2，…，xn}是一個正整數(shù)的集合，t是一個正整數(shù)。子集和問題判定是否存在S的一個子集S1，使得。164子集和問題問題描述：設(shè)子集和問題的一個實例為〈S,444.1子集和問題的指數(shù)時間算法intExactSubsetSum(S,t){intn=|S|；L[0]={0}；for(inti=1；i<=n；i++){L[i]=MergeLists(L[i-1],L[i-1]+S[i])；

刪去L[i]中超過t的元素；}

returnmax(L[n])；}算法以集合S={x1，x2，…，xn}和目標(biāo)值t作為輸入。算法中用到將2個有序表L1和L2合并成為一個新的有序表的算法MergeLists(L1,L2)。174.1子集和問題的指數(shù)時間算法intExactSu455.2子集和問題的近似算法基于算法ExactSubsetSum，通過對表L[i]作適當(dāng)?shù)男拚⒁粋€子集和問題的完全多項式時間近似格式。在對表L[i]進行修整時，用到一個修整參數(shù)δ，0＜δ＜1。用參數(shù)δ修整一個表L是指從L中刪去盡可能多的元素，使得每一個從L中刪去的元素y，都有一個修整后的表L1中的元素z滿足(1-δ)y≤z≤y。可以將z看作是被刪去元素y在修整后的新表L1中的代表。舉例：若δ=0.1，且L=〈10,11,12,15,20,21,22,23,24,29〉，則用δ對L進行修整后得到L1=〈10，12，15，20，23，29〉。其中被刪去的數(shù)11由10來代表，21和22由20來代表，24由23來代表。185.2子集和問題的近似算法基于算法ExactSubs465.2子集合問題的近似算法對有序表L修整算法ListTrim(L,δ){intm=|L|；L1=〈L[1]〉；intlast=L[1]；for(inti=2；i<=m；i++){if(last<(1-δ)*L[i]){

將L[i]加入表L1的尾部；

last=L[i]；}returnL1；}

子集和問題的近似算法intApproxSubsetSum(S,t,ε){n=|S|；L[0]=〈0〉；for(inti=1；i<=n；i++){L[i]=MergeLists(L[i-1], L[i-1]+S[i])；

L[i]=Trim(L[i],ε/n)；

刪去L[i]中超過t的元素；}

returnmax(L[n])；}195.2子集合問題的近似算法對有序表L修整算法List475ApproximationSchemeNP-completeproblemsallowpolynomial-timeapproximationalgorithmsthatcanachieveincreasinglysmallerapproximationratiosbyusingmoreandmorecomputationtime

Tradeoffbetweencomputationtimeandthequalityoftheapproximation

Foranyfixed∈>0,Anapproximationschemeforanoptimizationproblemisan(1+∈)-approximationalgorithm.205ApproximationSchemeNP-com485.1PTASandFPTASWesaythatanapproximationschemeisapolynomial-timeapproximationscheme(PTAS)ifforanyfixed∈>0,theschemerunsintimepolynomialinthesizenofitsinputinstance.

Example:O(n2/∈).

an