北京大学屈婉玲算法设计与分析课件 - 图文 

第8章近似算法

8.1 近似算法及其近似比8.2 多机调度问题

8.2.1 贪心的近似算法

822改进的贪心近似算法8.2.2

8.3 货郎问题

8.3.1 最邻近法

8.3.2 最小生成树法833最小权匹配法8.3.3

8.4 背包问题

8.4.1 841一个简单的贪心算法8.4.2 多项式时间近似方案

8.4.3 伪多项式时间算法与完全多项式时间近似方案

8.1近似算法及其近似比

近似算法: A是一个多项式时间算法且对组合优化问题Π的每个实例I 每一个实例I输出一个可行解输出个可行解σ. 记A(I)=)c(σ), )c(σ)是σ的值最优化算法: 恒有A(I)=OPT(I), 即A总是输出I 的最优解.当Π是最小化问题时, 记rA(I)=A(I)/OPT(I) ;当Π是最大化问题时,, 记rA(I))=OPT((I))/A((I)) .A的近似比为r(A是r–近似算法): 对每一个实例I, rA(I) ≤r. A具有常数比: r是一个常数.

可近似性分类

假设P≠NP , NP难的组合优化问题按可近似性可分成3 类:(1) 完全可近似的:对任意小的ε>0, 存在(1+ε)-近似算法. 0-1背包问题(2) 可近似的: 存在具有常数比的近似算法.

最小顶点覆盖、多机调度、满足三角不等式的货郎问题机度等(3) ()不可近似的: 不存在具有常数比的近似算法.

近似比是输入规模的对数多项式或多项式，如一般性的货郎问题

最小顶点覆盖问题

问题: 任给图G=, 求G的顶点数最少的顶点覆盖.算法MVC: 开始时令V′=?. 任取一条边(u,v), 把u和v加入V′并删去u和v及其关联的边. 重复上述过程, 直至删去所有的边为止. V′为所求的顶点覆盖.

2

1

6

9

7

83

4

2

{1,2}{1,2,3,4}{1,2,3,4,5,6}

5

7

8

1

69

3

4

5

一个最优解：个最优解：{1,3,6,9}{1369}，MVC的解：{1,2,3,4,5,6}{123456}

最小顶点覆盖问题

分析: 算法时间复杂度为O(m), m=|E|.

记|V′| = 2k, V′由k 条互不关联的边的端点组成. 为了覆盖这k 条边需要k 个顶点, 从而OPT(I) ≥k. 于是,

MVC(I)/OPT(I) ≤2k/k = 2.

又, ,设图G由k k条互不关联的边构成, ,显然

MVC(I) = 2k, OPT(I )= k,

这表明MVC MVC的近似比不会小于2, 2上面估计的MVC的近似比已不可能再进一步改进.