算法设计与分析讲义chapter7.doc

算法设计与分析讲义chapter7.doc

ID:49659204

大小:265.50 KB

页数:14页

时间:2020-03-03

算法设计与分析讲义chapter7.doc_第1页
算法设计与分析讲义chapter7.doc_第2页
算法设计与分析讲义chapter7.doc_第3页
算法设计与分析讲义chapter7.doc_第4页
算法设计与分析讲义chapter7.doc_第5页
资源描述:

《算法设计与分析讲义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、

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。