信息学竞赛中搜索问题的常见优化技巧
重庆一中黄晓愉
【摘要】结合例题分析归纳了信息学竞赛中解决搜索问题所常用的思考方法与解题方法，从深度优先搜索和广度优先搜索两个方面探讨了提高程序效率的适用技巧。
【关键词】１信息学；２搜索顺序；３搜索对象；４Hash表5剪枝。
在信息学竞赛中解决搜索问题通常采用两种方法进行，即：深度优先搜索和广度优先搜索。
一、深度优先搜索的优化技巧
我们在做题的时候，经常遇到这类题目——给出约束条件，求一种满足约束条件的方案，这类问题我们叫它“约束满足”问题。对于约束满足问题，我们通常可以从搜索的顺序和搜索的对象入手，进而提高程序的效率。
搜索的顺序及对象：
在解决约束满足问题的时候，题目给出的约束条件越强，对于搜索中的剪枝就越有利。之所以深度优先搜索的效率在很大程度上优于穷举，就是因为它在搜索过程中很好的利用了题目中的约束条件进行剪枝，达到提高程序效率的目的。
显然，在同样的一棵搜索树中，越在接近根接点的位置利用约束条件剪枝效果就越好。如何在搜索中最大化的利用题目的约束条件为我们提供剪枝的依据，是提高深度优先搜索效率的一个很重要的地方。而不同的搜索顺序和搜索对象就直接影响到我们对于题目约束条件的运用。
下面，我们就从搜索的顺序和搜索的对象两方面来探讨一下不同的方法对程序效率的影响。
（1）搜索顺序的选择：
我们先来看一道比较简单的题目：(zju1937) 已知一个数列a0,a1......am其中
a0=1 am=n
a0 对于每个k(1<=k<=m),ak=ai+aj(0<=i,j<=k-1)，这里i与j可以相等。 现给定n的值，要求m的最小值（并不要求输出）,及这个数列的值(可能存在多个数列,只输出任一个满足条件的就可以了)。 分析 由于ak=ai+aj(0<=i,j N 用0.03 0.01 0.03 0.05 0.20 0.34 1.80 1.80 8.91 10.1 时 ong ong ong ong 10 20 30 40 50 60 70 80 90 100 200 Tool300 Tool400 Tool500 Tool 由于题目要求的是m的最小值，也就是需要我们尽快得到数n，所以每次构造的数应当是尽可能大的数，根据题目的这个特性，我们将搜索顺序改为从大到小搜索每个数，新程序的效率如下： N 用时 10 20 30 40 50 60 70 80 90 100 200 300 400 500 0.01 0.01 0.01 0.01 0.01 0.01 0.03 0.01 0.03 0.03 0.13 1.48 1.5 22.88 显然，后一种搜索顺序得到的程序效率大大地优于第一种搜索顺序得到的程序。 当然，这道题还有很大的优化余地，但是搜索顺序这种思想在搜索的题目中是广泛运用的。也许大家会觉得这种单一的运用搜索顺序来优化程序的方法很普通，但是这种看似简单的方法在考试中出现得也不少，例如IOI2000中的BLOCK，只要将木块从大到小经过旋转和反转后，依次放入进行搜索，对于比赛中的数据就可以得到满分。 最近的一次出现是NOI2005中的智慧珠，同样的只是将珠子从大到小进行搜索，不加任何其他剪枝就可以在比赛中获得90分。 可见，选择合适的搜索顺序对于提高程序的效率是编程设计最有效的技巧之一，运用良好的搜索顺序来对搜索题目进行优化是一个性价比很高的算法。 （2）搜索对象的选择： 让我们再来看看下面一道题：(USACO－weight) 已知原数列a1，a2……an中前1项，前2项，前3项……前n项的和,以及后1项,后2项,后3项……后n项的和，但是所有的数据都已经被打乱了顺序，还知道数列中的数存在集合Ｓ中，求原数列。当存在多组可能数列的时候求左边的数最小的数列。 其中n<=1000,S∈{1..500} 例如，假如原数列为11525，S={1，2，4，5}那么知道的值就是(12791457121314) 1=15=5 2=1+17=2+5 7=1+1+512=5+2+5 9=1+1+5+213=1+5+2+5 14=1+1+5+2+514=1+1+5+2+5 分析 因为题目中的Ｓ∈{1..500}，最坏的情况下每个数可以取到的值有500种，从数学方面很难找到有较好方法予以解决，而采用搜索方法却是一种很好的解决办法，根据数列从左往右依次搜索原数列每个数可能的值，然后与所知道的值进行比较。这样，我们得到了一个最简单的搜索方法A。 但是搜索方法A的这个算法最坏的情况下扩展的节点为5001000，运算速度太慢了。 在这个算法中，我们对数列中的每个数分别进行了500次搜索，由此导致了搜索量如此之大。如何有效的减少搜索量是提高本题算法效率的关键。而前面提到的运用搜索顺序的方法在本题中由于规定了左边的数最小而无法运用。让我们换个角度对这