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

第15章近似算法 0 1背包MMMSTTSP就是货郎担问题 第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 近似算法的近似比总大于等于13 近似算法的近似比越小 性能越好 A I A I OPT I A I OPT I A I 3 近似算法的相对误差相对误差 的定义 相对误差的界 n 近似比与相对误差界的关系 n A I 1 即 A I 1 n 4 优化问题的近似方案 approximationscheme 很多难解问题可通过增加近似算法的计算量来改善其性能 优化问题的近似方案把满足 A I 1 在误差范围内 的一类近似算法 A 0 称为优化问题的近似方案 这些算法的性能比率会聚于1 多项式近似方案若近似方案中的每个算法A 均以输入实例规模的多项式时间运行 则称该近似方案为多项式近似方案 PolynomialApproximationScheme 多项式近似方案中算法的计算时间不随 的减少而增长太快 完全多项式近似方案若近似方案中每个算法的计算时间是1 和n的多项式 则称该近似方案为完全多项式近似方案 FullyPoly nomialApproximationScheme 满足三角不等式的旅行商问题 欧几里得旅行商问题 给定赋权无向图G V E 旅行商问题求图中最短Hamilton回路 若图中顶点是平面上的顶点 以任意两顶点之间的欧几里德距离作为它们之间的距离 则为欧几里德旅行商问题 15 2欧几里得旅行商问题 算法1 最近邻算法 NN 贪心 kruscal任选一个顶点作为起点 选取最邻近该起点的一个顶点 关联于起点和该顶点的边作为初始旅游通路 令v表示刚加到旅游通路上的新顶点 在不属于该旅游通路上的顶点中选一个最邻近顶点v的顶点v 将关联于v与v 的边加到已有旅游通路上 重复执行 2 逐点扩充旅游通路 直到所有顶点都包含在这条旅游通路上 将形成的旅游通路的起点和终点用边联结 形成所求的旅游回路 NN算法 NN 算法2 最小生成树算法 MST 对旅行商问题任意实例对应的赋权图 调用最小生成树算法 求其最小生成树 primO n2 或kruscalO nlogn 复制最小生成树的每条边 即沿每条边来回走两次 形成欧拉图 在这个欧拉图中寻找其欧拉回路 利用 抄近路 方法将欧拉回路变成所求旅游回路 因满足三角不等式 故采用 抄近路 方法不会增加旅游回路的长度 定理1 对满足三角不等式的旅行商问题的任意实例I 有 MST 2证明 因最小生成树长度 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 中寻找其欧拉回路 找到定点序列 利用 抄近路 方法将欧拉回路变成所求的旅游回路 定理2 对满足三角不等式的货郎问题的任意实例I 有 MM 3 2证明 1 最小生成树T的边长之和小于最短旅游回路 d T OPT I 2 因实例满足三角不等式 故赋权图G中经过V 中顶点的最短旅游回路长度必小于经过图G中所有顶点的最短旅游回路长度 d ep 1 2opt 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 3 2 有些问题存在性能比会聚于1的近似算法 只要增加算法的运算时间 可使算法的性能比接近于1 15 5多项式近似方案 1 0 1背包的多项式近似方案 背包问题 输入 U u1 u2 un 物体 V v1 v2 vn 质量 P p1 p2 pn 价值 C 背包容量 输出 子集S U 使得 ui Svi C max ui Spi按pi vi降序排序 并依次填入背包 分数背包问题 最优解0 1背包问题 近似解 0 1背包问题贪婪算法的性能比可能无界 例如 U u1 u2 v1 1 p1 2 v2 p2 C 2算法所求解为 u1 最优解为 u2 C可能任意大 故性能比可能无界 对算法做简单修改可使性能比为2 修改算法的步骤 对物体按pi vi降序排序 并依次装入背包 得到价值为pr的解 挑选一个价值最大的物体装入背包 得到价值为ps 选择pr和ps中较大者作为输出 算法Knapsack Problem近似算法输入 U u1 u2 un V v1 v2 vn P p1 p2 pn C输出 价值最大的子集S U排序使p1 v1 p2 v2 pn vni 0 v 0 p 0 S 初始化 whilei nandv C ifvi C v S S ui v v vi p p pi i i 1 令S us 其中us为价值最大物体 Ifp psreturnS elsereturnS 0 1背包问题的多项式近似方案算法步骤 n个物体按价值体积比递减排序 k 1 i 0 for i 0 i k i for j 1 j Cni j 2 j 1 3 从n个物体中选取i个物体放进背包 这种选择共有Cni组 选择第j组i个物体 其余物体的选择按贪心算法执行 令结果背包中物体总价值为vj 保存背包中物体序号的数组为kpj 4 若j Cni j j 1 则转3 否则转5 5 从Cni组结果中 选取vj最大的一组结果 令其价值为svi 保存相应背包中物体序号的数组为skpi 6 i i 1 若i k 则转2 否则转7 7 从k 1组结果中 选取svi最大的一组结果 令其价值为v 保存相应背包中物体序号的数组为kp 则v及kp为算法的最终输出结果 多项式近似方案的性能分析 定理15 4对某个k 1 令 1 k 算法的运行时间为O knk 1 性能比为1 证明 1 时间复杂性的证明对每个确定的i 共需进行Cni组选择 执行Cni次knapsack reedy算法 i由0递增到k 共需执行的循环次数为 物体排序在算法第一步完成 执行时无需重复执行 每一轮循环中 把物体装入背包的工作量为O n 因此 算法的总运行时间为O knk 1 2 性能比的证明令I是背包问题的一个实例 X是相应于最优解的物体集合 有两种情况 若 X k 则算法第3步Cni组选择中必有一组选择是最优解 遍历了所有种情况 此时 算法的性能比为1 若 X k 令Y u1 u2 uk 是X中k个价值最大的物体集合 令Z uk 1 uk 2 ur 是X中其余物体的集合 平均数 当i k 1时 平均值一直在减少假定对满足k 1 i r 1的所有的i 有 对所有的i i k 1 r 有 X k 集合Y必是算法第3步中Cni组选择中的某一组选择 算法所选物体一部分包含在集合Z中 另一部分不包含在集合Z中 令不包含在Z中那部分物体为W 必定存在物体um使得Z中 uk 1 uk 2 um