算法分析与设计AlgoD&ALectureNotesW12章节

1、Last Section,NP - Completeness,Why the theories ? Classifications Practice Optimization vs. Recognition Polynomially equivalent Problem Reduction and Transformation The TSP-optimization polynomially reduces to TSP-recognition I and III At least as hard as P, NP, NP-complete Certificate Proving NP-completeness Hamiltonian path problem vs. Hamiltonian cycle problem Longest path problem vs. Hamiltonian path problem Knapsack problem vs. partition problem,Approximation Algorithm,直观推断、贪婪。 相对误差、精确率、性能比

2、、c近似算法； TSP的近似算法 Nearest-neighbor algorithm 欧几里德类型实例 Twice-around-the-tree algorithm Christofide Algorithm 对TSP的所有实例求解,Christofide Algorithm,为将最小生成树T*变成欧拉图，不把它的边加倍，而是首先识别度数为奇数的顶点。 算法： 找出最小生成树T* ； 识别T*中度数为奇数的顶点集合X； 在X中寻找最小权重匹配M； 在T* M 中寻找欧拉旅程 te ； 在te中删除已访问过的顶点，得到解t 。 例：,Christofide Algo. 的性能比,设s*为最优旅程，则 f(T*) f(s*)； 又： f(M) f(s*)/2 令t为s*中所有不在X中的顶点和它们的关联边移走形成的一条回路，于是t由在X中的点集上的两个匹配M1和M2组成。 由于M是最小权重匹配，其权重小于或等于M1和M2中的任意一个。,Christofide Algo. 的性能比,f(t) f(te) = f(T*)+ f(M) f(s*)+f(s*)/2 =1.5f(s*),对TSP的

3、所有实例求解,定理 如果PNP， 那么对于旅行商问题来说，不会存在c近似算法； 即，不存在多项式时间的近似算法，能够使得下面的不等式对于的所有实例都成立： 存在某些常数c， 使得f(sa)c f(s*),证明,假设近似算法A和常数c 存在，则A可解Hamilton cycle 问题。 设G为n顶点图，将其映射为完全加权图G（对G的每条边赋权重1，任意两不相邻顶点间加权重为cn+1的边）。 若G有Hamilton 回路，它在G中的长度为n,即为G的TSP最优解。而A求G的f(sa)c n。 若G无Hamilton 回路，则G的TSP至少包含一条权重为cn+1的边；因此： f(sa) f(s*) c n 故,为在多项式时间内对G的Hamilton 回路问题求解，可将其映射为G，应用A求G的TSP，并与cn 比较。 因Hamilton 回路问题为NP-complete,则P=NP，矛盾。 所以，除非P=NP，否则假设就不成立。,最小顶点覆盖问题,在图G=（V，E）中的一个顶点覆盖C是一个顶点集合， 使得E中的每条边至少联到C中的一个顶点； 求G的一个最小顶点覆盖。 图,最小顶点覆盖问题,最直

