2006 年全国信息学冬令营讲座
信息学竞赛中搜索问题的常见优化技巧
重庆一中 黄晓愉
【摘要】结合例题分析归纳了信息学竞赛中解决搜索问题所常用的思考方法与解题方法，从深度
优先搜索和广度优先搜索两个方面探讨了提高程序效率的适用技巧。
【关键词】１信息学；２搜索顺序；３搜索对象；４ Hash 表 5 剪枝。
在信息学竞赛中解决搜索问题通常采用两种方法进行，即：深度优先搜索和广
度优先搜索。
一、深度优先搜索的优化技巧
我们在做题的时候，经常遇到这类题目——给出约束条件，求一种满足约束条
件的方案，这类问题我们叫它“约束满足”问题。对于约束满足问题，我们通常可以从
搜索的顺序和搜索的对象入手，进而提高程序的效率。
搜索的顺序及对象：
在解决约束满足问题的时候，题目给出的约束条件越强，对于搜索中的剪枝就
越有利。之所以深度优先搜索的效率在很大程度上优于穷举，就是因为它在搜索过
程中很好的利用了题目中的约束条件进行剪枝，达到提高程序效率的目的。
显然，在同样的一棵搜索树中，越在接近根接点的位置利用约束条件剪枝效果
就越好。如何在搜索中最大化的利用题目的约束条件为我们提供剪枝的依据，是提
高深度优先搜索效率的一个很重要的地方。而不同的搜索顺序和搜索对象就直接影
响到我们对于题目约束条件的运用。
下面，我们就从搜索的顺序和搜索的对象两方面来探讨一下不同的方法对程序
效率的影响。
（1）搜索顺序的选择：
我们先来看一道比较简单的题目： (zju1937)
已知一个数列 a0,a1......am 其中
a0 = 1
am = n
a0 < a1 < a2 < ... < am-1 < am
对于每个 k(1<=k<=m),ak=ai+aj (0 <= i, j <= k-1)，这里 i 与 j 可以相等。
现给定 n 的值，要求 m 的最小值（并不要求输出）,及这个数列的值(可能存在
多个数列,只输出任一个满足条件的就可以了)。
分析 由于 a
k
=a
i
+a
j
(0<=i,j<k),所以我们在搜索的过程中可以采用由小到大搜索数列的
每一项的搜索顺序进行试算。在一般搜索的时候我们习惯于从小到大依次搜索每个数的取值，但
是在这到题目中按照这样的顺序搜索编程运算其结果（效率）十分不理想：
1
评论0