Tanky WooRSS

搜索与剪枝

19 Sep 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

半年前在POJ上遇到过一次剪枝的题目,那时觉得剪枝好神秘。。。今天在网上查了半天资料,终于还是摸索到了一点知识,但是相关资料并不多,在我看来,剪枝是技巧,而不是方法,也就是说,可能一点实用的小技巧,让程序可以少判断一点,这就是剪枝,剪枝无处不在。

搜索的进程可以看作是从树根出发,遍历一棵倒置的树----搜索树的过程。而所谓的剪枝,顾名思义,就是通过某种判断,避免一些不必要的遍历过程,形象的说,就是减去了搜索树中的某些“枝条”,故称剪枝。 (杭电课件上是这么说的:即剪去解答树上已被证明不可能存在可行解或最优解的子树.)

既然采用了搜索,剪枝就显得十分的必要,即使就简简单单的设一个槛值,或多加一两条判断,就可对搜索的效率产生惊人的影响。例如N后问题,假如放完皇后再判断,则仅仅只算到7,就开始有停顿,到了8就已经超过了20秒,而如果边放边判断,就算到了10,也没有停顿的感觉。所以,用搜索一般都就要剪枝。

剪枝至少有两方面,一是从方法上剪枝,如采用分枝定界,启发式搜索等,适用范围比较广;二是使用一些小技巧,这类方法适用性虽不如第一类,有时甚至只能适用一道题,但也十分有效,并且几乎每道题都存在一些这样那样的剪枝技巧,只是每题有所不同而已。

剪枝的原则: 1.正确性:必须保证不丢失正确的结果。 2.准确性:能够尽可能多的减去不能通向正解的枝条 3.高效性:在很多时候,为了加强优化的效果,我们会增加一些判断,这样对程序效率也带来了副作用,所以要考虑剪枝的高效性,否则得不偿失。

最后说一下:剪枝在搜索中用的是非常的广泛的。 ( 参照杭电课件第47页一句话: ACMer们: 为了ACM事业,努力地剪枝吧!! )

题目我不多说,HDOJ 1010就是一个很好的剪枝题目。 另外,杭电的课件--搜索篇里面也讲了搜索与剪枝。