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