近似算法概述課件

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

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

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

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

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

算法approxVertexCover的性能比為2。（c=6，c*=3）62頂點(diǎn)覆蓋問(wèn)題的近似算法圖(a)～(e)說(shuō)明了算法的運(yùn)行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旅行售貨員問(wèn)題近似算法問(wèn)題描述：給定一個(gè)完全無(wú)向圖G=(V,E)，其每一邊(u,v)∈E有非負(fù)整數(shù)費(fèi)用c(u,v)。要找出G的最小費(fèi)用哈密頓回路。比如，費(fèi)用函數(shù)c往往具有三角不等式性質(zhì)，即對(duì)任意的3個(gè)頂點(diǎn)u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。當(dāng)圖G中的頂點(diǎn)就是平面上的點(diǎn)，任意2頂點(diǎn)間的費(fèi)用就是這2點(diǎn)間的歐氏距離時(shí)，費(fèi)用函數(shù)c就具有三角不等式性質(zhì)。

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

113.1旅行售貨員問(wèn)題近似算法對(duì)于給定的無(wú)向圖G，可以12

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

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

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

143.2一般的旅行售貨員問(wèn)題在費(fèi)用函數(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子集和問(wèn)題問(wèn)題描述：設(shè)子集和問(wèn)題的一個(gè)實(shí)例為〈S,t〉。其中，S={x1，x2，…，xn}是一個(gè)正整數(shù)的集合，t是一個(gè)正整數(shù)。子集和問(wèn)題判定是否存在S的一個(gè)子集S1，使得。164子集和問(wèn)題問(wèn)題描述：設(shè)子集和問(wèn)題的一個(gè)實(shí)例為〈S,174.1子集和問(wèn)題的指數(shù)時(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]中超過(guò)t的元素；}

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

子集和問(wèn)題的近似算法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]中超過(guò)t的元素；}

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

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

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

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

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

算法approxVertexCover的性能比為2。（c=6，c*=3）62頂點(diǎn)覆蓋問(wèn)題的近似算法圖(a)～(e)說(shuō)明了算法的運(yùn)行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旅行售貨員問(wèn)題近似算法問(wèn)題描述：給定一個(gè)完全無(wú)向圖G=(V,E)，其每一邊(u,v)∈E有非負(fù)整數(shù)費(fèi)用c(u,v)。要找出G的最小費(fèi)用哈密頓回路。比如，費(fèi)用函數(shù)c往往具有三角不等式性質(zhì)，即對(duì)任意的3個(gè)頂點(diǎn)u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。當(dāng)圖G中的頂點(diǎn)就是平面上的點(diǎn)，任意2頂點(diǎn)間的費(fèi)用就是這2點(diǎn)間的歐氏距離時(shí)，費(fèi)用函數(shù)c就具有三角不等式性質(zhì)。

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

113.1旅行售貨員問(wèn)題近似算法對(duì)于給定的無(wú)向圖G，可以39

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

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

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

143.2一般的旅行售貨員問(wèn)題在費(fèi)用函數(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子集和問(wèn)題問(wèn)題描述：設(shè)子集和問(wèn)題的一個(gè)實(shí)例為〈S,t〉。其中，S={x1，x2，…，xn}是一個(gè)正整數(shù)的集合，t是一個(gè)正整數(shù)。子集和問(wèn)題判定是否存在S的一個(gè)子集S1，使得。164子集和問(wèn)題問(wèn)題描述：設(shè)子集和問(wèn)題的一個(gè)實(shí)例為〈S,444.1子集和問(wèn)題的指數(shù)時(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]中超過(guò)t的元素；}

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

子集和問(wèn)題的近似算法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]中超過(guò)t的元素；}

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

Tradeoffbetweencomputationtimeandthequalityoftheapproximation

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

Example:O(n2/∈).

an