《Lecture12-近似算法》由会员分享，可在线阅读，更多相关《Lecture12-近似算法（39页珍藏版）》请在金锄头文库上搜索。
1、近似算法高文宇1近似算法一些NP完全问题存在多项式时间的近似算法，通过消耗越来越多的计算时间，这些近似算法可以达到不断缩小的近似比。也就是说，在计算时间和近似质量之间可以进行权衡，如子集和问题。2相关定义定义定义1.图G=(V,E)称为简单连通无向图，需满足以下条件：（1）G为无自回路的、连通的无向图。（2）G中任意两个节点之间至多有一条边。定义定义2.图中节点u和节点v之间存在一条边，则称节点与节点相邻。定义定义3.图中的任意节点u，称u在图中的相邻节点的个数为节点u的度数，记为d(u)。定义定义4. 点覆盖集。3点覆盖问题VertexCover:在给定图中找出最小点覆盖。4点覆盖的贪心算法
2、每次在剩余图中选择度最大的节点。5贪心策略不一定得到最好结果例如在下图中每次选择度大的节点将得到一个大小为5的点覆盖集，而最优解只需4个节点即可。6点覆盖的另一个近似算法2-近似APPROX-VERTEX-COVER(G)1C2EEG3whileE4dolet(u,v)beanarbitraryedgeofE5CCu,v6removefromEeveryedgeincidentoneitheruorv7returnC7APPROX-VERTEX-COVER算法执行过程近似解b,c,d,e,f,g最优解b,d,e8APPROX-VC是2-近似算法定理：APPROX-VC是2-近似算法。9点覆盖的
3、思考题35.1-3:ProfessorNixon提出使用贪心策略来求最小点覆盖，即每次选择度最大的节点。请给出一个例子说明这种策略达不到近似比2。(Hint:Tryabipartitegraphwithverticesofuniformdegreeontheleftandverticesofvaryingdegreeontheright.)35.1-4:设计一个贪心算法，在线性时间内找出一棵树树的最小点覆盖。35.1-5:从定理Theorem34.12的证明可知，点覆盖和团问题在某种意义上是互补的，即最小点覆盖是补图中某一最大团的补。这种关系是否意味着存在一个多项式的近似算法，它对团问题有着固
4、定的近似比？10关于点覆盖的开放问题对于点覆盖，存在近似比小于2的近似算法吗？11连通支配集问题ConnectedDominatingSet.连通支配集连通支配集.设图G=(V,E)是简单连通无向图，若节点集S是V的子集，S，对任意节点uV-S，u都与S中至少一个节点相邻，则称S是图G的支配集。若由S导出的子图为连通图，则S为连通支配集。在应用领域，我们通常希望求解最小CDS，即求得的CDS包含的节点数最少。然而，无论是求解最小支配集或最小CDS都是NP难问题，因此我们只能采用一些近似算法来求解这个问题。12连通支配集的贪心算法每次考虑度大的节点同时还需考虑连通性对偶的概念多叶子生成树13连通
5、支配集的难度尚未找到常数近似度的近似算法。支配集比点覆盖“更难”。14旅行商问题Traveling-salesman旅行商问题：给定一个完全无向图G，每条边用一非负权值表示代价，如何找出G的一个具有最小代价的哈密尔顿回路。TS问题是NP完全的，即使限定其代价函数满足三角不等式。15三角不等式三角不等式，triangle inequality：对所有节点u,v,wV,有：c(u,w)c(u,v)+c(v,w).则称代价函数c 满足三角不等式。在很多应用中，三角不等式自动满足，例如图的顶点为平面上的点，顶点间的旅行代价为顶点间的欧几里德距离。16满足三角不等式的TS问题求解思路（1）求出一棵MST
6、，MST的权值就是最低费用旅行线路的费用值的下界。（2）对MST进行先序遍历，所得节点序列即为TS巡游序列。17算法APPROX-TSP-TOUR(G,c)1selectavertexrVGtobearootvertex2computeaminimumspanningtreeTforGfromrootrusingMST-PRIM(G,c,r)3letLbethelistofverticesvisitedinapreordertreewalkofT4returnthehamiltoniancycleHthatvisitstheverticesintheorderL18TS算法执行过程Figure
7、35.2:TheoperationofAPPROX-TSP-TOUR.(a)Thegivensetofpoints,whichlieonverticesofanintegergrid.Forexample,fisoneunittotherightandtwounitsupfromh.Theordinaryeuclideandistanceisusedasthecostfunctionbetweentwopoints.(b)AminimumspanningtreeTofthesepoints,ascomputedbyMST-PRIM.Vertexaistherootvertex.Theverti
8、ceshappentobelabeledinsuchawaythattheyareaddedtothemaintreebyMST-PRIMinalphabeticalorder.(c)AwalkofT,startingata.Afullwalkofthetreevisitstheverticesintheordera, b, c, b, h, b, a, d, e, f, e, g, e, d, a.ApreorderwalkofTlistsavertexjustwhenitisfirstencountered,asindicatedbythedotnexttoeachvertex,yield
9、ingtheorderinga, b, c, h, d, e, f, g. (d)Atouroftheverticesobtainedbyvisitingtheverticesintheordergivenbythepreorderwalk.ThisisthetourHreturnedbyAPPROX-TSP-TOUR.Itstotalcostisapproximately19.074.(e)AnoptimaltourH*forthegivensetofvertices.Itstotalcostisapproximately14.715.近似解最优解19APPROX-TSP是2-近似Theor
10、em35.2:APPROX-TSP-TOURisapolynomial-time2-approximationalgorithmforthetraveling-salesmanproblemwiththetriangleinequality.尽管定理35.2给出了很好的近似比，但是在实践中，APPROX-TSP-TOUR通常并不是解决TS问题的最佳选择。有些近似算法的实际性能要比这个算法好得多，但这些算法却无法从理论上证明具有较小的近似比。20一般旅行商问题定理35.3：若PNP，则对任意常数1，一般旅行商问题不存在具有近似比的多项式时间近似算法。证明：用矛盾来证明。假设存在近似比为的近似算法
11、A，则我们可以说明如何在多项式时间内用A来解决哈密尔顿回路问题的各种实例。而哈密尔顿回路问题是NP完全的，因此这意味着P=NP。此即定理35.3的逆反命题。21-近似算法存在性证明设G=(V,E)是哈密顿回路问题的一个实例。我们希望通过假想的近似算法A来有效地确定G是否包含一个哈密顿回路。设G=(V,E)为V上的完全图，即E=(u,v):u,vVanduv.再对E中的每条边赋以一个整数代价如下：现在来考虑旅行商问题(G,c)。若原图G中存在一条哈密顿回路H，则代价函数c对H中的每条边赋以代价1，因而(G,c)包含一个代价为|V|的游程。另一方面，若G中不包含一个哈密顿回路，则G中的任何游程必定
12、用到不在E中的某条边。但是，任意一个用到不在E中边的游程的代价为：(|V|+1)+(|V|-1)=|V|+|V|V|.因为不在G中的边的代价如此之大，故G中哈密顿回路的游程代价与任何其它游程的代价之间相差至少为|V|。若将算法A应用于TSP问题(G,c)，由于A能返回不大于最优游程倍的游程。因此若A返回小于等于|V|的解，则图G中存在hamiltonian环，否则G中不包含hamiltonian环。22子集和问题子集和问题：子集和问题(S,t)，其中S是一个正整数集x1,x2,.,xn，t是一个正整数，问是否存在一个S的子集，使得该子集中的元素之和等于t。该问题是Knapsack问题的特例。在
13、优化问题中的描述是，求x1,x2,.,xn的一个子集，使得该子集中元素之和尽量接近，但又不超过t。23子集和的迭代计算及性质迭代计算子集和：在第i轮迭代计算中，计算集合x1,x2,.,xi的所有子集的元素和，计算的基础是集合x1,x2,.,xi-1的所有子集的和。性质：性质：在此计算过程中，一旦某个特定的子集S的和超过了t，就没必要在后继过程中对其进行处理了，因为S的超集都不会成为最优解。24EXACT-SUBSET-SUM算法EXACT-SUBSET-SUM的输入为S=x1,x2,.,xn和t。该算法迭代计算Li，即集合x1,.,xi所有子集的和，这些和值都不超过目标值t，最终的最优解即Ln
14、中的最大值。IfLisalistofpositiveintegersandxisanotherpositiveinteger,thenweletL+xdenotethelistofintegersderivedfromLbyincreasingeachelementofLbyx.Forexample,ifL=1,2,3,5,9,thenL+2=3,4,5,7,11.Wealsousethisnotationforsets,sothatS+x=s+x:sS.使用过程MERGE-LISTS(L,L)对两个有序表LandL进行归并，同时删除重复值。25EXACT-SUBSET-SUM算法EXACT-
15、SUBSET-SUM(S,t)1n|S|2L003fori1ton4doLiMERGE-LISTS(Li-1,Li-1+xi)5removefromLieveryelementthatisgreaterthant6returnthelargestelementinLn26示例ToseehowEXACT-SUBSET-SUMworks,letPidenotethesetofallvaluesthatcanbeobtainedbyselectinga(possiblyempty)subsetofx1,x2,.,xiandsummingitsmembers.Forexample,ifS=1,4,5,
16、thenP1=0,1P2=0,1,4,5P3=0,1,4,5,6,9,10.27算法的复杂度表Li是一个包含Pi中的所有值不大于t 的元素的有序表。因此的Li长度可大至2i，因此EXACT-SUBSET-SUM是一个指数时间算法。28一个完全多项式近似方案对子集和问题，我们可以导出一个fullypolynomial-timeapproximationscheme，通过修整（“trimming”）每次迭代产生的列表Li。其思想是若列表L中的两个值较为接近，那么出于需找近似解的目的，可以无需同时保留这两个数，而是用其中一个来代表所有与它接近的数。具体来说，我们引入参数（0last(1+)yilas
17、tbecauseLissorted6thenappendyiontotheendofL7lastyi8returnL30APPROX-SUBSET-SUM算法利用TRIM过程，给出一个近似算法，输入为S=x1,x2,.,xn和t，以及一个近似度参数，其满足01。算法返回一个值z，该值落在最优解的1+倍内。APPROX-SUBSET-SUM(S,t,)1n|S|2L003fori1ton4doLiMERGE-LISTS(Li-1,Li-1+xi)5LiTRIM(Li,/2n)6removefromLieveryelementthatisgreaterthant7letz*bethelargest
18、valueinLn8returnz*31示例假设S=104,102,201,101，t=308，=0.40。则为/8=0.05.算法执行过程如下。“linex”表示前面算法的对应行数。line2:L0=0,line4:L1=0,104,line5:L1=0,104,line6:L1=0,104,line4:L2=0,102,104,206,line5:L2=0,102,206,line6:L2=0,102,206,line4:L3=0,102,201,206,303,407,line5:L3=0,102,201,303,407,line6:L3=0,102,201,303,line4:L4=0
19、,101,102,201,203,302,303,404,line5:L4=0,101,201,302,404,line6:L4=0,101,201,302.Thealgorithmreturnsz*=302asitsanswer,whichiswellwithin=40%oftheoptimalanswer307=104+102+101;infact,itiswithin2%.32APPROX-SUBSET-SUM近似度定理35.8：APPROX-SUBSET-SUM是关于子集和问题的一个完全多项式时间近似方案（fullypolynomial-timeapproximationscheme）。证明：略。3334Steiner树问题的近似算法35363738再见再见39
