- 快召唤伙伴们来围观吧
- 微博 QQ QQ空间 贴吧
- 文档嵌入链接
- 复制
- 微信扫一扫分享
- 已成功复制到剪贴板
09算法设计与分析---近似算法
展开查看详情
1 .东南大学计算机学院 方效林 近似算法
2 .本章内容 近似算法的基本概念 顶点覆盖 问题 集合覆盖问题 旅行商问题 子集和问题 随机和线性规划 2
3 .近似算法的基本概念 实际应用中很多问题都是 NP- 完全问题 求解 NP- 完全问题很难 若 NP- 完全问题输入规模很小,可指数级穷举搜索 否则,用多项式算法近似 3
4 .近似算法的基本概念 近似算法 能够给出一个优化问题的近似优化解的算法 主要解决优化问题 ( 最大化、最小化 ) 近似算法的时间复杂度分析 分析方法与传统算法一致 近似算法的近似度 ( 近似解与优化解的差距 ) Ratio Bound 相对误差 4
5 .近似算法的基本概念 Ratio Bound 设 A 是一个优化问题的近似解, A 的 Ratio Bound 为 ,则 若问题是最大化问题,则 若问题是最小化问题,则 Ratio Bound 越大,近似解越坏 5
6 .近似算法的基本概念 相对误差 设 A 是一个优化问题的近似解, A 的相对误差为 相对误差界 6
7 .近似算法的基本概念 相对误差与 Ratio Bound 关系 对于最小化问题 对于最大化问题 只要求出了 Ratio Bound ,就求出了相对误差 7
8 .顶点覆盖问题 输入:无向图 输出: ,满足 ,其中 或者 且 大小最小 8 顶点覆盖是 NP- 完全问题
9 .顶点覆盖问题 近似算法 A 的基本思想 随机选一条边 ( u,v ) ,删除与 u 或 v 相连的边 重复,直到无边,将选中的边的端点作为结果 9 b a c f d e g 算法解 { b,c,e,f,d,g } b a c f d e g 最优解 { b,c,d } b c f d e g
10 .顶点覆盖问题 近似算法 A 性能分析 时间复杂度为 O(|E|) Ratio Bound 为 2 令 是选中的边的集合,若 ,则与 相邻的边都被删除,因此 中无相邻边 每次选择一条边,即每次有两个顶点加入近似解 A , 设 是最优解, 必须覆盖 ,由于 中无邻接边, 至少包含 中每条边的一个顶点 , ,即 10
11 .集合覆盖问题 输入:有限集 ,子集合的集合 , 输出: ,满足 且 最小 11
12 .集合覆盖问题 12 s 1 s 2 s 3 s 4 s 5 s 6 最优解
13 .集合覆盖问题 近似算法 A 的基本思想 每次迭代选择能覆盖最多未被覆盖元素的子集 13 s 1 s 2 s 3 s 4 s 5 s 6 近似解
14 .集合覆盖 问题 近似算法 A 性能分析 时间复杂度 每次选能覆盖最多未被覆盖元素的子集 个子集,判断覆盖未被覆盖元素个数,一次选择要计算 次 共选择 次 总计算复杂度 14
15 .集合覆盖 问题 近似算法 A 性能分析 Ratio Bound 为 令 为最优解,其每个元素平均覆盖代价为 算法 A 第一次迭代时,必然有一个 集合 s 1 ,其平均代价 ,不然 不存在的 同理,设第 i 次迭代时剩余 个元素未被覆盖,对这 个元素覆盖最优解为 ,则必然存在一个 集合 s 2 , 。算法 A 的代价 15 = = =
16 .旅行商问题 (Hamilton 环 ) 给定一个图, Hamilton 环是包含图中每个顶点一次的简单环 16
17 .旅行商问题 (Hamilton 环 ) 输入:完全无向图 , 每条边 存在一个权值 , 边满足三角不等式 输出:边权值和最小的 Hamilton 环 17
18 .旅行商问题 (Hamilton 环 ) 近似算法 A 的基本思想 先构造最小生成树,先序遍历的顺序构造环 18 a b c d e f g h a b c d e f g h a b c d e f g h 最优解 近似解 构造最小生成树 先 序遍历
19 .旅行商问题 (Hamilton 环 ) 近似算法 A 性能分析 时间复杂度 构造最小生成树 先序遍历 总时间复杂度 19
20 .旅行商问题 (Hamilton 环 ) 近似算法 A 性能分析 Ratio Bound 为 2 令 为 最优解,路径权值和即代价为 环中删除一条边可得一棵生成树 ,代价 构造的最小生成树 , 先序遍历实际上对 中所有的边走了 2 次,即代价为 按先序遍历的节点第一次访问的顺序构造的 Hamilton 环为 ,是 先序遍历 2 次访问满足三角不等式的简化 20 a b c a b c a,b,a,c,a a,b,c,a
21 .Max-3CNF ( 随机近似 ) 输入: n 个布尔变量组成的 m 个析取范式的合取范式 输出: 对 n 个变量赋值,使 m 个析取范式为 1 的个数最多 21
22 .Max-3CNF ( 随机近似 ) 随机近似算法 A 22 Random-Max-3CNF( CNF ) For 对于 CNF 中的每个变量 x Do 随机 地为 x 赋值 : x =0 的概率为 1/2, x =1 的概率 为 1/2;
23 .Max-3CNF ( 随机近似 ) 随机近似算法 A 分析 随机近似比为 8/7 n 个变量随机赋 0 或 1 , m 个 析取范式 第 i 个析取范式 , 其 值为 0 的概率 1/8 其值为 1 的概率 1-1/8=7/8 3CNF 中值为 1 的个数 7m/8 最优解中值为 1 的个数为 m ,随机近似比 8/7 23
24 .顶点覆盖问题 ( 线性规划 ) 输入:无向图 ,顶点 有权值 输出: ,满足 ,其中 或者 且 最小 将问题换另一种描述 假设 为一个覆盖, 若 ,令 , 否则 要覆盖所有的边,则对任意边 ,需满足 24
25 .顶点覆盖问题 ( 线性规划 ) 问题可描述为一个 0-1 整数规划问题 目标:最小化 约束: ,且 25 可放宽限制条件,设 取值可为浮点数,问题转换为线性规划问题 使用线性规划求解,得到线性最优解 若 ,令 否则令 整数规划是 NP 完全的 线性规划是多项式可解的
26 .顶点覆盖问题 ( 线性规划 ) 近似算法 A 26 Approx ( G , w ) C=0 ; 计算线性规划问题的最优解 x ; For each v V Do If x ( v ) 1/2 Then C=C { v }; /* 用 四舍五入法 把线性规划的 解近似 为 0-1 规划的 解 * / 5. Return C.
27 .顶点覆盖问题 ( 线性规划 ) 近似算法 A 分析 A 的近似比为 2 ,故 和 至少有一个大于等于 1/2 ,即 或 至少有一个在覆盖中 令线性规划最优解代价为 因为 是线性规划可能解 , 故 27
28 .子集和问题 输入 给定正整数集合 和一个正整数 输出 最大化 其中 ,满足 28 , =9 最大不超过 的结果
29 .子集和问题 穷举方法 给定正整数集合 和一个正整数 … 每步删除大于 的结果 在 中找最大的即为最终结果 29 时间复杂度是指数级的