计算机算法基础 第2版 课件 第15章 近似算法.pptx

第15章近似算法1问题定义 2顶点复盖问题 5货郎担向题 8集合复盖问题 16MAX-3-SAT问题 25加权的顶点复盖问题 29子集和问题 33鸿沟定理和不可近似性 46

2如果一个问题是个NPC问题，很可能不存在多项式的算法，而在实际工作中人们又经常碰到NPC的问题而且必须要解决，怎么办呢？找一个快速的近似算法(Approximationalgorithm)或者一个启发式算法(Heuristicalgorithm)成为解决问题的最重要手段。这两者的区别在于前者保证计算结果与最佳解之间的差别不超过一个范围，而后者不能定量地给予保证，它的实际效果往往通过仿真(simulation)实验予以证实。这一章，我们只讨论近似算法。NP难的优化型问题的解一般对应一个目标值C并要求这个值最大，或最小，或最长，或最短，等等。我们可以把它们分为两大类，一类是要求目标值C最大，另一类是要求目标值C最小，分别称为最大化(maximization)问题和最小化(minimization)问题。1. 问题定义

3?

4?

5计算图G(V,E)的顶点复盖的一个简单的近似算法是：任取一条边，(u,v)?E，把点u和v加入集合S中。把被顶点u和v复盖的边从图G中刪去。如果图G中不再有边，那说明所有的边已被S中点所复盖，否则，在剩下的边中重复步(1)(2)直到图中不再有边为止。Approx-Vertex-Cover(G(V,E))S??； //集合S初始为空 whileE?? selectanedge(u,v)?E //任选一条边(u,v) S?S?{u,v} //把u和v加入集合S E?E–{(x,y)|x?{u,v}ory?{u,v}} //刪除与u或v关联的边endwhilereturnSEnd2. 顶点复盖问题

6例 (a)图Gabefdcgh(b)选(a,e)，S={a,e}。虚线是刪除的边。abefdcgh(c)选(c,f)，S={a,e,c,f}。abefdcgh(d)选(d,h)，S={a,e,c,f,d,h}。abefdcgh(f)最小复盖是5个点，Sopt={a,b,f,g,d}。abefdcgh(e)近似解S={a,e,c,f,d,h}。abefdcgh

7定理15.1 算法Approx-Vertex-Cover是一个2-近似算法。证明：当算法结束时，图中所有边都因与集合S中某个点关联而被删去，因而S是一个顶点复盖。设算法一共选了k条边，那么这个解S的目标值为C=2k。再考虑最佳解C*。我们注意到，在近似算法每次选取的边(u,v)中，任何最佳解必须至少包含顶点u或v。又因为近似算法所选取的边都有不同的顶点，所以任何最佳解必须包含集合S中的至少k个顶点。因而有C/C*?2k/k=2。?

8我们可证明，对一般的货郎担问题，不存在有常数倍近似度的近似算法。但是，对于特殊的一类货郎担问题有很好的近似算法。下面先讨论这一特殊类货郎担问题，然后再讨论一般的货郎担问题。满足三角不等式关系的货郎担问题加权图G中，如果任意三个顶点u,v,w?V之间的边满足关系w(w,u)?w(u,v)+w(v,w)，那么称这个图满足三角不等式。定义15.4 满足三角不等式的货郎担问题定义如下：给定一个没有负权值的完全图G(V,E)和一个正数k，假设图G满足三角不等式，判断G是否含有一条货郎担回路使得它的总权值小于等于k？定理15.2 满足三角不等式关系的货郎担问题是个NP-难问题。证明： 我们把一般的货郎担问题多项式归约为这个满足三角不等式关系的货郎担问题。(接下页)3. 货郎担问题

9证明(继续1)：假设一般的货郎担问题的一个特例是一个没有负权值的完全图G(V,E)和正数k。现在，我们由此构造一个满足三角不等式的图G’(V’,E’)和正数k’。设|V|=n，这个构造步骤如下：Construct-Triangle-TSP(G(V,E))G’(V’,E’)?G(V,E) //复制M?max{w(u,v)|w(u,v)?E} //E中最大的边的权值Mforeach(u,v)?E’ w’(u,v)?w(u,v)+Mendfork’?k+nMEnd这显然是个多项式算法，并且G’满足三角不等式，这是因为：任取图G’三点，u,v,w，我们有：w’(w,u)=w(w,u)+M?M+