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

算法分析与设计,第13讲-2016 山东大学计算机学院,解决问题是最重要的，也是研究的源动力。 从设计算法开始。,。,再从高出看近似算法。,近似性能比r,定义了绝对近似性能比,渐进近似性能比也具有同样的含义。 当OPT(I)N时，满足RA(I)r，r的下确界。 回到另一面去看看：近似性能比能越来越小吗？ 人们要考虑这样的问题。 (1)是否能多花时间，提高解的质量。使绝对近似性能比越来越小？ (2)是否存在一个关于解质量的界，这个界难以逾越?,就像TSP问题的近似算法，能设计近似性能比更小的多项式算法吗？,让计算机多运行一些时间，得到更好的解，可以吗？要在多项式时间内。,要说明，这个算法存在，就能拿这个算法解答Hamilton回路问题。,说明：TSP问题不是在metric空间，不一定满足三角不等式。,渐进近似性能比,由Hamilton回路问题到是否存在TSP问题近似解的图灵归约,Hamilton回路问题实例,TSP问题实例,Hamilton回路问题实例,TSP问题实例,上面的图存在Hamilton回路，下面的不存在Hamilton回路。,解释怎么归约！,1,1,1,1,1,1,1,K|V|,K|V|,K|V|,(3)分析 GH存在Hamilton回路OPT(GTSP)=|V| A(GTSP)K*OPT(GTSP)=K|V| GH不存在Hamilton回路OPT(GTSP)K|V| A(GTSP)OPT(GTSP)K|V| 所以Hamilton回路问题存在多项式时间算法。,说明： (1)找错一条边，就会出大问题， 近似度超过任意常数，边太长了。 (2)这不是metric空间的TSP问题，是任意空间的TSP问题， 不存在任意常数近似度的近似算法。,K|V|,K|V|,K|V|,G=G1*G2的做法 (G)= (G1)*(G2)，如果G2是完全图，当然对。,G1：,G2：,2种颜色,拿这个算法去解答一个知道不行的问题。,实例：无向简单图G 询问：是否存在一种着色方案，使其颜色数不超过最小着色数的4/3倍。,三着色问题实例,图灵归约,NP-Hard,存在算法A,1.近似度想多么小，就多么小； 2.常数近似； 3.Logn近似； 4.n近似。,多项式时间近似方案,TSP, 排工,7.3多项式时间近似方案 独立任务排工的进一步讨论，n个任务，m台机器， 每个任务加工时间长度ti。 新算法，想办法多费点功夫，前K个任务求最优排工。 也与问题有关。 (1)任务排序：T=T1, T2, , Tn，t1t2tn (2)确定正整数K,对前K个任务，求最优排工，O(mK)时间， 后面n-k个任务，按照先大后小顺序排工。,上述算法叫F。举个例子： T=T1,T2,T3,T4,T5,T6 加工时间：8，6，5，4，4，1 T1,T2,T3,T4先求最优排工。后两任务再排，得15。最优为14。,这个不是最优的。,特别好，看不出来,tj,(2)在0，F(I)-tK+1区间所有处理器非空闲。 t1 t2 tK tK+1 tn 由(1)决定， 最后完成任务为Tj，则jK+1，所以0, F(I)-tj区间所有机器非空闲， 又tK+1tj，所以在0，F(I)-tK+1区间所有处理器非空闲。 最后一个完成的任务Tj, tj tK+1。,(3),= mF(I)-(m-1)tK+1,t1 tK tK+1 tn,无论哪种排工，鸽笼原理。,(5)分析算法时间复杂度TA(m,n)=O(mk+nlogn)， K=m，近似性能比小于1+1/2，K=2m；近似性能比小于1+1/3； 说明：K越大时间复杂度越高，解的优化程度越高。 定义7.2：若问题的近似算法A()满足：对任意实例I，任意0 (1)RA()I1+ (2)A()的时间复杂度是实例I长度的多项式函数， 则，A()称为求解问题的多项式时间近似方案。,另外给问题增加一个输入数据，是个常数。,Polynomial time approximation scheme,近似性能比1+，时间复杂度O(n3)，这个不行,Polynomial time approximation scheme,设元素：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=139 W=1+11+21+23+33=89 (2)K=1，时，先装入1个，再装入其他，得到1,2,3,4,7最好 x1,x2,x3,x4,x5,x6,x7,x8=1,1,1,1,0,0,1,0 Pmax=11+21+31+33+45=151 W=1+11+21+23+45=101 (3)k=2，先装入2个，再装入其他，得到1,2,3,5,6最好 x1,x2,x3,x4,x5,x6,x7,x8=1,1,1,0,1,1,0,0 Pmax=11+21+31+43+53=159 W=109=1+11+2