09算法设计与分析---近似算法

本章主要讲述近似算法,其中包括近似算法的基本概念:近似算法的时间复杂度分析,近似算法的近似度,相对误差,相对误差界;顶点覆盖问题:顶点覆盖是NP-完全问题,近似算法A的基本思想;集合覆盖问题;旅行商问题;子集和问题;随机和线性规划等
展开查看详情

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 时间复杂度是指数级的