《算法分析——8.ppt》由会员分享，可在线阅读，更多相关《算法分析——8.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法设计与分析算法设计与分析近似算法近似算法NP完全问题完全问题lNP完全问题完全问题lNondeterministic Polynomial Completel一个问题的计算复杂性可以通过解决该问题所需要的计算量来描述。l通常将可在多项式时间内解决的问题看作是多项式时间内解决的问题看作是“易易”问题问题；将需要指数函数时间解决的问题看作是指数函数时间解决的问题看作是“难难”问题问题；lNP类问题的计算复杂性状况至今未知，但许多现象表明这类问题可能是“难”解的。l在NP类问题中，NP完全问题类构成了NP类问题的核心l其困难性体现在任何一个任何一个NP类问题可以在多项式时间内转换类问题可以在多项
2、式时间内转换为一个为一个NP完全问题完全问题。l如果有一个如果有一个NP完全问题能在多项式时间内得到解决，那么完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解。中的每一个问题都可以在多项式时间内求解。但目前还没有但目前还没有一个一个NP完全问题有多项式时间算法。完全问题有多项式时间算法。如何求解如何求解NP完全问题？完全问题？NP完全完全问题问题如何求解如何求解？可行的解题策略可行的解题策略只对问题的特殊实例求解只对问题的特殊实例求解用动态规划法或分支限界法求解用动态规划法或分支限界法求解用概率算法求解用概率算法求解只求近似解只求近似解用启发式方法求解用启发式方
3、法求解可行的解题策略可行的解题策略只对问题的只对问题的特殊实例特殊实例求解求解用动态规划法或分支限界法求解用动态规划法或分支限界法求解用概率算法求解用概率算法求解只求近似解只求近似解用启发式方法求解用启发式方法求解策略一策略一l策略一策略一l只对问题的特殊实例求解只对问题的特殊实例求解l当遇到一个NP完全问题时（如调度问题），不仅要了解该问题的一般性，更要审视该特殊实例所具有的特性（比如解空间规模、可接受解的质量、工作流要求等）；往往在某种特殊情形进行问题求解时，常常会有高效的求解算法（比如Johnson法则、MS算法等）可行的解题策略可行的解题策略只对问题的特殊实例求解只对问题的特殊实例求解
4、用用动态规划法动态规划法或或分支限界法分支限界法求解求解用概率算法求解用概率算法求解只求近似解只求近似解用启发式方法求解用启发式方法求解策略二策略二l策略二策略二l用动态规划法或分支限界法求解用动态规划法或分支限界法求解l动态规划法动态规划法利用子问题的重叠性质，减少计算量l分支限界法分支限界法利用限界函数和剪枝函数，缩小解空间范围可行的解题策略可行的解题策略只对问题的特殊实例求解只对问题的特殊实例求解用动态规划法或分支限界法求解用动态规划法或分支限界法求解用用概率算法概率算法求解求解只求近似解只求近似解用启发式方法求解用启发式方法求解策略三策略三l策略三策略三l用概率算法求解用概率算法求解l
5、有时通过概率分析法证明某个完全问题的“难”实例是比较稀少的，因此可以采用概率算法求解这类完全问题，设计出在平均情况下的高效算法。考虑解精确性的可接受程度可行的解题策略可行的解题策略只对问题的特殊实例求解只对问题的特殊实例求解用动态规划法或分支限界法求解用动态规划法或分支限界法求解用概率算法求解用概率算法求解只求只求近似解近似解用启发式方法求解用启发式方法求解策略四策略四l策略四策略四l只求近似解只求近似解l在实际中遇到的完全问题不一定需要非常精确的解答（考虑实际输入数据的精度以及实际问题的要求）可以采用近似算法来求解完全问题，在较短的时间内得到一个可接受的近似解在实践中非常有效可行的解题策略可
6、行的解题策略只对问题的特殊实例求解只对问题的特殊实例求解用动态规划法或分支限界法求解用动态规划法或分支限界法求解用概率算法求解用概率算法求解只求近似解只求近似解用用启发式方法启发式方法求解求解策略五策略五l策略五策略五l用启发式方法求解用启发式方法求解l根据具体问题，设计启发式搜索策略实践中有效理论上？可行的解题策略可行的解题策略只对问题的特殊实例求解只对问题的特殊实例求解用动态规划法或分支限界法求解用动态规划法或分支限界法求解用概率算法求解用概率算法求解只求近似解只求近似解用启发式方法求解用启发式方法求解提纲提纲l近似算法的性能l顶点覆盖问题的近似算法lTSP问题的近似算法l集合覆盖问题的近
7、似算法l子集和问题的近似算法l本章小节提纲提纲l近似算法的性能近似算法的性能l顶点覆盖问题的近似算法lTSP问题的近似算法l集合覆盖问题的近似算法l子集和问题的近似算法l本章小节近似算法的性能评估指标近似算法的性能评估指标l许多完全问题实质上是最优化问题许多完全问题实质上是最优化问题l要求获得的解使某个目标函数达到极大（或极小）要求获得的解使某个目标函数达到极大（或极小）l对于确定的问题，不失一般性，我们假设其每一个可行解假设其每一个可行解所对应的目标函数值都不小于一个确定的正数。所对应的目标函数值都不小于一个确定的正数。l近似算法的性能评估指标近似算法的性能评估指标l性能比性能比l相对误差相
8、对误差近似算法的性能比近似算法的性能比性能比性能比&近似解的质量近似解的质量相对误差相对误差相对误差界相对误差界性能比性能比&相对误差界相对误差界对于有些对于有些NP完全问题，可以找到这样的近似算法，完全问题，可以找到这样的近似算法，其性能比可以通过增加计算量来改进。其性能比可以通过增加计算量来改进。提纲提纲l近似算法的性能l顶点覆盖问题的近似算法顶点覆盖问题的近似算法lTSP问题的近似算法l集合覆盖问题的近似算法l子集和问题的近似算法l本章小节顶点覆盖问题顶点覆盖问题uzyvxw大小为2的顶点覆盖V=w,z最优化顶点覆盖问题：最优化顶点覆盖问题：找图找图G的最小顶点覆盖的最小顶点覆盖NP难问
9、题难问题近似算法实现近似算法实现VertexSet approxVertexCover(Graph g)cset=空集；e1=g.e;while(e1!=空集）从e1中任取一条边(u,v)；cset=csetu,v;从e1中删除与u,v相连的所有边；return c;以无向图G为输入Cset存储顶点覆盖中的各顶点该算法计算出的近该算法计算出的近似最优顶点覆盖的大小似最优顶点覆盖的大小不会超过最小顶点覆盖不会超过最小顶点覆盖大小的大小的2倍。倍。实例说明实例说明bacegdf无向图无向图实例说明实例说明bacegdf首先选取边(b,c)，并将顶点b,c加入到顶点覆盖集c中，然后将与顶点b,c相关
10、联的边从e1中删除实例说明实例说明bacegdf然后选取边(e,f)，并将顶点e,f加入到顶点覆盖集c中，然后将与顶点e,f相关联的边从e1中删除实例说明实例说明bacegdf选取边(d,g)，并将顶点d,g加入到顶点覆盖集c中，然后将与顶点d,g相关联的边从e1中删除实例说明实例说明bacegdf近似最优解算法得到的最小顶点近似最优解算法得到的最小顶点覆盖（大小为覆盖（大小为6）bacegdf图的最小顶点覆盖图的最小顶点覆盖（大小为）（大小为）算法性能分析算法性能分析算法的性能比为算法的性能比为2提纲提纲l近似算法的性能l顶点覆盖问题的近似算法lTSP问题的近似算法问题的近似算法l集合覆盖问
11、题的近似算法l子集和问题的近似算法l本章小节TSP问题问题近似算法设计近似算法设计l近似算法设计近似算法设计l用找图G的最小生成树的算法设计找近似最优的TSP算法。l当费用函数满足三角不等式当费用函数满足三角不等式（即两边的费用和不小于第三边）时，算法找出的TSP回路的费用不会超过最优TSP回路费用的2倍。算法实现算法实现Void approTSP(Graph g)（1）选择g的任一顶点r；（2）用Prim算法找出图g的一棵以r为根的最小生成树T；（3）前序遍历树T得到的顶点表L；（4）将r加到表L的末尾，按表L中顶点次序组成回路H实例说明实例说明abchfdeg实例说明实例说明abchfde
12、g最小生成树T实例说明实例说明abchfdeg15678432前序遍历树T得到的顶点表L实例说明实例说明abchfdeg15678432将r加到表L的末尾，按表L中顶点次序组成回路H近似算法得近似算法得到的近似最到的近似最优优TSP回路回路实例说明实例说明abchfdeg15678432最优TSP回路近似最优TSP回路性能分析性能分析l性能分析性能分析l当费用函数满足三角不等式时，算法的性能比为当费用函数满足三角不等式时，算法的性能比为2l证明参看教材page331l当费用函数不满足三角不等式时（即对于一般情况）当费用函数不满足三角不等式时（即对于一般情况），不存在具有常数性能比的解，不存在具
13、有常数性能比的解TSP问题的多项式时问题的多项式时间近似算法（除非间近似算法（除非P=NP）。）。l参看教材page331-332提纲提纲l近似算法的性能l顶点覆盖问题的近似算法lTSP问题的近似算法l集合覆盖问题的近似算法集合覆盖问题的近似算法l子集和问题的近似算法l本章小节集合覆盖问题集合覆盖问题集合覆盖问题是许多常见组合问题的抽象。集合覆盖问题是许多常见组合问题的抽象。比如具有不同技能的人员的组合问题。比如具有不同技能的人员的组合问题。实例实例S1S3S4S6S2S5算法设计算法设计Set greedySetCover(X,F)U=X;C=空集；while(U!=空集）选择F中使|SU|
14、最大的子集S；U=U-S；C=C U S；return C;具有对数性能比的近似算法（采用贪心策略）该算法是一个多项该算法是一个多项式时间算法式时间算法结果结果S1S3S4S6S2S5S1S3S4S6S2S5近似结果近似结果最优结果最优结果提纲提纲l近似算法的性能l顶点覆盖问题的近似算法lTSP问题的近似算法l集合覆盖问题的近似算法l子集和问题的近似算法子集和问题的近似算法l本章小节 子集合问题子集合问题NP完全问题完全问题求解方案求解方案l求解方案求解方案l精确方法求解l近似方法求解精确求解方案精确求解方案l精确求解方案精确求解方案l考虑子集合S1中所有可能的不超过T的子集合l指数时间算法举
15、例：举例：S=1,4,5P0=0P1=0,1P2=0,1,4,5P3=0,1,4,5,6,9,10算法流程算法流程Int exactSubsetSum(S,t)int n=|S|;L0=0;for(int i=1;i=n;i+)Li=mergeLists(Li-1,Li-1+Si);删去Li中超过T的元素；return max(Ln);Pi-1=Pi-1 U(Pi-1+xi)Li中包含中包含Pi中所有不超过中所有不超过T的元素的有序表的元素的有序表近似求解方案近似求解方案l近似求解方案近似求解方案l完全多项式时间近似格式l引入修整参数,01l思想：从思想：从LiLi 中删除尽可能多的元素，使得每一个中删除尽可能多的元素，使得每一个从从LiLi 中删除的元素中删除的元素y y，都有一个修整后的表，都有一个修整后的表LiLi 中的元素中的元素z z满足满足(1-(1-)yzyz y.y.l将z看作事被删除元素y在修整后的新表中的代表。注意的设置对结果误差的影响l参看教材参看教材page337-340page337-340提纲提纲l近似算法的性能l顶点覆盖问题的近似算法lTSP问题的近似算法l集合覆盖问题的近似算法l子集和问题的近似算法l本章小节本章小节本章小节本章小节l本章小节本章小节lNP完全问题的求解策略l近似算法的性能l实例说明