第第15章章 近似算法近似算法(1)0/1背包(2)MM(3)MST(4)TSP就是货郎担问题设计郑宗汉郑晓明第15章近似算法第第15章章 近似算法近似算法(1)很多问题的输入数据是用测量方法取得的, 存在一定的误差, 即输输入入数数据是近似的据是近似的。(2)很多问题的最优解允许有一定程度的近似, 只要误差在一个有效范围内即可。(3)采用近似算法可以在很短时间内得到问题的解 (与指数时间相比较)。设计郑宗汉郑晓明第15章近似算法15.1 近似算法的性能比近似算法的性能比 1. 近似算法的基本要求近似算法的基本要求1)算法能在问题规模n的多项式时间内完成;2)算法的近似解满足一定的精度要求。设计郑宗汉郑晓明第15章近似算法2. 近似算法的近似比近似算法的近似比令 表示一最最小小化化问题, I是的一个实例, A是求解的一个近似算法, A(I)是近似解值, OPT是求解的最优算法, OPT(I)是最优解值, 则近似算法A的近似比近似比为: A(I)=A(I)/OPT(I)若是最大化最大化问题, 则 A(I)= OPT(I)/A(I)设计郑宗汉郑晓明第15章近似算法说明说明: 1) 对最小化问题, 有A(I) OPT(I) 对最大化问题, 有A(I) OPT(I)2) 近似算法的近似比总大于等于大于等于13) 近似算法的近似比越小近似比越小, 性能越好性能越好 A(I)=A(I)/OPT(I) A(I)= OPT(I)/A(I)设计郑宗汉郑晓明第15章近似算法3. 近似算法的相对误差近似算法的相对误差相对误差 的定义:相对误差的界 (n): 近似比与相对误差界的关系: (n) A(I)-1, 即 A(I) 1+(n) 设计郑宗汉郑晓明第15章近似算法4. 优化问题的近似方案优化问题的近似方案 (approximation scheme) 1)很多难解问题可通过增加近似算法的计算量来改善其性能;2)优化问题的近似方案把满足 A(I, ) 1+ （在在误误差差范范围围内内）的一类近似算法A | 0称为优化问题的近近似似方方案案, 这些算法的性能比率会聚于1。设计郑宗汉郑晓明第15章近似算法3) 多项式近似方案多项式近似方案 若近似方案中的每个算法A 均以输入实例规规模模的多项式时间运行, 则称该 近 似 方 案 为 多多 项项 式式 近近 似似 方方 案案(Polynomial Approximation Scheme) 多项式近似方案中算法的计计算算时时间间不随 的减少而增长太快。设计郑宗汉郑晓明第15章近似算法4) 完全多项式近似方案完全多项式近似方案若近似方案中每个算法的计算时间是1/ 和n的多项式, 则称该近似方案为完全多项式近似方案完全多项式近似方案(Fully Poly-nomial Approximation Scheme)设计郑宗汉郑晓明第15章近似算法满足三角不等式的旅行商问题 欧几里得旅行商问题:给定赋权无向图G=(V,E), 旅行商问题求图中最短Hamilton回路。若图中顶点是平面上的顶点, 以任意两顶点之间的欧几里德距离作为它们之间的距离, 则为欧几里德旅行商问题。15.2 欧几里得旅行商问题欧几里得旅行商问题设计郑宗汉郑晓明第15章近似算法算法算法1. 最近邻算法(NN, 贪心)kruscal(1)任选一个顶点作为起点, 选取最邻近该起点的一个顶点, 关联于起点和该顶点的边作为初始旅游通路;(2)令v表示刚加到旅游通路上的新顶点。在不属于该旅游通路上的顶点中选一个最邻近顶点v的顶点v, 将关联于v与v的边加到已有旅游通路上;设计郑宗汉郑晓明第15章近似算法(3)重复执行(2), 逐点扩充旅游通路, 直到所有顶点都包含在这条旅游通路上;(4)将形成的旅游通路的起点和终点用边联结, 形成所求的旅游回路.NN算法: NN= 设计郑宗汉郑晓明第15章近似算法算法算法2. 最小生成树算法(MST)(1)对旅行商问题任意实例对应的赋权图, 调用最小生成树算法, 求其最小生成树; prim O(n2) 或 kruscal O(nlogn)(2)复制最小生成树的每条边, 即沿每条边来回走两次, 形成欧拉图;(3)在这个欧拉图中寻找其欧拉回路;(4)利用“抄近路”方法将欧拉回路变成所求旅游回路 (因满足三角不等式,故采用“抄近路”方法不会增加旅游回路的长度)。设计郑宗汉郑晓明第15章近似算法定理定理1. 对满足三角不等式的旅行商问题的任意实例I, 有 MST2证明: 因最小生成树长度 OPT(I), AMST(I) 2*最小生成树长度, 故 AMST(I) 2*OPT(I) 即 MST(I)=AMST(I)/OPT(I)2设计郑宗汉郑晓明第15章近似算法MST算法的实现步骤算法的实现步骤1.用Prim或Kruskal算法构造给定赋权图的最小生成树;2.用深深度度优优先先搜搜索索算法遍历最小生成树, 得到按先序遍历顺序存放的顶点序号（得到序列）, 则数组中顺序存放的顶点序号即为欧几里德TSP的近似解。设计郑宗汉郑晓明第15章近似算法设计郑宗汉郑晓明第15章近似算法算法算法3. MM算法1)对旅行商问题任意实例对应的赋权图, 调用最小生成树算法, 求其最小生成树T; 2)对最小生成树T中顶点的度数为奇数的顶点集V =a1,a2,a2k, 调用最小对集（偶数个顶点的完全图）算法, 在图G中求出V的最小对集M;（度数为奇数的点一定是偶数个）。设计郑宗汉郑晓明第15章近似算法3)在最小生成树T上添加V的最小对集M, 形成欧拉图G;（每个点的度数都是偶数）4)在欧拉图G中寻找其欧拉回路（找到定点序列）;5)利用“抄近路”方法将欧拉回路变成所求的旅游回路。设计郑宗汉郑晓明第15章近似算法定理定理2. 对满足三角不等式的货郎问题的任意实例I, 有 MM3/2证明: (1)最小生成树T的边长之和小于最短旅游回路; d(T)OPT(I)(2)因实例满足三角不等式, 故赋权图G中经过V 中顶点的最短旅游回路长度必必小小于于经过图G中所有顶点的 最 短 旅 游 回 路 长 度 。d(ep)=1/2opt(i)设计郑宗汉郑晓明第15章近似算法在经过V中顶点的最短旅游回路中, 每隔一条边删除一条边, 得到V的对集M, 而步骤(2)找出的是V的最小对集M。它们之间的关系为:最小对集M中边长度之和 对集M中边长度之和 V中最短回路长度的一半 实例I中最短回路长度的一半因此,步骤(2)中求出的V中最小对集M的边长度之和不不会会超超过过实例I中最短回路长度之和的一半;设计郑宗汉郑晓明第15章近似算法(3)欧拉图G的所有边长度之和小小于于实例I中最短回路长度之和的3/2倍; (4)因满足三角不等式, 故采用抄近路方法在欧拉图G中找出的旅游回路长度AMM(I)小小于于实例I中最短回路长度的3/2倍.因此, AMM(I)3/2OPT(I), 即 MM 2 算法所求解为u1, 最优解为u2C可能任意大, 故性能比可能无界.对算法做简单修改可使性能比为2.设计郑宗汉郑晓明第15章近似算法修改算法的步骤修改算法的步骤:(1)对物体按pi/vi降序排序, 并依次装入背包, 得到价值为pr的解; (2)挑选一个价值最大的物体装入背包, 得到价值为ps;(3)选择pr和ps中较大者作为输出。设计郑宗汉郑晓明第15章近似算法算法算法 Knapsack-Problem近似算法输入: U=u1,u2,un,V=v1,v2,vn, P=p1,p2,pn, C输出: 价值最大的子集SU 排序使 p1/v1 p2/v2 pn/vn i0; v0; p0; S; /初始化设计郑宗汉郑晓明第15章近似算法3. while in and vC 4. if vi C-v 5. SSui; vv+vi; pp+pi;6. ii+1;7. 8. 令S =us, 其中us为价值最大物体;9. If p ps return S; else return S.设计郑宗汉郑晓明第15章近似算法0/1背包问题的多项式近似方案背包问题的多项式近似方案算法步骤: 1) n个物体按价值体积比价值体积比递减排序; k=1/ ; i=0; for(i=0;i=k;i+)for(j=1;j= Cni;j+)1)2) j=1; 2)3)从n个物体中选取i个个物物体体放进背包,这种选择共有Cni组, 选择第第j组组i个物体, 其余物体的选择按贪心算法执行; 令结果背包中物体总价值为vj, 保存背包中物体序号的数组为kpj;设计郑宗汉郑晓明第15章近似算法4)若jk, 令Y=u1,u2,uk是X中中k个价值最大的物体集合,令Z=uk+1, uk+2, , ur是X中中其余物体的集合。设计郑宗汉郑晓明第15章近似算法平均数：当ik+1时，平均值一直在减少假定对满足k+1 i r-1的所有的i, 有 对所有的i, i=k+1, , r, 有 设计郑宗汉郑晓明第15章近似算法|X|k, 集合Y必是算法第3步中Cni组选择中的某一组选择。算算法法所选物体一部分包含在集合Z中, 另一部分不包含在集合Z中。令不包含在Z中那部分物体为W, 必定存在物体um使得Z中uk+1, uk+2,um-1是算法所选物体。设计郑宗汉郑晓明第15章近似算法把最优解的结果写成: 把算法的结果写成: 设计郑宗汉郑晓明第15章近似算法令C为背包中装入物体u1,u2, um-1之后的剩余容量, 则有分数背包：设计郑宗汉郑晓明第15章近似算法令装入C为算法所有物体之后的剩余容量, 即则则有则则对uiW, uiu1, u2, um,放不下了根据算法的贪婪选择性质, 有有 设计郑宗汉郑晓明第15章近似算法整理得: 设计郑宗汉郑晓明第15章近似算法因此, 有 由算法的时间复杂性可看出, 算法的运行时间是1/和n的多项式时间, 故该算法是一个完全多项式近似算法。 设计郑宗汉郑晓明第15章近似算法