26近似算法1.docx
- 文档编号:16586646
- 上传时间:2023-07-15
- 格式:DOCX
- 页数:24
- 大小:182KB
26近似算法1.docx
《26近似算法1.docx》由会员分享,可在线阅读,更多相关《26近似算法1.docx(24页珍藏版)》请在冰点文库上搜索。
26近似算法1
最小生成树法
针对满足三角不等式的货郎问题
最小生成树法MST:
首先,求图的一棵最小生成树T.然后,沿着T走两遍得到图的一条欧拉回路.最后,顺着这条欧拉回路,跳过已走过的顶点,抄近路得到一条哈密顿回路.
例
求最小生成树和欧拉回路都可以在多项式时间内完成,故算法是多项式时间的.
1
最小生成树法的性能
定理对货郎问题的所有满足三角不等式的实例I,
MST(I)<2OPT(I)
证因为从哈密顿回路中删去一条边就得到一棵生成树,故
T的权小于OPT(I).沿T走两遍的长小于2OPT(I).因为满足三角不等式,抄近路不会增加长度,故
MST(I)<2OPT(I).
MST是2-近似算法.
2
紧实例
OPT(I)=2nMST(I)=4n-2
ç
=⎛2-
⎝
1⎫OPT(I)
⎪
n⎭
3
最小权匹配法
最小权匹配法MM:
首先求图的一棵最小生成树T.
记T的所有奇度顶点在原图中的导出子图为H,H有偶数个顶点,求H的最小匹配M.把M加入T得到一个欧拉图,求这个欧拉图的欧拉回路;最后,沿着这条欧拉回路,跳过已走过的顶点,抄近路得到一条哈密顿回路.
求任意图最小权匹配的算法是多项式时间的,因此MM是多项式时间的.
4
最小权匹配法的性能
定理对货郎问题的所有满足三角不等式的实例I,
MM(I)<
3OPT(I)
2
证由于满足三角不等式,导出子图H中的最短哈密顿回路
C的长度不超过原图中最短哈密顿回路的长度OPT(I).沿着C隔一条边取一条边,得到H的一个匹配.总可以使这个匹配的权不超过C长的一半.因此,H的最小匹配M的权不超过OPT(I)/2,求得的欧拉回路的长小于(3/2)OPT(I).抄近路不会增加长度,得证
MM(I)<(3/2)OPT(I).
MM是3/2-近似算法
5
货郎问题的难度
定理货郎问题(不要求满足三角不等式)是不可近似的,除非P=NP.
证假设不然,设A是货郎问题的近似算法,其近似比r≤K,
K是常数.任给图G=
城市集V,∀u,v∈V,
若(u,v)∈E,则令d(u,v)=1;否则令d(u,v)=Kn,
其中|V|=n.若G有哈密顿回路,则
OPT(IG)=n,A(IG)≤rOPT(IG)≤Kn
否则
OPT(IG)>Kn,A(IG)≥OPT(IG)>Kn
所以,G有哈密顿回路当且仅当A(IG)≤Kn
6
实例
1
HC货郎问题
HC实例有哈密顿回路,则货郎问题实例有长度不超过n的旅行,即近似算法的解不超过Kn.若HC实例没有哈密顿回路,则货郎实例的旅行路线长度大于Kn.
7
7
证明
下述算法可以判断图G是否有哈密顿回路.算法
1.由I构造货郎问题的实例IG
2.对IG运用近似算法A
3.若A(IG)≤Kn,则输出“Yes”;否则输出“No”
由于K是固定的常数,构造IG可在O(n2)时间内完成且
|IG|=O(n2).A是多项式时间的,A对IG可在n的多项式时间内完成计算,所以上述算法是HC的多项式时间算法.而HC是NP完全的,推得P=NP.
8
0-1背包问题
0-1背包问题的优化形式:
任给n件物品和一个背包,物品i的重量为wi,价值为vi,1≤i≤n,背包的重量限制为B,其中wi,vi以及B都是正整数.
把哪些物品装入背包才能在不超过重量限制的条件下使得价值最大?
即,求子集S*⊆{1,2,⋯,n}使得
∑vii∈S*
=max⎧v
⎨∑
i
⎩i∈S
|∑wii∈S
≤B,S
⊆{1,2.
⎫
n}⎬.
⎭
9
贪心算法G-KK
一个简单的贪心算法
1.
按单位重量的价值从大到小排列物品.设
v1/w1≥v2/w2≥⋯≥vn/wn.
2.顺序检查每一件物品,只要能装得下就将它装入背包,设装入背包的总价值为V.
3.求vk=max{vi|i=1,2,⋯,n}.
若vk>V,则将背包内的物品换成物品k.
实例(wi,vi):
(3,7),(4,9),(5,9),(2,2);B=6.
G-KK给出的解是装入(3,7)和(2,2),总价值为9.
若把第3件物品改为(5,10),则装入第3件,总价值为10.这两个实例的最优解都是装入(4,9)和(2,2),总价值为11.
10
G-KK的性能
定理对0-1背包问题的任何实例I,有
OPT(I)<2G-KK(I)
证设物品l是第一件未装入背包的物品,由于物品按单位重量的价值从大到小排列,故有
OPT(I) ≤G-KK(I)+vmax ≤2G-KK(I). G-KK是2-近似算法. 11 多项式时间近似方案 算法PTAS输入ε>0和实例I. 1.令m=⎡1/ε⎤. 2.按单位重量的价值从大到小排列物品.设 v1/w1≥v2/w2≥⋯≥vn/wn. 3.对每一个t=1,2,⋯,m和t件物品,检查这t件物品的重量之和.若它们的重量之和不超过B,则接着用G-KK把剩余的物品装入背包. 4.比较得到的所有装法,取其中价值最大的作为近似解. PTAS是一簇算法.对每一个固定的ε>0,PTAS是一个算法,记作PTASε. 12 例子 取ε=0.1,m=10. t=1: 尝试n次,装入背包物品集分别为{1},{2},…,{n},再使用G-KK算法 t=2: 尝试n(n-1)/2次,装入物品集分别是{1,2},{1,3},…, {n-1,n},再使用G-KK算法. … t=10: 尝试 10次,装入物品集为{1,…,9,10},{1,…,9,11}, C n …,{n-9,n-8,…,n-1,n},再用G-KK算法. 总计运行G-KK算法次数至多: C C C + + nn n 12...+10 13 , PTAS的性能 定理对每一个ε>0和0-1背包问题的实例I, OPT(I)<(1+ε)PTASε(I), 且PTASε的时间复杂度为O(n1/ε+2). 证设最优解为S*.若|S*|≤m,则算法必得到S*.设|S*|>m.考虑计算中以S*中m件价值最大的物品为基础,用G-KK得到的结果S.设物品l是S*中第一件不在S中的物品,在此之前G-KK装入不属于S*的物品(肯定有这样的物品,否则应该装入物品l)单位重量的价值都不小于vl/wl,当然也不小于S*中所有没有装入的物品的单位重量的价值,故有 OPT(I)<∑i∈Svi+vl S包括S*中m件价值最大的物品,它们的价值都不小于vl, vl≤∑i∈Svi/m 14 多项式时间近似方案 OPT(I)<∑i∈Svi+vl ≤∑i∈Svi+∑i∈Svi/m ≤(1+1/m)PTASε(I) ≤(1+ε)PTASε(I) c ≤ n m 时间复杂度.从n件物品中取t件(t=1,2,⋯,m),所有可能取法的个数为 c c + nn 12++ mm⋅nm! ≤nm. 对每一种取法,G-KK的运行时间为O(n),故算法的时间复杂度为O(nm+1)=O(n1/ε+2). 多项式时间近似方案: 以ε>0和问题的实例作为输入I,对每一个固定的ε>0,算法是1+ε-近似的. 15 伪多项式时间算法与完全多项式时间近似方案 完全多项式时间近似方案: 以ε>0和问题的实例I作为输入,时间复杂度为二元多项式p(|I|,1/ε),且对每一个固定的 ε>0,算法的近似比为1+ε. 动态规划算法A记Gk(d): 当只考虑前k件物品时,为了得到不小于d的价值,至少要装入的物品重量 Gk(d)= ⎧k ∑ min⎨ ⎩i=1 wixi k |∑ i=1 vixi ≥d,xi =0或1,1≤i ⎫ ≤k⎬, ⎭ 0≤k≤n,0≤d≤D,D=v1+v2+⋯+vn 约定: min∅=+∞ OPT(I)=max{d|Gn(d)≤B} 16 动态规划算法 递推公式 G0(d)= ⎧0, ⎩ ⎨+∞, 若d=0, 若d>0, G(d)= ⎧min{Gk(d),wk+1}, 若d≤ vk+1, k+1 ⎨min{G(d),G(d-v)+ ⎩ k kk+1 wk+1}, 若d> vk+1, 0≤k≤n-1,0≤d≤D.A的时间复杂度为O(nD)=O(n2vmax),是伪多项式时间算法. 17 完全多项式时间近似方案 算法FPTAS(FullyPolynomial-TimeApproximationScheme) 输入ε>0和实例I. 1.令 ⎧⎢ b=max vmax⎥⎫ ⎨⎢(1+1/ε)n⎥,1⎬. ⎩⎣⎦⎭ 2.令vi'=⎡vi/b⎤,1≤i≤n.把所有vi换成vi',记新的实例为I'. 3.对I'应用算法A得到解S,把S取作实例I的解. 定理对每一个ε>0和0-1背包问题的实例I, OPT(I)<(1+ε)FPTAS(I), 并且FPTAS的时间复杂度为O(n3(1+1/ε)). 18 证明 证由于 (vi'-1)b (1) 对任意的T⊆{1,2,⋯,n} 0≤b∑i∈Tvi'-∑i∈Tvi (2) 设I的最优解为S*,注意到S是I'的最优解,故有 OPT(I)-FPTAS(I)=∑i∈S*vi-∑i∈Svi =(∑i∈S*vi-b∑i∈S*vi')(≤0,由式 (1)vi≤vi'b) +(b∑i∈S*vi'-b∑i∈Svi')(≤0,S是关于输入vi'的最优解) +(b∑i∈Svi'-∑i∈Svi) ≤(b∑i∈Svi'-∑i∈Svi) (2)) 19 证明 OPT(I)-FPTAS(I) 对每一个ε>0,若b=1,则I'就是I,S是I的最优解.设b>1,则 OPT(I)-FPTAS(I) ≤OPT(I)/(1+1/ε)(因为vmax≤OPT(I)) 得OPT(I)<(1+ε)FPTAS(I). 时间: 主要是A对I'的运算,时间复杂度为 O(n2vmax/b)=O(n3(1+1/ε)) 20
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 26 近似 算法