谈搜索算法的剪枝优化.doc

谈搜索算法的剪枝优化
许晋炫
【摘要】本文讨论了搜索算法中“剪枝”这一常见的优化技巧。首先由回溯法解决迷宫问题展开论述,介绍了什么是剪枝;而后分析剪枝的三个原则棗正确、准确、高效,并分别就剪枝的两种思路:可行性剪枝及最优性剪枝,结合例题作进一步的阐述;最后对剪枝优化方法进行了一些总结。
【关键字】搜索、优化、剪枝、时间复杂度
引论
在竞赛中,我们有时会碰到一些题目,它们既不能通过建立数学模型解决,又没有现成算法可以套用,或者非遍历所有状况才可以得出正确结果。这时,我们就必须采用搜索算法来解决问题。
     搜索算法按搜索的方式分有两类,一类是深度优先搜索,一类是广度优先搜索。我们知道,深度搜索编程简单,程序简洁易懂,空间需求也比较低,但是这种方法的时间复杂度往往是指数级的,倘若不加优化,其时间效率简直无法忍受;而广度优先搜索虽然时间复杂度比前者低一些,但其庞大的空间需求量又往往让人望而却步。
     所以,对程序进行优化,就成为搜索算法编程中最关键的一环。
     本文所要讨论的便是搜索算法中优化程序的一种基本方法棗“剪枝”。
什么是剪枝
     相信刚开始接触搜索算法的人,都做过类似迷宫这样的题目吧。我们在“走迷宫”的时候,一般回溯法思路是这样的:
     1、这个方向有路可走,我没走过
     2、往这个方向前进
     3、是死胡同,往回走,回到上一个路口
     4、重复第一步,直到找着出口
     这样的思路很好理解,编程起来也比较容易。但是当迷宫的规模很大时,回溯法的缺点便暴露无遗:搜索耗时极巨,无法忍受。
     我们可不可以在向某个方向前进时,先一步判断出这样走会不会走到死胡同里呢?这样一来,搜索的时间不就可以减少了吗?
     答案是:可以的。
     剪枝的概念,其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树的遍历,那么剪枝顾名思义,就是将树中的一些“死胡同”,不能到达我们需要的解的枝条“剪”掉,以减少搜索的时间。
搜索算法,绝大部分需要用到剪枝。然而,不是所有的枝条都可以剪掉,这就需要通过设计出合理的判断方法,以决定某一分支的取舍。在设计判断方法的时候,需要遵循一定的原则。
剪枝的原则
     1、正确性
     正如上文所述,枝条不是爱剪就能剪的。如果随便剪枝,把带有最优解的那一分支也剪掉了的话,剪枝也就失去了意义。所以,剪枝的前提是一定要保证不丢失正确的结果。
     2、准确性
     在保证了正确性的基础上,我们应该根据具体问题具体分析,采用合适的判断手段,使不包含最优解的枝条尽可能多的被剪去,以达到程序“最优化”的目的。可以说,剪枝的准确性,是衡量一个优化算法好坏的标准。
     3、高效性设计优化程序的根本目的,是要减少搜索的次数,使程序运行的时间减少。但为了使搜索次数尽可能的减少,我们又必须花工夫设计出一个准确性较高的优化算法,而当算法的准确性升高,其判断的次数必定增多,从而又导致耗时的增多,这便引出了矛盾。
因此,如何在优化与效率之间寻找一个平衡点,使得程序的时间复杂度尽可能降低,同样是非常重要的。倘若一个剪枝的判断效果非常好,但是它却需要耗费大量的时间来判断、比较,结果整个程序运行起来也跟没有优化过的没什么区