第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.1
近似算法及其近似比
近似算法: A是一个多项式时间算法且对组合优化问题Π的每个实例I 每一个实例I 输出一个可行解输出个可行解σ. 记A(I )=) c (σ), ) c (σ) 是σ的值最优化算法: 恒有A(I )=OPT(I ), 即A 总是输出I 的最优解. 当Π是最小化问题时, 记r A (I )=A(I )/OPT(I ) ;当Π是最大化问题时, , 记r A (I ) )=OPT((I ) )/A((I ) ) .A 的近似比为r (A 是r –近似算法): 对每一个实例I , r A (I ) ≤r . A 具有常数比: r 是一个常数.
可近似性分类假设
P ≠NP , NP难的组合优化问题按可近似性可分成3 类:
(1) 完全可近似的:对任意小的ε>0, 存在(1+ε)-近似算法.
(2) 可近似的: 存在具有常数比的近似算法.
(3) 不可近似的: 不存在具有常数比的近似算法,
最小顶点覆盖问题问题: 任给图G =, 求G 的顶点数最少的顶点覆盖.
算法MVC : 开始时令V ′=∅. 任取一条边(u , v ), 把u 和v 加入V ′并删去u 和v 及其关联的边. 重复上述过程, 直至删去所有的边为止. V ′为所求的顶点覆盖.
2
1
6
9
78342{1,2}{1,2,3,4}{1,2,3,4,5,6}5
7819345
一个最优解：个最优解：{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 的近似比已不可能再进一步改进.
近似算法的分析研究近似算法的两个基本方面
⎯⎯设计算法和分析算法的运行时间与近似比.
分析近似比
(1) 关键是估计最优解的值.
(2) 构造使算法产生最坏的解的实例. 如果这个解的值与最(2)
优值的比达到或者可以任意的接近得到的近似比(这样的实例称作紧实例), ), 那么说明这个近似比已经是最好的、不可改进的了; 否则说明还有进一步的研究余地.
(3) 研究问题本身的可近似性, 即在P ≠NP(或其他更强) 的假(3)
设下, 该问题近似算法的近似比的下界.
8.2 多机调度问题
多机调度问题:
任给有穷的作业集任给有穷的作集A 和m 台相同的机器, , 作作业a 的处的处理时时间为正整数t (a ), 每一项作业可以在任一台机器上处理. 如何把作业分配给机器才能使完成所有作业的时间最短? 即, 如何把A 划分成m 个不相交的子集A i 使得
⎧⎫max ⎨∑t (a ) |i =1, 2, " , m ⎬⎩a ∈A i ⎭
最小?
负载: 分配给一台机器的作业的处理时间之和.
贪心法G-MPS G MPS : 按输入的顺序分配作业, 把每一项作业分把每项作业分配给当前负载最小的机器. 如果当前负载最小的机器有2台或2台以上, , 则分配给其中的任意则分配给其中的任意一台台.
实例例如，3 台机器, 8 项作业, 处理时间为3, 4, 3, 6, 5, 3, 8, 4
11 44
2 6 7
33 5 858
1 3 4
2 5 6
7 8G-MPS 的解完成时间15最优解完成时间12
算法给出的分配方案是{1,4}, {2,6,7}, {3,5,8},
负载分别为3+6=9, 4+3+8=15, 3+5+4=12
最优的分配方案是{1,3,4}, {2,5,6}, {7,8},
负载分别为3+3+6=12, 4+5+3=12, 8+4=12
紧实例M
台机器, m (m −1)+1 项作业,
前m (m −1) 1) 项作业的处理时间都为1, 1最后一项作业的处理时间为m .
算法把前m (m −1) 项作业平均地分配给m 台机器, 每台m −1项, 最后一项任意地分配给一台机器.
G MPS(I ) = 2G-MPS() 2m −1. 1
最优分配方案是把前m (m −1) 项作业平均地分配给m −1 台机器, 每台m 项, 最后一项分配给留下的机器,
OPT(I ) = m .
G-MPS 是2-近似算法
m =5的紧实例
1 6 11 16 21
2 7 12 17
3 8 13 18
4 9 14 19
5 10 15 20
21G-MPS 算法的解
最优解
12
8.2.2
改进的贪心近似算法
递降贪心法DG-MPS : 首先按处理时间从大到小重新排列作业, 然后运用G G-MPS MPS.
例如对上一小节的紧实例得到最优解.
对另个实例先重新排序8, 6, 5, 4, 4, 3, 3, 3; 对另一个实例：先重新排序
3台机器的负载分别为8+3=11, 6+4+3=13, 5+4+3=12. 比G-MPS 的结果好的结.
DG-MPS 的解4 8 6
5 2 3 完成时间13分析：DG-MPS 增加排序时间O (n log n ), 仍然是多项式时间
8.3
货郎问题
本节考虑满足三角不等式的货郎问题
831最邻近法8.3.1
最邻近法NN : 从任意一个城市开始, 在每一步取离当前所在城市最近的尚未到过的城市作为下个城市. 若这样的在城市最近的尚未到过的城市作为下一个城市城市不止一个, 则任取其中的11一个. 直至走遍所有城市, 最后
回到开始出发的城市.
一个NN 性能很坏的实例I ,
NN(I )=21, OPT() 21OPT(I )=15) 151211
[**************]11
8.3.2
最小生成树法
最小生成树法MST : 首先, 求图的一棵最小生成树T . 然后, 沿着T T 走两遍得到图的一条欧拉回路走两遍得到图的条欧拉回路. 最后, 顺着这条欧拉回路, 跳过已走过的顶点, 抄近路得到一条哈密顿回路. 例
求最小生成树和欧拉回路都可以在多项式时间内完成, , 故算法是多项式时间的.
最小生成树法的性能定理
8.4对货郎问题的所有满足三角不等式的实例I ,
MST(I )
证因为从哈密顿回路中删去因为从哈密顿回路中删去一条边就得到一棵生成树条边就得到棵生成树, 故T 的权小于OPT(I ). 沿T 走两遍的长小于2OPT(I ). 因为满足三角不等式, , 抄近路不会增加长度, , 故
MST(I )
MST 是2-近似算法.
8.3.3
最小权匹配法
最小权匹配法MM :
首先求图的一棵最小生成树首先求图的棵最小生成树T .
记T 的所有奇度顶点在原图中的导出子图为H , H 有偶数个顶点, , 求H 的最小匹配M . . 把M 加入T 得到得到一个欧拉图个欧拉图, , 求这个欧拉图的欧拉回路; 最后, 沿着这条欧拉回路, 跳过已走过的顶点, 抄近路得到一条哈密顿回路.
求任意图最小权匹配的算法是多项式时间的, 因此MM 是多项式时间的.
货郎问题的难度定理
8.6货郎问题(不要求满足三角不等式) 是不可近似的, 除非P = NP.P =NP
证假设不然, 设A 是货郎问题的近似算法, 其近似比r ≤K , K 是常数. 任给图G = , 如下构造货郎问题的实例I G : 城市集V , ∀u , v ∈V ,
若(u , v ) ∈E , 则令d (u , v )=1; 否则令d (u , v )=Kn , 其中|V | = n . 若G 有哈密顿回路, 则
OPT(I G ) = ) n , A(A(I G ) ) ≤r OPT(I G ) ) ≤Kn K
否则
OPT(I G ) > ) >Kn , A(A(I G ) ) ≥OPT(I G ) > ) >Kn
所以, G 有哈密顿回路当且仅当A(I G ) ≤Kn
证明于是
, 下述算法可以判断图G 是否有哈密顿回路: 首先构造货郎问题的实例I G , 然后对I G 运用算法A. 若A(I G ) ≤Kn , 则输出“Yes ”; 否则输出“No ”.
2) 由于K 是固定的常数, , 构造I G 可在O (n ) 时间内完成且G
| I G |=O (n 2). A是多项式时间的, A 对I G 可在n 的多项式时间内完成计算, , 所以上述算法是HC 的多项式时间算法. 而HC 是NP 完全的, 推得P=NP.
8.4
背包问题
0-1背包问题的优化形式:
任给n 件物品和一个背包件物品和个背包, 物品i i 的重量为w i , 价值为v i , 1≤i ≤n , 背包的重量限制为B , 其中w i , v i 以及B 都是正整数.
把哪些物品装入背包才能在不超过重量限制的条件下使得价值最大? ? 即, 求子集S *⊆{1,2,{12…, n } }使得
⎧⎫v i =max ⎨∑v i |∑w i ≤B , S ⊆{1, 2. " , n }⎬. ∑i ∈S *i ∈S ⎩i ∈S ⎭
8.4.1
一个简单的贪心算法贪心算法G-KK
1. 按单位按单位重量的价值从大到小排列物品的价值从大到小排列物品. 设
v 1/w 1 ≥v 2/w 2 ≥…≥v n /w n .
. 顺序检查每顺序检查每一件物品件物品, , 只要能装得下就将它装入背包, , 设2.
装入背包的总价值为V .
3. 求v k = max{ {v i | i = 1, 2, …, n }}. i |
若v k >V , 则将背包内的物品换成物品k .
实例(w i , v i ): (3,7), (4,9), (5,9), (2,2); B =6.
G KK 给出的解是装入(3,7)和(2,2), G-KK (2,2),总价值为9. 9. 若把第3件物品改为(5,10), 则装入第3件, 总价值为10.
(4,9), ) 和((2,2), , ), 总价值为11. 这两个实例的最优解都是装入(
G-KK
的性能
定理8.7 对0-1背包问题的任何实例I , 有
OPT(I )
证设物品l 是第一件未装入背包的物品, 由于物品按单位重量的价值从大到小排列, 故有
OPT(I )
≤G-KK(G KK(I ) +) +v max
≤2 G-KK(I ).
G-KK 是2-近似算法.
8.4.2
多项式时间近似方案算法PTAS 输入ε>0和实例I .
1令m = ⎡1/ε⎤. 1.
2. 按单位重量的价值从大到小排列物品. 设
v 1/w 1 ≥v 2/w 2 ≥…≥v n /w n .
3. 对每一个t =1,2,…, m 和t 件物品, 检查这t 件物品的重量之和. 若它们的重量之和不超过B , 则接着用G-KK G KK 把剩余的物品装入背包.
4比较得到的所有装法, 取其中价值最大的作为近似解. 4.
PTAS 是一簇算法. 对每一个固定的ε> 0, PTAS>0PTAS 是一个算法, 记作PTAS ε.
PTAS
的性能
定理8.8对每一个ε>0和0-1背包问题的实例I ,
OPT(I )
且PTAS ε的时间复杂度为O (n 1/ε+2 ) .
证设最优解为S *. 若|S *| ≤m , 则算法必得到S *. 设|S *| > m . 考虑计算中以S *中m 件价值最大的物品为基础, 用G-KK
*中第一件不在得到的结果S . 设物品l 是S * 中第件不在S 中的物品, 在
此之前G-KK 装入的不属于S * 的物品(肯定有这样的物品, 否则应该装入物品l l ) ) 的单位重量的价值都不小于v l /w l , 当然也不小于S * 中所有没有装入的物品的单位重量的价值, 故有OPT(I )
第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.1
近似算法及其近似比
近似算法: A是一个多项式时间算法且对组合优化问题Π的每个实例I 每一个实例I 输出一个可行解输出个可行解σ. 记A(I )=) c (σ), ) c (σ) 是σ的值最优化算法: 恒有A(I )=OPT(I ), 即A 总是输出I 的最优解. 当Π是最小化问题时, 记r A (I )=A(I )/OPT(I ) ;当Π是最大化问题时, , 记r A (I ) )=OPT((I ) )/A((I ) ) .A 的近似比为r (A 是r –近似算法): 对每一个实例I , r A (I ) ≤r . A 具有常数比: r 是一个常数.
可近似性分类假设
P ≠NP , NP难的组合优化问题按可近似性可分成3 类:
(1) 完全可近似的:对任意小的ε>0, 存在(1+ε)-近似算法.
(2) 可近似的: 存在具有常数比的近似算法.
(3) 不可近似的: 不存在具有常数比的近似算法,
最小顶点覆盖问题问题: 任给图G =, 求G 的顶点数最少的顶点覆盖.
算法MVC : 开始时令V ′=∅. 任取一条边(u , v ), 把u 和v 加入V ′并删去u 和v 及其关联的边. 重复上述过程, 直至删去所有的边为止. V ′为所求的顶点覆盖.
2
1
6
9
78342{1,2}{1,2,3,4}{1,2,3,4,5,6}5
7819345
一个最优解：个最优解：{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 的近似比已不可能再进一步改进.
近似算法的分析研究近似算法的两个基本方面
⎯⎯设计算法和分析算法的运行时间与近似比.
分析近似比
(1) 关键是估计最优解的值.
(2) 构造使算法产生最坏的解的实例. 如果这个解的值与最(2)
优值的比达到或者可以任意的接近得到的近似比(这样的实例称作紧实例), ), 那么说明这个近似比已经是最好的、不可改进的了; 否则说明还有进一步的研究余地.
(3) 研究问题本身的可近似性, 即在P ≠NP(或其他更强) 的假(3)
设下, 该问题近似算法的近似比的下界.
8.2 多机调度问题
多机调度问题:
任给有穷的作业集任给有穷的作集A 和m 台相同的机器, , 作作业a 的处的处理时时间为正整数t (a ), 每一项作业可以在任一台机器上处理. 如何把作业分配给机器才能使完成所有作业的时间最短? 即, 如何把A 划分成m 个不相交的子集A i 使得
⎧⎫max ⎨∑t (a ) |i =1, 2, " , m ⎬⎩a ∈A i ⎭
最小?
负载: 分配给一台机器的作业的处理时间之和.
贪心法G-MPS G MPS : 按输入的顺序分配作业, 把每一项作业分把每项作业分配给当前负载最小的机器. 如果当前负载最小的机器有2台或2台以上, , 则分配给其中的任意则分配给其中的任意一台台.
实例例如，3 台机器, 8 项作业, 处理时间为3, 4, 3, 6, 5, 3, 8, 4
11 44
2 6 7
33 5 858
1 3 4
2 5 6
7 8G-MPS 的解完成时间15最优解完成时间12
算法给出的分配方案是{1,4}, {2,6,7}, {3,5,8},
负载分别为3+6=9, 4+3+8=15, 3+5+4=12
最优的分配方案是{1,3,4}, {2,5,6}, {7,8},
负载分别为3+3+6=12, 4+5+3=12, 8+4=12
紧实例M
台机器, m (m −1)+1 项作业,
前m (m −1) 1) 项作业的处理时间都为1, 1最后一项作业的处理时间为m .
算法把前m (m −1) 项作业平均地分配给m 台机器, 每台m −1项, 最后一项任意地分配给一台机器.
G MPS(I ) = 2G-MPS() 2m −1. 1
最优分配方案是把前m (m −1) 项作业平均地分配给m −1 台机器, 每台m 项, 最后一项分配给留下的机器,
OPT(I ) = m .
G-MPS 是2-近似算法
m =5的紧实例
1 6 11 16 21
2 7 12 17
3 8 13 18
4 9 14 19
5 10 15 20
21G-MPS 算法的解
最优解
12
8.2.2
改进的贪心近似算法
递降贪心法DG-MPS : 首先按处理时间从大到小重新排列作业, 然后运用G G-MPS MPS.
例如对上一小节的紧实例得到最优解.
对另个实例先重新排序8, 6, 5, 4, 4, 3, 3, 3; 对另一个实例：先重新排序
3台机器的负载分别为8+3=11, 6+4+3=13, 5+4+3=12. 比G-MPS 的结果好的结.
DG-MPS 的解4 8 6
5 2 3 完成时间13分析：DG-MPS 增加排序时间O (n log n ), 仍然是多项式时间
8.3
货郎问题
本节考虑满足三角不等式的货郎问题
831最邻近法8.3.1
最邻近法NN : 从任意一个城市开始, 在每一步取离当前所在城市最近的尚未到过的城市作为下个城市. 若这样的在城市最近的尚未到过的城市作为下一个城市城市不止一个, 则任取其中的11一个. 直至走遍所有城市, 最后
回到开始出发的城市.
一个NN 性能很坏的实例I ,
NN(I )=21, OPT() 21OPT(I )=15) 151211
[**************]11
8.3.2
最小生成树法
最小生成树法MST : 首先, 求图的一棵最小生成树T . 然后, 沿着T T 走两遍得到图的一条欧拉回路走两遍得到图的条欧拉回路. 最后, 顺着这条欧拉回路, 跳过已走过的顶点, 抄近路得到一条哈密顿回路. 例
求最小生成树和欧拉回路都可以在多项式时间内完成, , 故算法是多项式时间的.
最小生成树法的性能定理
8.4对货郎问题的所有满足三角不等式的实例I ,
MST(I )
证因为从哈密顿回路中删去因为从哈密顿回路中删去一条边就得到一棵生成树条边就得到棵生成树, 故T 的权小于OPT(I ). 沿T 走两遍的长小于2OPT(I ). 因为满足三角不等式, , 抄近路不会增加长度, , 故
MST(I )
MST 是2-近似算法.
8.3.3
最小权匹配法
最小权匹配法MM :
首先求图的一棵最小生成树首先求图的棵最小生成树T .
记T 的所有奇度顶点在原图中的导出子图为H , H 有偶数个顶点, , 求H 的最小匹配M . . 把M 加入T 得到得到一个欧拉图个欧拉图, , 求这个欧拉图的欧拉回路; 最后, 沿着这条欧拉回路, 跳过已走过的顶点, 抄近路得到一条哈密顿回路.
求任意图最小权匹配的算法是多项式时间的, 因此MM 是多项式时间的.
货郎问题的难度定理
8.6货郎问题(不要求满足三角不等式) 是不可近似的, 除非P = NP.P =NP
证假设不然, 设A 是货郎问题的近似算法, 其近似比r ≤K , K 是常数. 任给图G = , 如下构造货郎问题的实例I G : 城市集V , ∀u , v ∈V ,
若(u , v ) ∈E , 则令d (u , v )=1; 否则令d (u , v )=Kn , 其中|V | = n . 若G 有哈密顿回路, 则
OPT(I G ) = ) n , A(A(I G ) ) ≤r OPT(I G ) ) ≤Kn K
否则
OPT(I G ) > ) >Kn , A(A(I G ) ) ≥OPT(I G ) > ) >Kn
所以, G 有哈密顿回路当且仅当A(I G ) ≤Kn
证明于是
, 下述算法可以判断图G 是否有哈密顿回路: 首先构造货郎问题的实例I G , 然后对I G 运用算法A. 若A(I G ) ≤Kn , 则输出“Yes ”; 否则输出“No ”.
2) 由于K 是固定的常数, , 构造I G 可在O (n ) 时间内完成且G
| I G |=O (n 2). A是多项式时间的, A 对I G 可在n 的多项式时间内完成计算, , 所以上述算法是HC 的多项式时间算法. 而HC 是NP 完全的, 推得P=NP.
8.4
背包问题
0-1背包问题的优化形式:
任给n 件物品和一个背包件物品和个背包, 物品i i 的重量为w i , 价值为v i , 1≤i ≤n , 背包的重量限制为B , 其中w i , v i 以及B 都是正整数.
把哪些物品装入背包才能在不超过重量限制的条件下使得价值最大? ? 即, 求子集S *⊆{1,2,{12…, n } }使得
⎧⎫v i =max ⎨∑v i |∑w i ≤B , S ⊆{1, 2. " , n }⎬. ∑i ∈S *i ∈S ⎩i ∈S ⎭
8.4.1
一个简单的贪心算法贪心算法G-KK
1. 按单位按单位重量的价值从大到小排列物品的价值从大到小排列物品. 设
v 1/w 1 ≥v 2/w 2 ≥…≥v n /w n .
. 顺序检查每顺序检查每一件物品件物品, , 只要能装得下就将它装入背包, , 设2.
装入背包的总价值为V .
3. 求v k = max{ {v i | i = 1, 2, …, n }}. i |
若v k >V , 则将背包内的物品换成物品k .
实例(w i , v i ): (3,7), (4,9), (5,9), (2,2); B =6.
G KK 给出的解是装入(3,7)和(2,2), G-KK (2,2),总价值为9. 9. 若把第3件物品改为(5,10), 则装入第3件, 总价值为10.
(4,9), ) 和((2,2), , ), 总价值为11. 这两个实例的最优解都是装入(
G-KK
的性能
定理8.7 对0-1背包问题的任何实例I , 有
OPT(I )
证设物品l 是第一件未装入背包的物品, 由于物品按单位重量的价值从大到小排列, 故有
OPT(I )
≤G-KK(G KK(I ) +) +v max
≤2 G-KK(I ).
G-KK 是2-近似算法.
8.4.2
多项式时间近似方案算法PTAS 输入ε>0和实例I .
1令m = ⎡1/ε⎤. 1.
2. 按单位重量的价值从大到小排列物品. 设
v 1/w 1 ≥v 2/w 2 ≥…≥v n /w n .
3. 对每一个t =1,2,…, m 和t 件物品, 检查这t 件物品的重量之和. 若它们的重量之和不超过B , 则接着用G-KK G KK 把剩余的物品装入背包.
4比较得到的所有装法, 取其中价值最大的作为近似解. 4.
PTAS 是一簇算法. 对每一个固定的ε> 0, PTAS>0PTAS 是一个算法, 记作PTAS ε.
PTAS
的性能
定理8.8对每一个ε>0和0-1背包问题的实例I ,
OPT(I )
且PTAS ε的时间复杂度为O (n 1/ε+2 ) .
证设最优解为S *. 若|S *| ≤m , 则算法必得到S *. 设|S *| > m . 考虑计算中以S *中m 件价值最大的物品为基础, 用G-KK
*中第一件不在得到的结果S . 设物品l 是S * 中第件不在S 中的物品, 在
此之前G-KK 装入的不属于S * 的物品(肯定有这样的物品, 否则应该装入物品l l ) ) 的单位重量的价值都不小于v l /w l , 当然也不小于S * 中所有没有装入的物品的单位重量的价值, 故有OPT(I )