算法分析解析与设计-2016第13讲.ppt

《算法分析解析与设计-2016第13讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计第13讲-2016山东大学计算机学院解决问题是最重要的，也是研究的源动力。从设计算法开始。。再从高出看近似算法。近似性能比r定义了绝对近似性能比渐进近似性能比也具有同样的含义。当OPT(I)>N时，满足RA(I)r，r的下确界。回到另一面去看看：近似性能比能越来越小吗？人们要考虑这样的问题。(1)是否能多花时间，提高解的质量。使绝对近似性能比越来越小？(2)是否存在一个关于解质量的界，这个界难以逾越?就像TSP问题的近似算法，能设计近似性能比更小的多项式算法吗？让计算机多运行一些时间，得到更好的解，可以吗？要在多项式时间内。要说

2、明，这个算法存在，就能拿这个算法解答Hamilton回路问题。说明：TSP问题不是在metric空间，不一定满足三角不等式。渐进近似性能比由Hamilton回路问题到是否存在TSP问题近似解的图灵归约Hamilton回路问题实例TSP问题实例Hamilton回路问题实例TSP问题实例上面的图存在Hamilton回路，下面的不存在Hamilton回路。解释怎么归约！1111111K

3、V

4、K

5、V

6、K

7、V

8、(3)分析GH存在Hamilton回路OPT(GTSP)=

9、V

10、A(GTSP)K*OPT(GTSP)=K

11、V

12、GH不存在Hamilton回路

13、OPT(GTSP)>K

14、V

15、A(GTSP)OPT(GTSP)>K

16、V

17、所以Hamilton回路问题存在多项式时间算法。说明：(1)找错一条边，就会出大问题，近似度超过任意常数，边太长了。(2)这不是metric空间的TSP问题，是任意空间的TSP问题，不存在任意常数近似度的近似算法。K

18、V

19、K

20、V

21、K

22、V

23、G=G1*G2的做法(G)=(G1)*(G2)，如果G2是完全图，当然对。G1：G2：2种颜色拿这个算法去解答一个知道不行的问题。实例：无向简单图G询问：是否存在一种着色方案，使其颜色数不超过最小着色数的4/3倍。三着色问题实例图灵归

24、约NP-Hard存在算法A1.近似度想多么小，就多么小；2.常数近似；3.Logn近似；4.n近似。多项式时间近似方案TSP,排工§7.3多项式时间近似方案独立任务排工的进一步讨论，n个任务，m台机器，每个任务加工时间长度ti。新算法，想办法多费点功夫，前K个任务求最优排工。也与问题有关。(1)任务排序：T={T1,T2,…,Tn}，t1t2…tn(2)确定正整数K,对前K个任务，求最优排工，O(mK)时间，后面n-k个任务，按照先大后小顺序排工。上述算法叫F。举个例子：T={T1,T2,T3,T4,T5,T6}加工时间：8，6，5，4

25、，4，1T1,T2,T3,T4先求最优排工。后两任务再排，得15。最优为14。这个不是最优的。特别好，看不出来tj(2)在[0，F(I)-tK+1]区间所有处理器非空闲。t1t2…tKtK+1…tn由(1)决定，最后完成任务为Tj，则jK+1，所以[0,F(I)-tj]区间所有机器非空闲，又tK+1tj，所以在[0，F(I)-tK+1]区间所有处理器非空闲。最后一个完成的任务Tj,tjtK+1。(3)=mF(I)-(m-1)tK+1t1…tKtK+1…tn无论哪种排工，鸽笼原理。(5)分析算法时间复杂度TA(m,n)

26、=O(mk+nlogn)，K=m，近似性能比小于1+1/2，K=2m；近似性能比小于1+1/3；说明：K越大时间复杂度越高，解的优化程度越高。定义7.2：若问题的近似算法A()满足：对任意实例I，任意>0(1)RA()[I]<1+(2)A()的时间复杂度是实例I长度的多项式函数，则，A()称为求解问题的多项式时间近似方案。另外给问题增加一个输入数据，是个常数。Polynomialtimeapproximationscheme近似性能比1+，时间复杂度O(n3)，这个不行Polynomialtimeapproximations

27、cheme设元素：a1,a2,…,an(p1,w1)，(p2,w2),…,(pn,wn)加上数值M，就是背包问题实例。这样装法显然不一定多么好，若任意一种K个元素的组合都先放入背包尝试，选择其中最好的，则最后结果一定比直接装入好。全部尝试完后选择最好的，作为最后结果。(1)K=0时，直接从头开始装入：x1,x2,x3,x4,x5,x6,x7,x8=11111000，前5个装入背包Pmax=11+21+31+33+43=139W=1+11+21+23+33=89(2)K=1，时，先装入1个，再装入其他，得到1,2,3,4,7最好x1,x2,x3,

28、x4,x5,x6,x7,x8=1,1,1,1,0,0,1,0Pmax=11+21+31+33+45=151W=1+11+21+23+45=101(3)