算法分析及设计-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}，t1?t2?…?tn (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，则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+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(?)[I]1+? (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