北京大学屈婉玲算法设计与分析必威体育精装版课件08.pdf

第8章近似算法 8.1 近似算法及其近似比 8.2 多机调度问题 8.2.1 贪心的近似算法 88.22.22 改进的贪心近似算法改进的贪心近似算法 8.3 货郎问题 8.3.1 最邻近法最邻近法 8.3.2 最小生成树法 88.33.33 最小权匹配法最小权匹配法 8.4 背包问题 88.44.11 一个简单的贪心算法一个简单的贪心算法 8.4.2 多项式时间近似方案 8.4.3 伪多项式时间算法与完全多项式时间近似方案伪多项式时间算法与完全多项式时间近似方案 8.1 近似算法及其近似比 近似算法: A是一个多项式时间算法且对组合优化问题Π 的 每每一个实例个实例II 输出输出一个可行解个可行解σ. 记记A(A(II))=c((σ)), c((σ))是是σ 的值的值 最优化算法: 恒有A(I)=OPT(I), 即A 总是输出I 的最优解. 当Π是最小化问题时, 记rA(I)=A(I)/OPT(I) ; 当Π是最大化问题时,, 记rAA((I))=OPT((I))/A((I)) . A 的近似比为r (A 是r–近似算法): 对每一个实例I, rA(I) ≤r. A具有常数比: r是一个常数. 可近似性分类 假设P≠NP , NP难的组合优化问题按可近似性可分成3 类: (1) 完全可近似的:对任意小的ε0, 存在(1+ε)-近似算法. 00--11背包问题背包问题 (2) 可近似的: 存在具有常数比的近似算法. 最小顶点覆盖、多机机调度度、满足三角不等等式的货郎问题 ((3)) 不可近似的不可近似的: 不存在具有常数比的近似算法不存在具有常数比的近似算法. 近似比是输入规模的对数多项式或多项式，如一般性 的货郎问题的货郎问题 最小顶点覆盖问题 问题: 任给图G= V,E, 求G的顶点数最少的顶点覆盖. 算法MVC: 开始时令V′=∅. 任取一条边(u,v), 把u和v加入V′ 并删去u和v及其关联的边. 重复上述过程, 直至删去所有的 边为止边为止. VV′′为所求的顶点覆盖为所求的顶点覆盖. 2 3 2 3 44 44 {1,2} 1 1 66 {1,2,3,4} 66 {1,2,3,4,5,6} 9 9 55 55 8 8 7 7 一个最优解个最优解：：{1{1,33,66,9}9}，MVCMVC的解的解：：{1{1,22,33,44,55,6}6} 最小顶点覆盖问题 分析: 算法时间复杂度为O(m), m=|E |. 记记| V′| = 2k, V′由由k 条互不关联的边的端点组成条互不关联的边的端点组成. 为了覆盖为了覆盖 这k 条边需要k 个顶点, 从而OPT(I) ≥k. 于是,