《2023年算法合集之信息学竞赛中搜索问题的常见优化技巧》由会员分享，可在线阅读，更多相关《2023年算法合集之信息学竞赛中搜索问题的常见优化技巧（10页珍藏版）》请在金锄头文库上搜索。
1、信息学竞赛中搜索问题的常见优化技巧重庆一中 黄晓愉【摘要】结合例题分析归纳了信息学竞赛中解决搜索问题所常用的思考方法与解题方法，从深度优先搜索和广度优先搜索两个方面探讨了提高程序效率的合用技巧。 【关键词】信息学；搜索顺序；搜索对象；Hash表 5剪枝。在信息学竞赛中解决搜索问题通常采用两种方法进行，即：深度优先搜索和广度优先搜索。一、深度优先搜索的优化技巧我们在做题的时候，经常碰到这类题目给出约束条件，求一种满足约束条件的方案，这类问题我们叫它“约束满足”问题。对于约束满足问题，我们通常可以从搜索的顺序和搜索的对象入手，进而提高程序的效率。搜索的顺序及对象：在解决约束满足问题的时候，题目给出
2、的约束条件越强，对于搜索中的剪枝就越有利。之所以深度优先搜索的效率在很大限度上优于穷举，就是由于它在搜索过程中很好的运用了题目中的约束条件进行剪枝，达成提高程序效率的目的。显然，在同样的一棵搜索树中，越在接近根接点的位置运用约束条件剪枝效果就越好。如何在搜索中最大化的运用题目的约束条件为我们提供剪枝的依据，是提高深度优先搜索效率的一个很重要的地方。而不同的搜索顺序和搜索对象就直接影响到我们对于题目约束条件的运用。下面，我们就从搜索的顺序和搜索的对象两方面来探讨一下不同的方法对程序效率的影响。（1）搜索顺序的选择：我们先来看一道比较简朴的题目： (zju1937)已知一个数列a0,a1.am其中
3、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的最小值（并不规定输出）,及这个数列的值(也许存在多个数列,只输出任一个满足条件的就可以了)。分析由于ak=ai+aj(0=i,jk),所以我们在搜索的过程中可以采用由小到大搜索数列的每一项的搜索顺序进行试算。在一般搜索的时候我们习惯于从小到大依次搜索每个数的取值，但是在这到题目中按照这样的顺序搜索编程运算其结果（效率）十分不抱负：N102030405060708090100200300400500用时0.030
4、.010.030.050.200.341.801.808.9110.1Too longToo longToo longToo long由于题目规定的是m的最小值，也就是需要我们尽快得到数n，所以每次构造的数应当是尽也许大的数，根据题目的这个特性，我们将搜索顺序改为从大到小搜索每个数，新程序的效率如下：N102030405060708090100200300400500用时0.010.010.010.010.010.010.030.010.030.030.131.481.522.88显然，后一种搜索顺序得到的程序效率大大地优于第一种搜索顺序得到的程序。当然，这道题尚有很大的优化余地，但是搜索顺序
5、这种思想在搜索的题目中是广泛运用的。也许大家会觉得这种单一的运用搜索顺序来优化程序的方法很普通，但是这种看似简朴的方法在考试中出现得也不少，例如IOI2023中的BLOCK，只要将木块从大到小通过旋转和反转后，依次放入进行搜索，对于比赛中的数据就可以得到满分。最近的一次出现是NOI2023中的智慧珠，同样的只是将珠子从大到小进行搜索，不加任何其他剪枝就可以在比赛中获得90分。可见，选择合适的搜索顺序对于提高程序的效率是编程设计最有效的技巧之一，运用良好的搜索顺序来对搜索题目进行优化是一个性价比很高的算法。（2）搜索对象的选择：让我们再来看看下面一道题：(USACOweight)已知原数列a1，
6、a2an中前1项，前2项，前3项前n项的和,以及后1项,后2项,后3项后n项的和，但是所有的数据都已经被打乱了顺序，还知道数列中的数存在集合中，求原数列。当存在多组也许数列的时候求左边的数最小的数列。其中n=1000,S1.500例如，假如原数列为1 1 5 2 5，S=1，2，4，5那么知道的值就是 (1 2 7 9 14 5 7 12 13 14)1 = 1 5 = 52 = 1+1 7 = 2+57 = 1+1+5 12 = 5+2+59 = 1+1+5+2 13 = 1+5+2+514 = 1+1+5+2+5 14 = 1+1+5+2+5分析由于题目中的1.500，最坏的情况下每个数可
7、以取到的值有500种，从数学方面很难找到有较好方法予以解决，而采用搜索方法却是一种很好的解决办法，根据数列从左往右依次搜索原数列每个数也许的值，然后与所知道的值进行比较。这样，我们得到了一个最简朴的搜索方法A。但是搜索方法A的这个算法最坏的情况下扩展的节点为5001000，运算速度太慢了。在这个算法中，我们对数列中的每个数分别进行了500次搜索，由此导致了搜索量如此之大。如何有效的减少搜索量是提高本题算法效率的关键。而前面提到的运用搜索顺序的方法在本题中由于规定了左边的数最小而无法运用。让我们换个角度对这个问题进行思考：搜索方法B：回过头来看看题目提供应我们的约束条件，我们用Si表达前I项的和
8、，用Ti表达后I项的和。根据题目，我们得到的数据应当是数列中的S1,S2,S3Sn，以及T1,T2,T3Tn。其中的任意Si+1-Si 和Ti+1-Ti都属于集合。另一个比较容易发现的约束条件是对于任意的I，有Sn=Tn=Si+Tn-I。同样的，在搜索的过程中最大化这些约束条件是提高程序效率的关键。那么当我们任意从已知的数据中取出两个数的时候，只会出现两种情况：1、两个数同属于Si,或者Ti2、两数分别属于Ti和Si。当两数同属于Si或者Ti时，两个数之差，就是图中Sj-Si那一段，而当j=I+1时，Sj-Si必然属于题目给出的集合。由此，当每次得到一个数Si或者Ti时，假如我们已知Si-1或
9、者Ti-1，便可以判断出此时的Si或者Ti是否合法。所以我们在搜索中尽也许运用Si-1和Ti-1推得Si和Ti的也许，便能尽也许运用题目的约束条件。由于题目的约束条件集中在Si和Ti中，我们改变搜索的对象，不再搜索原数列中每个数的值，而是搜索给出的数中出现在Si或者Ti中的位置。又由于约束条件中得出的Si+1与Si的约束关系，提醒我们在搜索中按照Si中i递增或者递减的顺序进行搜索。例如，对于数据组：1 1 5 2 5，由它得到的值为1 2 7 9 14 5 7 12 13 14排序后为：1 2 5 7 7 9 12 13 14 14由于最大的两个数为所有数的和，在搜索中不用考虑它们，去掉14：
10、 1 2 5 7 7 9 12 13观测发现，数列中的最小数1，只也许出现在所求数列的头部或者尾部。再假设1的位置已经得到了，去掉它以后，我们再观测剩下的数中最小的数2，显然也只也许在当前状态的头部或者尾部加上一个数得到2。这样，每搜索一个数，都只会将它放在头部和尾部，也就是放入Si中或者Ti中。推而广之，我们由小到大对排序的数进行搜索，判断每个数是出现在原数列头部还是尾部。此时我们由原数列的两头向中间搜索，而不是先前的从一头搜向另一头。由之前的分析已经知道，每个数只也许属于Si和Ti中。当我们已经搜索出原数列的S1,S2Si和T1,T2Tj，此时对于正在搜索的数K,只也许有两种存在的也许：S
11、i+1和Tj+1，分别依次搜索这两个也许，即判断K-Si和K-Tj是否属于已知集合。并且在每搜索出一个数的时候，我们将排序后的数列中Sn-k去掉。这样，当K-Si(Ti)不属于集合或者Sn-k不存在与排序后的数列时，就回溯。这样得到的算法在最坏情况下扩展的节点为21000(实际中远远小于这个数)，并且由于在搜索过程中充足运用了题目约束条件，其程序运营结果如下：在这道题目中，原始的搜索方法搜索量巨大，我们通过度析，选择适当的搜索对象，在搜索量减少的同时充足运用了题目的约束条件，成为了程序的一个有利的剪枝，使题目得到较好的解决。二、广度优先搜索的优化技巧相对于深度优先搜索的此外一类题目给出起始和目
12、的状态，以及状态转移的规则，规定找到一条到达目的状态的的途径或者方法。这类问题我们叫它途径寻找问题（例如走迷宫问题）。解决这类问题最有效的手段是选取合适的构造Hash表的方法。Hash表的一般构造方法有：状态压缩-运用2进制来记录状态。直接取余法-选取一个素数M作为除数。平方取中法-计算关键值平方，再取中间r位形成一个大小为2r的表。折叠法-把所有字符的ASCII码加起来。途径寻找问题中，经常会碰到走回头路的问题，所以在搜索的过程中都必须做一件事，就是判重。判重是决定程序效率的关键，而如何构造一个优秀的Hash表决定着这一切。一个好的Hash函数可以很大限度上提高程序的整体时间效率和空间效率。
13、(zju1301)：黑先生新买了一栋别墅，可是里面的电灯线路的连接是很混乱的(每个房间的开关也许控制其他房间,房间数=10)，有一天晚上他回家时发现所有的灯（除了他出发的房间）都是关闭的，而他想回卧室去休息。可是很不幸，他十分怕黑，因此他不会走入任何关着灯的房间，于是请你帮他找出一条路使他既能回到卧室又能关闭除卧室以外的所有灯。假如同时有好几条路线的话，请输出最短的路线。分析这是一道比较简朴的搜索题目，题目规定是一条途径，所以我们用广度优先搜索来解决。广度优先搜索不能避免的是反复状态，而用循环判断反复是得不偿失的，在状态多的情况下，循环法甚至比深度优先搜索的效率更低，并且低得多。而题目的难点在
14、于Hash表的构造，通过度析发现，对于状态有影响的便是房间内电灯的开关与否，尚有当时所在的房间。由于电灯只有开和关两种情况，我们考虑用进制来储存状态，也就是大家熟悉的状态压缩。将每个房间中电灯的状态用0和1来表达，然后将10个房间的状态排列起来就成了这样的形式。然后将他转换成10进制()2=(549)10，这样一来就可认为唯一的表达出一个电灯开关的状态,再用一个数记录下黑先生当时所在的房间，就成功地构造出了所需的Hash表。总共的状态数为210*10=10240。同时，在搜索中可以用位运算来判断某个房间的状态，使得Hash表的填充和查找变得简朴。例如，假设当前状态为K，现在要判断第I个房间的状
15、态。只需(2i-1 and K)是否为0就行了。这样一来，这道题就已经解决了。(pku1729)在一个N*N(N=30)的地图上，有A和B两个人，地图上的一些地方为空地，一些地方有障碍不能通过。在每一个时刻A和B必须向四个方向移动 (N,E,W,S)，并且AB两人彼此特别讨厌对方，他们希望在移动的时候尽也许的离对方远，现在知道两个人分别的起点和终点。求出一条使AB到达终点的途径，并且在途中AB间最近的距离最远，在此基础上使AB尽快到达终点。如图为N=10时的一种情况。分析：本题是求途径的一道题，所以是一道很明显的广度优先搜索题目，题目的条件很多：一方面是要AB都到达终点，然后是要途径中AB离得尽也许的远，同时AB
