Lecture12-近似算法.ppt

1 近似算法 高文宇gwyy 2 近似算法 一些NP完全问题存在多项式时间的近似算法 通过消耗越来越多的计算时间 这些近似算法可以达到不断缩小的近似比 也就是说 在计算时间和近似质量之间可以进行权衡 如子集和问题 3 相关定义 定义1 图G V E 称为简单连通无向图 需满足以下条件 1 G为无自回路的 连通的无向图 2 G中任意两个节点之间至多有一条边 定义2 图中节点u和节点v之间存在一条边 则称节点与节点相邻 定义3 图中的任意节点u 称u在图中的相邻节点的个数为节点u的度数 记为d u 定义4 点覆盖集 4 点覆盖问题 VertexCover 在给定图中找出最小点覆盖 5 点覆盖的贪心算法 每次在剩余图中选择度最大的节点 6 贪心策略不一定得到最好结果 例如在下图中每次选择度大的节点将得到一个大小为5的点覆盖集 而最优解只需4个节点即可 7 点覆盖的另一个近似算法 2 近似APPROX VERTEX COVER G 1C 2E E G 3whileE 4dolet u v beanarbitraryedgeofE 5C C u v 6removefromE everyedgeincidentoneitheruorv7returnC 8 APPROX VERTEX COVER 算法执行过程 近似解 b c d e f g 最优解 b d e 9 APPROX VC是2 近似算法 定理 APPROX VC是2 近似算法 10 点覆盖的思考题 35 1 3 ProfessorNixon提出使用贪心策略来求最小点覆盖 即每次选择度最大的节点 请给出一个例子说明这种策略达不到近似比2 Hint Tryabipartitegraphwithverticesofuniformdegreeontheleftandverticesofvaryingdegreeontheright 35 1 4 设计一个贪心算法 在线性时间内找出一棵树的最小点覆盖 35 1 5 从定理Theorem34 12的证明可知 点覆盖和团问题在某种意义上是互补的 即最小点覆盖是补图中某一最大团的补 这种关系是否意味着存在一个多项式的近似算法 它对团问题有着固定的近似比 11 关于点覆盖的开放问题 对于点覆盖 存在近似比小于2的近似算法吗 12 连通支配集问题 ConnectedDominatingSet 连通支配集 设图G V E 是简单连通无向图 若节点集S是V的子集 S 对任意节点u V S u都与S中至少一个节点相邻 则称S是图G的支配集 若由S导出的子图为连通图 则S为连通支配集 在应用领域 我们通常希望求解最小CDS 即求得的CDS包含的节点数最少 然而 无论是求解最小支配集或最小CDS都是NP难问题 因此我们只能采用一些近似算法来求解这个问题 13 连通支配集的贪心算法 每次考虑度大的节点同时还需考虑连通性对偶的概念多叶子生成树 14 连通支配集的难度 尚未找到常数近似度的近似算法 支配集比点覆盖 更难 15 旅行商问题 Traveling salesman旅行商问题 给定一个完全无向图G 每条边用一非负权值表示代价 如何找出G的一个具有最小代价的哈密尔顿回路 TS问题是NP完全的 即使限定其代价函数满足三角不等式 16 三角不等式 三角不等式 triangleinequality 对所有节点u v w V 有 c u w c u v c v w 则称代价函数c满足三角不等式 在很多应用中 三角不等式自动满足 例如图的顶点为平面上的点 顶点间的旅行代价为顶点间的欧几里德距离 17 满足三角不等式的TS问题 求解思路 1 求出一棵MST MST的权值就是最低费用旅行线路的费用值的下界 2 对MST进行先序遍历 所得节点序列即为TS巡游序列 18 算法 APPROX TSP TOUR G c 1selectavertexr V G tobea root vertex2computeaminimumspanningtreeTforGfromrootrusingMST PRIM G c r 3letLbethelistofverticesvisitedinapreordertreewalkofT4returnthehamiltoniancycleHthatvisitstheverticesintheorderL 19 TS算法执行过程 Figure35 2 TheoperationofAPPROX TSP TOUR a Thegivensetofpoints whichlieonverticesofanintegergrid Forexample fisoneunittotherightandtwounitsupfromh Theordinaryeuclideandistanceisusedasthecostfunctionbetweentwopoints b AminimumspanningtreeTofthesepoints ascomputedbyMST PRIM Vertexaistherootvertex TheverticeshappentobelabeledinsuchawaythattheyareaddedtothemaintreebyMST PRIMinalphabeticalorder c AwalkofT startingata Afullwalkofthetreevisitstheverticesintheordera b c b h b a d e f e g e d a ApreorderwalkofTlistsavertexjustwhenitisfirstencountered asindicatedbythedotnexttoeachvertex yieldingtheorderinga b c h d e f g d Atouroftheverticesobtainedbyvisitingtheverticesintheordergivenbythepreorderwalk ThisisthetourHreturnedbyAPPROX TSP TOUR Itstotalcostisapproximately19 074 e AnoptimaltourH forthegivensetofvertices Itstotalcostisapproximately14 715 近似解 最优解 20 APPROX TSP是2 近似 Theorem35 2 APPROX TSP TOURisapolynomial time2 approximationalgorithmforthetraveling salesmanproblemwiththetriangleinequality 尽管定理35 2给出了很好的近似比 但是在实践中 APPROX TSP TOUR通常并不是解决TS问题的最佳选择 有些近似算法的实际性能要比这个算法好得多 但这些算法却无法从理论上证明具有较小的近似比 21 一般旅行商问题 定理35 3 若P NP 则对任意常数 1 一般旅行商问题不存在具有近似比 的多项式时间近似算法 证明 用矛盾来证明 假设存在近似比为 的近似算法A 则我们可以说明如何在多项式时间内用A来解决哈密尔顿回路问题的各种实例 而哈密尔顿回路问题是NP完全的 因此这意味着P NP 此即定理35 3的逆反命题 22 近似算法存在性证明 设G V E 是哈密顿回路问题的一个实例 我们希望通过假想的近似算法A来有效地确定G是否包含一个哈密顿回路 设G V E 为V上的完全图 即E u v u v Vandu v 再对E 中的每条边赋以一个整数代价如下 现在来考虑旅行商问题 G c 若原图G中存在一条哈密顿回路H 则代价函数c对H中的每条边赋以代价1 因而 G c 包含一个代价为 V 的游程 另一方面 若G中不包含一个哈密顿回路 则G 中的任何游程必定用到不在E中的某条边 但是 任意一个用到不在E中边的游程的代价为 V 1 V 1 V V V 因为不在G中的边的代价如此之大 故G中哈密顿回路的游程代价与任何其它游程的代价之间相差至少为 V 若将算法A应用于TSP问题 G c 由于A能返回不大于最优游程 倍的游程 因此若A返回小于等于 V 的解 则图G中存在hamiltonian环 否则G中不包含hamiltonian环 23 子集和问题 子集和问题 子集和问题 S t 其中S是一个正整数集 x1 x2 xn t是一个正整数 问是否存在一个S的子集 使得该子集中的元素之和等于t 该问题是Knapsack问题的特例 在优化问题中的描述是 求 x1 x2 xn 的一个子集 使得该子集中元素之和尽量接近 但又不超过t 24 子集和的迭代计算及性质 迭代计算子集和 在第i轮迭代计算中 计算集合 x1 x2 xi 的所有子集的元素和 计算的基础是集合 x1 x2 xi 1 的所有子集的和 性质 在此计算过程中 一旦某个特定的子集S 的和超过了t 就没必要在后继过程中对其进行处理了 因为S 的超集都不会成为最优解 25 EXACT SUBSET SUM算法 EXACT SUBSET SUM的输入为S x1 x2 xn 和t 该算法迭代计算Li 即集合 x1 xi 所有子集的和 这些和值都不超过目标值t 最终的最优解即Ln中的最大值 IfLisalistofpositiveintegersandxisanotherpositiveinteger thenweletL xdenotethelistofintegersderivedfromLbyincreasingeachelementofLbyx Forexample ifL 1 2 3 5 9 thenL 2 3 4 5 7 11 Wealsousethisnotationforsets sothatS x s x s S 使用过程MERGE LISTS L L 对两个有序表LandL 进行归并 同时删除重复值 26 EXACT SUBSET SUM算法 EXACT SUBSET SUM S t 1n S 2L0 0 3fori 1ton4doLi MERGE LISTS Li 1 Li 1 xi 5removefromLieveryelementthatisgreaterthant6returnthelargestelementinLn 27 示例 ToseehowEXACT SUBSET SUMworks letPidenotethesetofallvaluesthatcanbeobtainedbyselectinga possiblyempty subsetof x1 x2 xi andsummingitsmembers Forexample ifS 1 4 5 thenP1 0 1 P2 0 1 4 5 P3 0 1 4 5 6 9 10 28 算法的复杂度 表Li是一个包含Pi中的所有值不大于t的元素的有序表 因此的Li长度可大至2 i 因此EXACT SUBSET SUM是一个指数时间算法 29 一个完全多项式近似方案 对子集和问题 我们可以导出一个fullypolynomial timeapproximationscheme 通过修整 trimming 每次迭代产生的列表Li 其思想是若列表L中的两个值较为接近 那么出于需找近似解的目的 可以无需同时保留这两个数 而是用其中一个来代表所有与它接近的数 具体来说 我们引入参数 0 1 用 来修整表L意味着以这样一种方式从L中删除尽可能多的元素 即若L 为修整L后的结果 则对从L中删除的每个元素y 都存在一个仍在L 中的 近似y的元素z 使得满足 可以将这样一个z看成是在新表L 中代表y 例如若 0 1 且L 10 11 12 15 20 21 22 23 24 29 则修整后有 L 10 12 15 20 23 29 30 TRIM过程 TRIM L 1m L 2L y1 3last y14fori 2tom5doifyi last 1 yi lastbecauseLissorted6thenappendyiontotheendofL 7last yi8returnL 31 APPROX SUBSET SUM算法 利用TRIM过程 给出一个近似算法 输入为S x1 x2 xn 和t 以及一个近似度参数 其满足0 1 算法返回一个值z 该值落在最优解的1 倍内 APPROX SUBSET SUM S t 1n S 2L0 0 3fori 1ton4doLi MERGE LISTS Li 1 Li 1 xi 5Li TRIM Li 2n 6removefromLieveryelementthatisgreaterthant7letz bethelargestvalueinLn8returnz 32 示例 假设S 104 102 201 101 t