1、- 56 - IOI99 中国集训队优秀论文选搜索方法中的剪枝优化南开中学 齐鑫【关键字】搜索、优化、剪枝【摘要】本文讨论了搜索方法中最常见的一种优化技巧剪枝，而且主要以剪枝判断方法的设计为核心。文章首先借助搜索树，形象的阐明了什么是剪枝；然后分析了设计剪枝判断方法的三个原则：正确、准确、高效，本文将常见的设计剪枝判断的思路分成可行性剪枝和最优性剪枝两大类，并结合上述三个原则分别以一道竞赛题为例作了说明；文章最后对剪枝方法作了一些总结。搜索中的剪枝优化IOI99 中国集训队优秀论文选 - 57 -一、引子搜索是人工智能中的一种基本方法，也是信息学竞赛选手所必须熟练掌握的一种方法。我们在建立一个
2、搜索算法的时候，首要的问题不外乎两个：1.建立算法结构。2.选择适当的数据结构。然而众所周知的是，搜索方法的时间复杂度大多是指数级的，简单的不加优化的搜索，其时间效率往往低的不能忍受，更是难以应付信息学竞赛严格的运行时间限制。本文所讨论的主要内容就是在建立算法的结构之后，对程序进行优化的一种基本方法剪枝。首先应当明确的是， “剪枝”的含义是什么。我们知道，搜索的进程可以看作是从树根出发，遍历一棵倒置的树搜索树的过程。而所谓剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条” ，故称剪枝。我们在编写搜索程序的时候，一般都要考虑到剪枝。显而易见，应
3、用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。设计出好的剪枝判断方法，往往能够使程序的运行时间大大缩短；否则，也可能适得其反。那么，我们就应当首先分析一下设计剪枝判断方法的时候，需要遵循的一些原则。图 1 搜索树搜索中的剪枝优化- 58 - IOI99 中国集训队优秀论文选二、剪枝的原则原则之一：正确性。我们知道，剪枝方法之所以能够优化程序的执行效率，正如前文所述，是因为它能够“剪去”搜索树中的一些“枝条” 。然而，如果在剪枝的时候，将“长有”我们所需要的解的枝条也剪掉了，那么，一切优化也就都失去了意义。所以，对剪枝的第一个要求就是正确性，即必须保证不
4、丢失正确的结果，这是剪枝优化的前提。为了满足这个原则，我们就应当利用“必要条件”来进行剪枝判断。也就是说，通过解所必须具备的特征、必须满足的条件等方面来考察待判断的枝条能否被剪枝。这样，就可以保证所剪掉的枝条一定不是正解所在的枝条。当然，由必要条件的定义，我们知道，没有被剪枝不意味着一定可以得到正解（否则，也就不必搜索了） 。原则之二：准确性。在保证了正确性的基础上，对剪枝判断的第二个要求就是准确性，即能够尽可能多的剪去不能通向正解的枝条。剪枝方法只有在具有了较高的准确性的时候，才能真正收到优化的效果。因此，准确性可以说是剪枝优化的生命。当然，为了提高剪枝判断的准确性，我们就必须对题目的特点进
5、行全面而细致的分析，力求发现题目的本质，从而设计出优秀的剪枝判断方案。原则之三：高效性。一般说来，设计好剪枝判断方法之后，我们对搜索树的每个枝条都要执行一次判断操作。然而，由于是利用出解的“必要条件”进行判断，所以，必然有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作，对于程序的效率的提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用，我们除了要下功夫改善判断的准确性外，经常还需要提高判断操作本身的时间效率。然而这就带来了一个矛盾：我们为了加强优化的效果，就必须提高剪枝判断的准确性，因此，常常不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但是，如果剪枝判断的时间搜索中
6、的剪枝优化IOI99 中国集训队优秀论文选 - 59 -消耗过多，就有可能减小、甚至完全抵消提高判断准确性所能带来的优化效果，这恐怕也是得不偿失。很多情况下，能否较好的解决这个矛盾，往往成为搜索算法优化的关键。综上所述，我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。当然，我们在应用剪枝优化的时候，仅有上述的原则是不够的，还需要具体研究一些设计剪枝判断方法的思路。我们可以把常用的剪枝判断大致分成以下两类：1.可行性剪枝。2.最优性剪枝（上下界剪枝） 。下面，我们就结合上述的三个原则，分别对这两种剪枝判断方法进行一些讨论。搜索中的剪枝优化- 60 - IOI99 中国集训队优秀论文选
7、三、可行性剪枝我们已经知道，搜索过程可以看作是对一棵树的遍历。在很多情况下，并不是搜索树中的所有枝条都能通向我们需要的结果，很多的枝条实际上只是一些死胡同。如果我们能够在刚刚进入这样的死胡同的时候，就能够判断出来并立即剪枝，程序的效率往往会得到提高。而所谓可行性剪枝，正是基于这样一种考虑。下面我们举一个例子Betsy 的旅行(USACO)。题目简述：一个正方形的小镇被分成 N2 个小方格，Betsy 要从左上角的方格到达左下角的方格，并且经过每个方格恰好一次。编程对于给定的 N，计算出 Betsy 能采用的所有的旅行路线的数目。我们用深度优先的回溯方法来解决这个问题：Betsy 从左上角出发，
8、每一步可以从一个格子移动到相邻的没有到过的格子中，遇到死胡同则回溯，当移动了 N2-1 步并达到左下角时，即得到了一条新的路径，继续回溯搜索，直至遍历完所有道路。但是，仅仅依照上述算法框架编程，时间效率极低，对 N=6 的情况无法很好的解决，所以，优化势在必行。对本题优化的关键就在于当搜索到某一个步骤时，能够提前判断出在后面的搜索过程中是否一定会遇到死胡同，而可行性剪枝正可以在这里派上用场。我们首先从“必要条件” ，即合法的解所应当具备的特征的角度分析剪枝的方法，主要有两个方向：1. 对于一条合法的路径，除出发点和目标格子外，每一个中间格子都必然有“一进一出”的过程。所以在搜索过程中，必须保证
9、每个尚未经过的格子都与至少两个尚未经过的格子相邻（除非当时Betsy 就在它旁边） 。这里，我们是从微观的角度分析问题。2. 在第一个条件的基础上，我们还可以从宏观的角度分析，进一步提高剪枝判断的准确性。显然，在一个合法的移动方案的任何时刻，都不可能有孤立的区域存在。虽然孤立区域中的每一个格子也可能都有至少两个相邻的空的格子，但它们作为一个整体，Betsy已经不能达到。我们也应当及时判断出这种情况，并避免之。以上两个剪枝判断条件都是正确的，其准确度也比较高。但是，仅仅满足这两点还不够，剪枝判断的操作过程还必须力求高效。假如我们在每次剪枝判断时，都简单的对 N2 个格子进行一遍扫描，其效率的低下
10、可想而知。因此，我们必须尽可能的简化判断的过程。实际上，由于 Betsy 的每一次移动，只会影响到附近的格子，搜索中的剪枝优化IOI99 中国集训队优秀论文选 - 61 -所以每次执行剪枝判断时，应当只对她附近的格子进行检查：对于第一个剪枝条件，我们可以设一个整型标志数组，分别保存与每个格子相邻的没被经过的格子的数目，Betsy 每次移动到一个新位置，都只会使与之相邻的至多 4 个格子的标志值发生变化，只要检查它们的标志值即可。而对于第二个剪枝条件，处理就稍稍麻烦一些。但我们仍然可以使用局部分析的方法，即只通过对 Betsy 附近的格子进行判断，就确定是否应当剪枝，下图简要说明了剪枝的原理：上
11、图给出了可以剪枝的三种情况。由于 Betsy 到过的所有格子都一定是四连通的，所以每种情况下的两个白色的格子之间必定是不连通的，它们当中必然至少有一个是属于某个孤立区域的，都一定可以剪枝。经过上述的优化，程序的时间效率有了很大的提高（参见附录） 。一般说来，可行性剪枝多用于路径搜索类的问题。除本例外，如 Prime Circle (ACM Asian Regional 96)等问题，也都可以使用这种剪枝方法。在应用可行性剪枝的时候，首先要多角度全面分析问题的特点（本题就是从微观和宏观两个角度设计剪枝方法） ，找到尽可能多的可以剪枝的情况；同时，还必须注意提高剪枝的时间效率，所以我们使用了“局部
12、判断”的方法，特别是在处理第二个剪枝条件时，更是通过局部判断来体现整体性质（是否有孤立区域） ，这一技巧不仅在设计剪枝方法的时候能够发挥作用，在其他方面也有着极为广已经到过的格子 尚未到过的格子 Betsy 的移动方向 Betsy 的位置图 2 剪枝原理示意图搜索中的剪枝优化- 62 - IOI99 中国集训队优秀论文选泛的应用。搜索中的剪枝优化IOI99 中国集训队优秀论文选 - 63 -三、最优性剪枝在我们平时遇到的问题中，有一大类是所谓最优化问题，即所要求的结果是最优解。如果我们使用搜索方法来解决这类问题，那么，最优性剪枝是一定要考虑到的。为了表述的统一，首先要作一些说明：我们知道，解的
13、优劣一般是通过一个评价函数来评判的。这里定义一个抽象的评价函数“优度” ，它的值越大，对应的解也就越优（对于具体的问题，我们可以认为“优度”代表正的收益或负的代价等） 。然后，我们再来回顾一下搜索最优解的过程：一般情况下，我们需要保存一个“当前最优解” ，实际上就是保存解的优度的一个下界。在遍历到搜索树的叶子节点的时候，我们就能得到一个新的解，当然也就得到了它的评价函数值，与保存的优度的下界作比较，如果新解的优度值更大，则这个优度值就成为新的下界。搜索结束后，所保存的解就是最优解。那么，最优性剪枝又是如何进行的呢？当我们处在搜索树的枝条上时，可以通过某种方法估算出该枝条上的所有解的评价函数的上
14、界，即所谓估价函数 。显然， 大于当前保存的优度的下界，是hh该枝条上存在最优解的必要条件，否则就一定可以剪枝。所以，最优性剪枝也可以称为“上下界剪枝” 。同时，我们也可以看到，最优性剪枝的核心问题就是估价函数的建立。下面举一个应用最优性剪枝的典型例题最少乘法次数。题目简述：由 开始，通过最少的乘法次数得出 ，其中 为输x nx入数据。 （参见参考书目 1）因为两式相乘等于方幂相加，所以本题可以等效的表示为：构造一个数列 ，满足ia)1(,1(ikjkji要求 ，并且使 最小。nt t我们选择回溯法作为本程序的主体结构：当搜索到第 层时，i的取值范围在 到 之间，为了尽快接近目标 ，应当从ia
15、1ia2*1i n开始从大到小为 取值，当然，选取的数都不能大于 。当搜2*1索到 出现时，就得到了一个解，与当前保存的解比较取优。最终n搜索结束之后，即得到最终的最优解。如果按上述结构直接进行搜索，效率显然很低。因此，我们可以考虑使用最优性剪枝进行优化：搜索中的剪枝优化- 64 - IOI99 中国集训队优秀论文选优化之一：当然首先要建立估价函数。由于使数列中的最大数加倍无疑是最快的增长方式，所以一种最简单的估价函数为（设数列中当前的最大者是 ，即当前搜索深度为 ）：iaiinh2log然而，这个估价函数的准确性太差，特别是当 大于 时， 只ia2nh能等于 1，根本不能发挥剪枝的作用。因此
16、，无论是深度优先的回溯法还是宽度优先的 A*搜索方法，只要还使用这个估价函数，其优化效果都比较有限。下面，我们再讨论一些进一步的优化手段优化之二：着眼于估价函数的“生命”准确性。我们可以利用加法在奇偶性上的特点的推广，使估价函数在某些情况下的准确性得到一定的提高（具体改进请参见附录） 。优化之三：我们新建立的这个估价函数虽然准确性稍有提高，但时间复杂度也相应提高。为了提高剪枝的效率，我们可以使用一种“逐步细化”的技巧，即先使用一次原先的估价函数（快而不准）进行“过滤” ，再使用新的估价函数（稍准但较慢）减少“漏网之鱼”，以求准确性和运行效率的平衡。优化之四：我们可以在搜索之前将 分解质因数，对
17、每个质因n数先使用上述搜索方法求解（如某个质因数仍太大，还可以将其减1，再分解） ，即相当于将构造数列的过程，划分成若干阶段处理。这样得到的结果虽然不一定是全局的最优解，却可以作为初始设定的优度下界，使后面的全局搜索少走很多弯路。事实上，该估计方法相当准确，在很多情况下都能直接得到最优解，使程序效率得到极大提高。优化之五：当数列中的当前最大数 超过 后，原估价函数就ia2n难以发挥作用了。但是，此后的最优方案，实际上就等价于从 到1a这 个数中，选出尽可能少的数（可重复） ，使它们的和等于 。这ia n个问题已经可以使用动态规划方法来解决。这样得到的“估价函数”不但完全准确，甚至直接就可以代替
18、后面的搜索过程。这里也体现出了搜索和动态规划的优势互补。这道题中所体现的最优性剪枝技巧是很多的，它们的优化效果也是非常显著的（优化效果的分析请参见附录） 。由本题，并结合以前的经验，我们可以简单的总结一些在应用最优性剪枝时需注意的问题：1. 估价函数的设计当然首先得满足正确的原则，即使用“必要搜索中的剪枝优化IOI99 中国集训队优秀论文选 - 65 -条件”来剪枝。在此基础上，就要注意提高估价的准确性。本题的优化之二就是为了这个目的。2. 与其他剪枝判断操作一样，最优性剪枝的估价函数在提高准确性的同时，也必须注意使计算过程尽量高效的原则。由于剪枝判断在运行时执行极为频繁，所以对其算法进行精雕
19、细琢是相当必要的，有时甚至还可以使用一些非常手法，如前述的“逐步细化”技巧，就是一种寻求时间效率和精确度相平衡的方法。3. 在使用最优性剪枝时，一个好的初始“优度”下界往往是非常重要的。在搜索开始之前，我们可以使用某种高效方法（如贪心法等）求出一个较优解，作为初始下界，经常可以剪去大量明显不可能的枝条。本题使用划分阶段的搜索方法进行初始定界，就带来了大幅度的优化。4. 本节所举的是在深度优先搜索中应用最优性剪枝的例子。当然，在广度优先搜索中，也是可以使用最优性剪枝的，也就是我们常说的分枝定界方法。本题也可以使用分枝定界结合 A*算法的方法来解决（用改进的估价函数作为优度上界估计，即 h*函数；前述的动态规划方法可以作为优度下界估计） ，但时间效率和空间效率都要差一些。不过，在有些问题中，分枝定界和 A*算法的结合以其较好的稳定性，还是有用武之地的。
