算法分析——8

《算法分析——8》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析——近似算法NP完全问题NP完全问题NondeterministicPolynomialComplete一个问题的计算复杂性可以通过解决该问题所需要的计算量来描述。通常将可在多项式时间内解决的问题看作是“易”问题；将需要指数函数时间解决的问题看作是“难”问题；NP类问题的计算复杂性状况至今未知，但许多现象表明这类问题可能是“难”解的。在NP类问题中，NP完全问题类构成了NP类问题的核心其困难性体现在任何一个NP类问题可以在多项式时间内转换为一个NP完全问题。如果有一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解。但目前还没有一个NP完

2、全问题有多项式时间算法。如何求解NP完全问题？NP完全问题如何求解？可行的解题策略只对问题的特殊实例求解用动态规划法或分支限界法求解用概率算法求解只求近似解用启发式方法求解可行的解题策略只对问题的特殊实例求解用动态规划法或分支限界法求解用概率算法求解只求近似解用启发式方法求解策略一策略一只对问题的特殊实例求解当遇到一个NP完全问题时（如调度问题），不仅要了解该问题的一般性，更要审视该特殊实例所具有的特性（比如解空间规模、可接受解的质量、工作流要求等）；往往在某种特殊情形进行问题求解时，常常会有高效的求解算法（比如Johnson法则、MS算法等）可行的解题策略只对问题的特殊实例求解用动态规

3、划法或分支限界法求解用概率算法求解只求近似解用启发式方法求解策略二策略二用动态规划法或分支限界法求解动态规划法利用子问题的重叠性质，减少计算量分支限界法利用限界函数和剪枝函数，缩小解空间范围可行的解题策略只对问题的特殊实例求解用动态规划法或分支限界法求解用概率算法求解只求近似解用启发式方法求解策略三策略三用概率算法求解有时通过概率分析法证明某个ＮＰ完全问题的“难”实例是比较稀少的，因此可以采用概率算法求解这类ＮＰ完全问题，设计出在平均情况下的高效算法。考虑解精确性的可接受程度可行的解题策略只对问题的特殊实例求解用动态规划法或分支限界法求解用概率算法求解只求近似解用启发式方法求解策略四策略

4、四只求近似解在实际中遇到的ＮＰ完全问题不一定需要非常精确的解答（考虑实际输入数据的精度以及实际问题的要求）可以采用近似算法来求解ＮＰ完全问题，在较短的时间内得到一个可接受的近似解——在实践中非常有效可行的解题策略只对问题的特殊实例求解用动态规划法或分支限界法求解用概率算法求解只求近似解用启发式方法求解策略五策略五用启发式方法求解根据具体问题，设计启发式搜索策略实践中——有效理论上——？可行的解题策略只对问题的特殊实例求解用动态规划法或分支限界法求解用概率算法求解只求近似解用启发式方法求解提纲近似算法的性能顶点覆盖问题的近似算法TSP问题的近似算法集合覆盖问题的近似算法子集和问题的近似算法

5、本章小节提纲近似算法的性能顶点覆盖问题的近似算法TSP问题的近似算法集合覆盖问题的近似算法子集和问题的近似算法本章小节近似算法的性能评估指标许多ＮＰ完全问题实质上是最优化问题要求获得的解使某个目标函数达到极大（或极小）＊对于确定的问题，不失一般性，我们假设其每一个可行解所对应的目标函数值都不小于一个确定的正数。近似算法的性能评估指标性能比相对误差近似算法的性能比性能比&近似解的质量相对误差相对误差界性能比&相对误差界对于有些NP完全问题，可以找到这样的近似算法，其性能比可以通过增加计算量来改进。提纲近似算法的性能顶点覆盖问题的近似算法TSP问题的近似算法集合覆盖问题的近似算法子集和问题的

6、近似算法本章小节顶点覆盖问题uzyvxw大小为2的顶点覆盖V’=｛w,z}最优化顶点覆盖问题：找图G的最小顶点覆盖NP难问题近似算法实现VertexSetapproxVertexCover(Graphg){cset=空集；e1=g.e;while(e1!=空集）｛从e1中任取一条边(u,v)；cset=csetＵ{u,v};从e1中删除与u,v相连的所有边；}returnc;}以无向图G为输入Cset存储顶点覆盖中的各顶点——该算法计算出的近似最优顶点覆盖的大小不会超过最小顶点覆盖大小的2倍。实例说明bacegdf无向图Ｇ实例说明bacegdf首先选取边(b,c)，并将顶点b,c加入到顶

7、点覆盖集c中，然后将与顶点b,c相关联的边从e1中删除实例说明bacegdf然后选取边(e,f)，并将顶点e,f加入到顶点覆盖集c中，然后将与顶点e,f相关联的边从e1中删除实例说明bacegdf选取边(d,g)，并将顶点d,g加入到顶点覆盖集c中，然后将与顶点d,g相关联的边从e1中删除实例说明bacegdf近似最优解算法得到的最小顶点覆盖（大小为6）bacegdf图Ｇ的最小顶点覆盖（大小为３）算法性能分析算法的性能比为2提纲近似