设计郑宗汉郑晓明第15章近似算法.ppt

* 第15章 近似算法 0/1背包 MM MST TSP就是货郎担问题 第15章 近似算法 很多问题的输入数据是用测量方法取得的, 存在一定的误差, 即输入数据是近似的。 很多问题的最优解允许有一定程度的近似, 只要误差在一个有效范围内即可。 采用近似算法可以在很短时间内得到问题的解 (与指数时间相比较)。 15.1 近似算法的性能比 1. 近似算法的基本要求 算法能在问题规模n的多项式时间内完成; 算法的近似解满足一定的精度要求。 2. 近似算法的近似比 令?表示一最小化问题, 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) 近似算法的近似比总大于等于1 3) 近似算法的近似比越小, 性能越好 ?A(I)=A(I)/OPT(I) ?A(I)= OPT(I)/A(I) 3. 近似算法的相对误差 相对误差?的定义: 相对误差的界?(n): 近似比与相对误差界的关系: ?(n) ? ?A(I)-1, 即?A(I) ? 1+?(n) 4. 优化问题的近似方案 (approximation scheme) 很多难解问题可通过增加近似算法的计算量来改善其性能; 优化问题的近似方案 　把满足?A(I,?)?1+?（在误差范围内）的一类近似算法{A?|?0}称为优化问题的近似方案, 这些算法的性能比率会聚于1。 多项式近似方案 若近似方案中的每个算法A?均以输入实例规模的多项式时间运行, 则称该近似方案为多项式近似方案(Polynomial Approximation Scheme) 多项式近似方案中算法的计算时间不随?的减少而增长太快。 完全多项式近似方案 　若近似方案中每个算法的计算时间是1/?和n的多项式, 则称该近似方案为完全多项式近似方案(Fully Poly-nomial Approximation Scheme) {满足三角不等式的旅行商问题} 欧几里得旅行商问题: 给定赋权无向图G=(V,E), 旅行商问题求图中最短Hamilton回路。若图中顶点是平面上的顶点, 以任意两顶点之间的欧几里德距离作为它们之间的距离, 则为欧几里德旅行商问题。 15.2 欧几里得旅行商问题 算法1. 最近邻算法(NN, 贪心) kruscal 任选一个顶点作为起点, 选取最邻近该起点的一个顶点, 关联于起点和该顶点的边作为初始旅游通路; 令v表示刚加到旅游通路上的新顶点。在不属于该旅游通路上的顶点中选一个最邻近顶点v的顶点v?, 将关联于v与v?的边加到已有旅游通路上; 重复执行(2), 逐点扩充旅游通路, 直到所有顶点都包含在这条旅游通路上; 将形成的旅游通路的起点和终点用边联结, 形成所求的旅游回路. NN算法: ?NN=? 算法2. 最小生成树算法(MST) 对旅行商问题任意实例对应的赋权图, 调用最小生成树算法, 求其最小生成树; 　prim O(n2) 或 kruscal O(nlogn) 复制最小生成树的每条边, 即沿每条边来回走两次, 形成欧拉图; 在这个欧拉图中寻找其欧拉回路; 利用“抄近路”方法将欧拉回路变成所求旅游回路 (因满足三角不等式,故采用“抄近路”方法不会增加旅游回路的长度)。 定理1. 对满足三角不等式的旅行商 　　问题的任意实例I, 有?MST2 证明: 因最小生成树长度 OPT(I), 　AMST(I) 2*最小生成树长度, 故 AMST(I) 2*OPT(I) 　　 即 ?MST(I)=AMST(I)/OPT(I)2 MST算法的实现步骤 用Prim或Kruskal算法构造给定赋权图的最小生成树; 用深度优先有哪些信誉好的足球投注网站算法遍历最小生成树, 得到按先序遍历顺序存放的顶点序号（得到序列）, 则数组中顺序存放的顶点序号即为欧几里德TSP的近似解。 算法3. MM算法 对旅行商问题任意实例对应的赋权图, 调用最小生成树算法, 求其最小生成树T; 对最小生成树T中顶点的度数为奇数的顶点集V?={a1,a2,…,a2k}, 调用最小对集（偶数个顶点的完全图）算法, 在图G中求出V?的最小对集M;（度数为奇数的点一定是偶数个）。 在最小生成树T上添加V?的最小对集M, 形成欧拉图G?;（每个点的度数都是偶数） 在欧拉图G?中寻找其欧拉回路（找到定点序列）; 利用“抄近路”方法将欧拉回路变成所求的