信息学竞赛中搜索问题的常见优化技巧重庆一中黄晓愉【摘要】结合例题分析归纳了信息学竞赛中解决搜索问题所常用的思考方法与解题方法，从深度优先搜索和广度优先搜索两个方面探讨了提高程序效率的适用技巧。【关键词】１信息学；２搜索顺序；３搜索对象；４Hash表5剪枝。在信息学竞赛中解决搜索问题通常采用两种方法进行，即：深度优先搜索和广度优先搜索。一、深度优先搜索的优化技巧我们在做题的时候，经常遇到这类题目——给出约束条件，求一种满足约束条件的方案，这类问题我们叫它“约束满足”问题。对于约束满足问题，我们通常可以从搜索的顺序和搜索的对象入手，进而提高程序的效率。搜索的顺序及对象：在解决约束满足问题的时候，题目给出的约束条件越强，对于搜索中的剪枝就越有利。之所以深度优先搜索的效率在很大程度上优于穷举，就是因为它在搜索过程中很好的利用了题目中的约束条件进行剪枝，达到提高程序效率的目的。显然，在同样的一棵搜索树中，越在接近根接点的位置利用约束条件剪枝效果就越好。如何在搜索中最大化的利用题目的约束条件为我们提供剪枝的依据，是提高深度优先搜索效率的一个很重要的地方。而不同的搜索顺序和搜索对象就直接影响到我们对于题目约束条件的运用。下面，我们就从搜索的顺序和搜索的对象两方面来探讨一下不同的方法对程序效率的影响。（1）搜索顺序的选择：我们先来看一道比较简单的题目：(zju1937)已知一个数列a0,a1......am其中a0=1am=na0
