展开查看详情
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 时间复杂度是指数级的
热门城市
