会计学第15章近似算法15.1近似算法的性能比2.近似算法的近似比令表示(biǎoshì)一最小化问题,I是的一个实例,A是求解的一个近似算法,A(I)是近似解值,OPT是求解的最优算法,OPT(I)是最优解值,则近似算法A的近似比为:A(I)=A(I)/OPT(I)若是最大化问题,则A(I)=OPT(I)/A(I)说明:1)对最小化问题,有A(I)OPT(I)对最大化问题,有A(I)OPT(I)2)近似(jìnsì)算法的近似(jìnsì)比总大于等于13)近似(jìnsì)算法的近似(jìnsì)比越小,性能越好3.近似算法的相对误差(xiānꞬduìwùchà)相对误差(xiānꞬduìwùchà)的定义:4.优化问题的近似方案(approximationscheme)很多难解问题可通过增加近似算法的计算量来改善其性能(xìngnéng);优化问题的近似方案把满足A(I,)1+（在误差范围内）的一类近似算法{A|>0}称为优化问题的近似方案,这些算法的性能(xìngnéng)比率会聚于1。多项式近似方案若近似方案中的每个算法A均以输入实例规模(guīmó)的多项式时间运行,则称该近似方案为多项式近似方案(PolynomialApproximationScheme)多项式近似方案中算法的计算时间不随的减少而增长太快。完全多项式近似方案若近似方案中每个算法(suànfǎ)的计算时间是1/和n的多项式,则称该近似方案为完全多项式近似方案(FullyPoly-nomialApproximationScheme){满足三角不等式的旅行商问题}欧几里得旅行商问题:给定赋权无向图G=(V,E),旅行商问题求图中最短Hamilton回路。若图中顶点(dǐngdiǎn)是平面上的顶点(dǐngdiǎn),以任意两顶点(dǐngdiǎn)之间的欧几里德距离作为它们之间的距离,则为欧几里德旅行商问题。算法1.最近邻算法(NN,贪心)kruscal任选(rènxuǎn)一个顶点作为起点,选取最邻近该起点的一个顶点,关联于起点和该顶点的边作为初始旅游通路;令v表示刚加到旅游通路上的新顶点。在不属于该旅游通路上的顶点中选一个最邻近顶点v的顶点v,将关联于v与v的边加到已有旅游通路上;重复执行(zhíxíng)(2),逐点扩充旅游通路,直到所有顶点都包含在这条旅游通路上;将形成的旅游通路的起点和终点用边联结,形成所求的旅游回路.NN算法:NN=算法2.最小生成树算法(MST)对旅行商问题任意实例对应的赋权图,调用最小生成树算法,求其最小生成树;primO(n2)或kruscalO(nlogn)复制(fùzhì)最小生成树的每条边,即沿每条边来回走两次,形成欧拉图;在这个欧拉图中寻找其欧拉回路;利用“抄近路”方法将欧拉回路变成所求旅游回路(因满足三角不等式,故采用“抄近路”方法不会增加旅游回路的长度)。定理1.对满足三角(sānjiǎo)不等式的旅行商问题的任意实例I,有MST<2证明:因最小生成树长度<OPT(I),AMST(I)<2*最小生成树长度,故AMST(I)<2*OPT(I)即MST(I)=AMST(I)/OPT(I)<2MST算法的实现(shíxiàn)步骤用Prim或Kruskal算法构造给定赋权图的最小生成树;用深度优先搜索算法遍历最小生成树,得到按先序遍历顺序存放的顶点序号（得到序列）,则数组中顺序存放的顶点序号即为欧几里德TSP的近似解。/算法3.MM算法对旅行商问题任意实例对应(duìyìng)的赋权图,调用最小生成树算法,求其最小生成树T;对最小生成树T中顶点的度数为奇数的顶点集V={a1,a2,…,a2k},调用最小对集（偶数个顶点的完全图）算法,在图G中求出V的最小对集M;（度数为奇数的点一定是偶数个）。在最小生成树T上添加V的最小对集M,形成欧拉图G;（每个点的度数都是偶数）在欧拉图G中寻找其欧拉回路(huílù)（找到定点序列）;利用“抄近路”方法将欧拉回路(huílù)变成所求的旅游回路(huílù)。定理2.对满足三角不等式的货郎问题的任意实例I,有MM<3/2证明(zhèngmíng):(1)最小生成树T的边长之和小于最短旅游回路;d(T)<OPT(I)(2)因实例满足三角不等式,故赋权图G中经过V中顶点的最短旅游回路长度必小于经过图G中所有顶点的最短旅游回路长度。d(ep)<=1/2opt(i)在经过V中顶点的最短旅游回路中,每隔一条边删除一条边,得到V的对集M,而步骤(2)找出的是V的最小对集M。它们之间的关系为:最小对集M中边长度(chángdù