资源描述：
《算法设计与分析讲义chapter7.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章近似算法·很多实际应用中问题都是NP-完全问题·NP-完全问题的多项式算法是难以得到的·求解NP-完全问题的两种方法：·如果问题的输入很小，可以使用指数级算法圆满地解决该问题·使用多项式算法求解问题的近似优化解·近似算法：能够给出一个优化问题的近似优化解的算法·本章将介绍几个NP-完全问题的多项式时间算法7.1近似算法的性能分析·本节讨论的问题是优化问题·问题的每一个可能的解都具有一个正的代价·问题的优化解可能具有最大或最小代价——最大化或最小化问题·我们希望寻找问题的一个近似优化解1.RatioBound定义1(RatioBound)设A是一个优化问题的近似算法
2、，A具有ratioboundp(n)，如果,其中n是输入大小，c是近似算法所产生的解的代价，c*是优化解的代价。*若问题是最大化问题，则，*若问题是最小化问题，则，*由于c/c*<1当且仅当c*/c>1,近似算法的RatioBound不会小于1，即*求解准确优化解的优化算法的RatioBound一定是1*具有较大RatioBound的近似算法给出的近似解一定比优化解坏的多—RatioBound表示了近似算法的性能142.相对误差定义2对于任意输入,近似算法的相对误差定义为,其中c是近似算法所产生的解的代价，c*是优化解的代价。*相对误差总是非负的。定义3一个近似算法的相
3、对误差界为如果。结论1。证.对于最小化问题===对于最大化问题===.*对于某些问题，和独立于输入n，我们用p和表示之*对于另一些问题，很难找到具有固定ratiobound的多项式时间算法，我们可以令ratiobound是输入大小n的函数*某些NP-完全问题的近似算法满足：当运行时间增加时，ratiobound和相对误差将减少定义4一个优化问题的近似模式是一个算法，是一个具有相对误差界的近似算法，其中I是问题实例，是任意一个固定的数。定义5近似模式称为一个多项式时间近似模式，如果对于，的运行时间是的多项式。定义6一个近似模式称为完全多项式时间近似模式，如果它的运行时间是
4、关于和输入实例大小n的多项式。14例1.设模式s的运行时间是，则s是完全多项式时间近似模式。7.2优化结点覆盖问题1.问题定义输入：无向图G=（V，E）输出：，满足(1).，、或{u,v}ÍV’(2).是满足条件(1)的最小集合。*理论上已经证明优化结点覆盖问题是NP-完全问题。2.近似算法APPROX-Vertex-Cover(G)1.2.3.whileDO4.任取5.6.E’←E’-{(u’,v’)
5、u’=u或v’=v}7.RoturnC3.时间复杂性T(G)=O(
6、E
7、).4.性能定理1Approx-Vertex-Cover具有RatioBound214证:令A=
8、是算法第4步选中的边}。若(u,v)ÎA，则所以与（u,v）邻接的边皆从中删除。于是,A中无相邻接边.于是，第五步的每次运行增加两个结点到C，
9、C
10、=2
11、A
12、设C*是优化解，C*必须覆盖A。由于A中无邻接边，C*至少包含A中每条边的一个结点。于是，
13、A
14、£
15、C*
16、，
17、C
18、=2
19、A
20、£2
21、C*
22、，即
23、C
24、/
25、C*
26、£2.7.3最小集合覆盖问题1.问题的定义输入：有限集X，F是X的所有子集合集族，X=输出：CÍF，满足(1).X=，(2).C是满足条件(1)的最小集族，即
27、C
28、最小。*最小集合覆盖问题是很多实际问题的抽象。*最小集合覆盖问题是NP-完全问题。2.Greedy
29、近似算法Greedy-Set-Cover(X,F)1.U¬X;2.C¬q;3.WhileU¹qDo/*U表示X中尚未被覆盖的元素的集合*/4.selectSÎF使得
30、S∩U
31、最大;/*Greedy选择——选择能够覆盖最多X元素的子集合S*/5.U¬U-S6.C¬C∩{S};/*构造X的覆盖*/7.ReturnC.1.复杂性14·3-6的循环次数至多为min(
32、X
33、,
34、F
35、)·
36、S∩U
37、需要时间O(
38、X
39、)·第4步需要时间O(
40、F
41、
42、X
43、)·T(X,F)=O(
44、F
45、
46、X
47、×min(
48、x
49、,
50、F
51、))1.性能定理1令H(d)=。Greedy-Set-Cover具有Ratio
52、BoundH(max{
53、S
54、:SÎF})。证：设C*是优化的集合覆盖,C*的代价是
55、C*
56、。令Si是由Greedy-Set-Cover选中的第i个子集。设当把Si加入C时,C的代价加1。把选择Si的代价均匀地分配到由Si首次覆盖的所有结点。对于xÎX，令cx是分配到x的代价。若x被Si首次覆盖,则cx=.显然，算法给出的解C的代价为
57、C
58、，
59、C
60、平均地分布到x的所有点.由于C*也覆盖X，我们有
61、C
62、=£.注意：上式的小于成立是因为C*中各子集可能相交，在中，某些cx被加了多次，而在中每个cx只加一次。如果"SÎF，£H(
63、s
64、)成立，则
65、
