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

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