算法合集之《搜索方法中的剪枝优化》.doc

搜索方法中的剪枝优化
南开中学齐鑫
【关键字】搜索、优化、剪枝
【摘要】本文讨论了搜索方法中最常见的一种优化技巧——剪枝,而且主要以剪枝判断方法的设计为核心。文章首先借助搜索树,形象的阐明了什么是剪枝;然后分析了设计剪枝判断方法的三个原则:正确、准确、高效,本文将常见的设计剪枝判断的思路分成可行性剪枝和最优性剪枝两大类,并结合上述三个原则分别以一道竞赛题为例作了说明;文章最后对剪枝方法作了一些总结
引子
搜索是人工智能中的一种基本方法,也是信息学竞赛选手所必须熟练掌握的一种方法。我们在建立一个搜索算法的时候,首要的问题不外乎两个:
建立算法结构。
选择适当的数据结构。
然而众所周知的是,搜索方法的时间复杂度大多是指数级的,简单的不加优化的搜索,其时间效率往往低的不能忍受,更是难以应付信息学竞赛严格的运行时间限制。
本文所讨论的主要内容就是在建立算法的结构之后,对程序进行优化的一种基本方法——剪枝。
图1 搜索树
首先应当明确的是,“剪枝”的含义是什么。我们知道,搜索的进程可以看作是从树根出发,遍历一棵倒置的树——搜索树的过程。而所谓剪枝,顾名思义,就是通过某种判断,避免一些不必要的遍历过程,形象的说,就是剪去了搜索树中的某些“枝条”,故称剪枝。
我们在编写搜索程序的时候,一般都要考虑到剪枝。显而易见,应用剪枝优化的核心问题是设计剪枝判断方法,即确定哪些枝条应当舍弃,哪些枝条应当保留的方法。设计出好的剪枝判断方法,往往能够使程序的运行时间大大缩短;否则,也可能适得其反。那么,我们就应当首先分析一下设计剪枝判断方法的时候,需要遵循的一些原则。
剪枝的原则
原则之一:正确性。
我们知道,剪枝方法之所以能够优化程序的执行效率,正如前文所述,是因为它能够“剪去”搜索树中的一些“枝条”。然而,如果在剪枝的时候,将“长有”我们所需要的解的枝条也剪掉了,那么,一切优化也就都失去了意义。所以,对剪枝的第一个要求就是正确性,即必须保证不丢失正确的结果,这是剪枝优化的前提。
为了满足这个原则,我们就应当利用“必要条件”来进行剪枝判断。也就是说,通过解所必须具备的特征、必须满足的条件等方面来考察待判断的枝条能否被剪枝。这样,就可以保证所剪掉的枝条一定不是正解所在的枝条。当然,由必要条件的定义,我们知道,没有被剪枝不意味着一定可以得到正解(否则,也就不必搜索了)。
原则之二:准确性。
在保证了正确性的基础上,对剪枝判断的第二个要求就是准确性,即能够尽可能多的剪去不能通向正解的枝条。剪枝方法只有在具有了较高的准确性的时候,才能真正收到优化的效果。因此,准确性可以说是剪枝优化的生命。
当然,为了提高剪枝判断的准确性,我们就必须对题目的特点进行全面而细致的分析,力求发现题目的本质,从而设计出优秀的剪枝判断方案。
原则之三:高效性。
一般说来,设计好剪枝判断方法之后,我们对搜索树的每个枝条都要执行一次判断操作。然而,由于是利用出解的“必要条件”进行判断,所以,必然有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作,对于程序的效率的提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用,我们除了要下功夫改善判断的准确性外,经常还需要提高判断操作本身的时间效率。
然而这就带来了一个矛盾:我们为了加强优化的效果,就必须提高剪枝判断的准确性,因此,常常不得不提高判断操作的复杂度,也就同时降低了剪枝判断的时间效率;但是,如果剪枝判断的时间消耗过多,就有可能减小、甚至完全抵消提高判断准确性所能带来的优化效果,这恐怕也是得不偿失。很多情况下,能否较好的解决这个矛盾,往往成为搜索算法优化的关键。
综上所述,我们可以把剪枝优化的主要原则归结为六个字:正确、准确、高效。
当然,我们在应用剪枝优化的时候,仅有上述的原则是不够的,还需要具体研究一些设计剪枝判断方法的思路。我们可以把常用的剪枝判断大致分成以下两类:
可行性剪枝。
最优性剪枝(上下界剪枝)。
下面,我们就结合上述的三个原则,分别对这两种剪枝判断方法进行一些讨论。
三、可行性剪枝
我们已经知道,搜索过程可以看作是对一棵树的遍历。在很多情况下,并不是搜索树中的所有枝条都能通向我们需要的结果,很多的枝条实际上只是一些死胡同。如果我们能够在刚刚进入这样的死胡同的时候,就能够判断出来并立即剪枝,程序的效率往往会得到提高。而所谓可行性剪枝,正是基于这样一种考虑。
下面我们举一个例子——Betsy的旅行(USACO)。
题目简述:一个正方形的小镇被分成N2个小方格,Betsy要从左上角的方格到达左下角的方格,并且经过每个方格恰好一次。编程对于给定的N,计算出Betsy能采用的所有的旅行路线的数目。
我们用深度优先的回溯方法来解决这个问题:Betsy从左上角出发,每一