4、观推断 重复以下步骤直至E为空： -任意选一条边e并加它的一个端点（v）到c； -删除e和所有其它和v关联的边。 这是一个输出顶点覆盖的近似算法。 然而这个算法的近似度？,The Vertex Cover Problem,|v| Any closer approximation? 如果在考虑边e时，把它的两个顶点都加到顶点覆盖中， 则近似度变成2。,The Vertex Cover Problem,算法 VCOVERAPPROX 输入：无向图G=（V，E） 输出：G的一个顶点覆盖C。 C while E 取E中任意边e=(u,v) CCu，v 删除e和E中所有与u和v 相关联的边 end while,Proof,ME(G), M, M中任意两条边在G中均不相邻，则称M是G的一个匹配。 显然，算法 输出了一个顶点覆盖。 第3步中所选的边构成一个匹配M。 为了覆盖M中边，需要至少|M|个顶点，这意味着一个最佳顶点覆盖的大小至少是|M|。 由算法等到的覆盖的大小恰好是2|M|. 考虑图 G=(v1, v2, (v1, v2) 最佳覆盖是v1，而由算法得到的覆盖是v1，v2。,背包问题,背包的

5、承重量W 等于10,背包问题,对每一物品计算价值/重量比； 按比值的降序对物品排序； 重复直至有序列表中不存在物品： 若当前物品能够放入背包，装之； 否则，考虑下一物品。,近似度？,该算法选择了第一个物品并跳过了第二个物品；这个子集的总价值是2。 而最优选择是物品2，它的价值是W。 因此，这个近似解的精确率是W/2，无上界。 算法的性能比为。,背包的承重量为w2,S.Sahni 的近似算法,生成所有小于等于k个物品的子集； 按照它们的价值/重量比的非递增序列，向每一个能够装入背包的子集添加剩余的物品； 以这种方式得到的最有价值的子集作为算法的输出。 例,W=10, k=2,S.Sahni 算法的性能比,设I为项U=u1, u2, ,un的背包问题的一个实例，C为背包的容量（承重量）； 设X是对应于一个最优解的项的集合, 并假定|X|k ； ( why?) 设Y= u1, u2, ,uk是X中k个最大值项的集合，并且设Z=uk+1， uk+2， ， ur用来表示X中剩余项的集合，假定对于所有的j, k+1jr-1, 有vj/sjvj+1/sj+1成立 ； 由于Y中的元素具有较大值，有 j

6、=k+1, k+2, r (1),S.Sahni 算法的性能比,考虑迭代算法将集合Y作为初始k-子集测试的情况： 设um为Z中第一个未被算法包含进背包的项（如果这样的项不存在，则算法的输出是最优的，所以假设um存在），最优解可以写成 (2) 设W表示um之前算法所考虑的并由算法装包的，但是不在u1, u2, ,um中的项的集合；即，如果ujW, 则， ，且vj/sjvm/sm.。则A(I)可以写成 (3),S.Sahni 算法的性能比,令 分别为在最优解和近似解中的有效剩余容量 (C是留给Z中um-1之后各项的； C”是留给（U Y Z中um之前各项 W中各项）中各项的)。 由(2)，有 根据m的定义和算法本身，有C”sm, 并且对于每个项vjW, 都有vj/sjvm/sm.。,S.Sahni 算法的性能比,由于 必定有 因此，根据 (3)，OPT(I)A(I)+vm ； 又由(1)，有,S.Sahni 算法的性能比,即 所以,多项式近似方案,某些NP困难的问题存在有有界近似比的近似算法； 有些问题，除非NP=P，否则不可能设计出具有有界近似比的近似算法； 存在这样的问题，对于它们存在

7、着一系列近似度收敛到1的近似算法（背包问题、子集和问题和多处理机调度问题等）。 定义 一个最优问题的近似方案是一个算法族A|0，使得RA1+。 一个近似方案可以看作是一个近似算法A，它的输入是问题的一个实例 I 和有界误差， 使得RA(I, )1+。 定义 一个多项式近似方案（PAS）是一个近似方案 A, 其中每一个算法A在输入实例 I 的规模的多项式时间内运行。,S.Sahni 算法的复杂性,算法生成的子集总数是 对于每一个子集，需要O(n)的时间来确定它可能的扩展； 因此，该算法的效率属于O(knk+1)，是背包问题的一个多项式近似方案。（但不是 k 的多项式） A可能不是1/的多项式时间的。,完全多项式近似方案,定义 一个完全多项式近似方案（FPAS）是一个近似方案A， 其中每个算法A在以输入实例的规模和1/两者的多项式时间内运行。 定义 伪多项式时间算法是一种算法，它在L值的多项式时间内运行，其中L是输入实例中的最大数值。 为NP难问题找到一个FPAS的想法对存在伪多项式时间算法的问题来说是很典型的。 对实例I的输入值应用尺度变换和舍入得到实例I并解之,子集和问题,子集和问题是

8、背包问题的特例，就是在背包问题中各项的值和它们的重量（尺寸）相同： 给出大小为s1, s2, , sn的n个项和背包容量正整数C， 找出这些项的一个子集，使得它们大小的总和最大化，且不超过背包的容量C。 求解该问题的算法几乎和求解背包问题的算法相同。,算法 SUBSETSUM 输入：项集U=u1, u2, , un, 大小分别为s1, s2, , sn, 背包容量C。 输出：函数 的最大值，满足对 的项的某个子集， 。 for i0 to n Ti,0 0 end for for j0 to C T0, j 0 end for for i1 to n for j1 to C Ti, j Ti-1, j if sij then xTi-1, j-si+si if xTi, j then Ti, j x end if end for end for return Tn,C (nc) * Ti,j 表示从前i项中取出来的装入体积为j的背包的物品的最大价值。,0/1 背包问题,当i和j都大于0时，有以下的结论： Vi,j是下面两个量的最大值： Vi-1,j:仅用最优的方法取自u1，u2，,ui

9、-1的物品去装入体积为j的背包所得到的价值最大值。 Vi-1,j-si+vi:用最优的方法取自u1，u2，,ui-1的物品去装入体积为j-si的背包所得到的价值最大值加上物品ui的价值。这仅应用于如果jsi以及它等于把物品ui加到背包上的情况。 观察结论对于找出最优装背包时的值，有下面的递推式 Vi,j = 0 若i=0或j=0 =Vi-1,j 若j0和jsi,子集和问题的 FPAS,为设计近似算法A，其中=1/k, k 为某个正整数，使算法对于任意实例I 有 令 首先，对于所有1jn，设 得到一个新的实例I。 然后对I应用算法SUBSETSUM，算法的运行时间现在减少到（nC/K）=（kn2）。,子集和问题的 FPAS,由于最优解不可能包含多于所有的n项，I和I的最优值之间有如下关系： (因sj= sj /K且向下取整) 设实例I的近似解是算法输出的实例I的解的K倍，则有 或,子集和问题的 FPAS,不失一般性，可以假定OPT（I）C/2， 因为如果OPT（I）C/2, 最优解可直接得出； 因此,子集和问题的 FPAS,算法的近似度（性能比）是 1+，运行时间是（n2/）。 令=1/ nr近似度，r1， 运行时间是（nr+2）。,Randomized Algorithm,随机算法,Deterministic vs. Probabilistic,Deterministic algorithms If we run the algorithm twice with the same input, we get two identical execution patterns and results. Probabilistic algorithms Depends also on some random events. The same algorithm

《算法分析与设计AlgoD&ALectureNotesW12章节》由会员E****分享，可在线阅读，更多相关《算法分析与设计AlgoD&ALectureNotesW12章节》请在金锄头文库上搜索。