2023年算法合集之《信息学竞赛中搜索问题的常见优化技巧》.doc

2023年全国信息学冬令营讲座 信息学竞赛中搜索问题的常见优化技巧 重庆一中 黄晓愉 【】结合例题分析归纳了信息学竞赛中解决搜索问题所常用的思考方法与解题方法，从深度优先搜索和广度优先搜索两个方面探讨了提高程序效率的适用技巧。 【关键词】１信息学；２搜索顺序；３搜索对象；４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的最小值〔并不要求输出〕,及这个数列的值(可能存在多个数列,只输出任一个满足条件的就可以了)。 分析　由于ak=ai+aj(0<=i,j<k),所以我们在搜索的过程中可以采用由小到大搜索数列的每一项的搜索顺序进行试算。在一般搜索的时候我们习惯于从小到大依次搜索每个数的取值，但是在这到题目中按照这样的顺序搜索编程运算其结果〔效率〕十分不理想： N 10 20 30 40 50 60 70 80 90 100 200 300 400 500 用时 0.03 0.01 0.03 0.05 0.20 0.34 1.80 1.80 8.91 10.1 Too long Too long Too long Too long 由于题目要求的是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 　　显然，后一种搜索顺序得到的程序效率大大地优于第一种搜索顺序得到的程序。 当然，这道题还有很大的优化余地，但是搜索顺序这种思想在搜索的题目中是广泛运用的。也许大家会觉得这种单一的运用搜索顺序来优化程序的方法很普通，但是这种看似简单的方法在考试中出现得也不少，例如IOI2023中的BLOCK，只要将木块从大到小经过旋转和反转后，依次放入进行搜索，对于比赛中的数据就可以得到总分值。最近的一次出现是NOI2023中的智慧珠，同样的只是将珠子从大到小进行搜索，不加任何其他剪枝就可以在比赛中获得90分。 可见，选择适宜的搜索顺序对于提高程序的效率是编程设计最有效的技巧之一，运用良好的搜索顺序来对搜索题目进行优化是一个性价比很高的算法。 〔2〕搜索对象的选择： 让我们再来看看下面一道题：(USACO－weight) 原数列a1，a2……an中前1项，前2项，前3项……前n项的和,以及后1项,后2项,后3项……后n项的和，但是所有的数据都已经被打乱了顺序，还知道数列中的数存在集合Ｓ中，求原数列。当存在多组可能数列的时候求左边的数最小的数列。 其中n<=1000,S∈{1..500} 例如，假设原数列为1 1 5 2 5，S={1，2，4，5}那么知道的值就是 (1 2 7 9 14 5 7 12 13 14) 1 = 1 5 = 5 2 = 1+1 7 = 2+5 7 = 1+1+5 12 = 5+2+5 9 = 1+1+5+2 13 = 1+5+2+5 14 = 1+1+5+2+5 14 = 1+1+5+2+5 分析　因为题目中的Ｓ∈{1..500}，最坏的情况下每个数可以取到的值有500种，从数学方面很难找到有较好方法予以解决，而采用搜索方法却是一种很好的解决方法，根据数列从左往右依次搜索原数列每个数可能的值，然后与所知道的值进行比拟。这样，我们得到了一个最简单的搜索方法A。 但是搜索方法A的这个算法最坏的情况下扩展的节点为5001000，运算速度太慢了。 在这个算法中，我们对数列中的每个数分别进行了500次搜索，由此导致了搜索量如此之大。如何有效的减少搜索量是提高此题算法效率的关键。而前面提到的运用搜索顺序的方法在此题中由于规定了左边的数最小而无法运用。让我们换个角度对这个问题进行思考： 搜索方法B：回过头来看看题目提供应我们的约束条件，我们用Si表示前I项的和，用Ti表示后I项的和。 根据题目，我们得到的数据应该是数列中的S1,S2,S3……Sn，以及T1,T2,T3……Tn。其中的任意Si+1-Si 和Ti+1-Ti都属于集合Ｓ。另一个比拟容易发现的约束条件是对于任意的I，有Sn=Tn=Si+Tn-I。同样的，在搜索的过程中最大化这些约束条件是提高程序效率的关键。 那么当我们任意从的数据中取出两个数的时候，只会出现两种情况： 1、两个数同属于Si,或者Ti 2、两数分别属于Ti和Si。 当两数同属于Si或者Ti时，两个数之差，就是图中Sj-Si那一段，而当j=I+1时，Sj-Si必然属于题目给出的集合Ｓ。由此，当每次得到一个数Si或者Ti时，如果我们Si-1或者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： 1 2 5 7 7 9 12 13 观察发现，数列中的最小数1，只可能出现在所求数列的头部或者尾部。再假设1的位置已经得到了，去掉它以后，我们再观察剩下的数中最小的数2，显然也只可能在当前状态的头部或者尾部加上一个数得到2。这样，每搜索一个数，都只会将它放在头部和尾部，也就是放入Si中或者Ti中。 推而广之，我们由小到大对排序的数进行搜索，判断每个数是出现在原数列头部还是尾部。此时我们由原数列的两头向中间搜索，而不是先前的从一头搜向另一头。由之前的分析已经知道，每个数只可能属于Si和Ti中。当我们已经搜索出原数列的S1,S2…Si和T1,T2…Tj，此时对于正在搜索的数K,只可能有两种存在的可能：Si+1和Tj+1，分别依次搜索这两个可能，即判断K-Si和K-Tj是否属于集合Ｓ。并且在每搜索出一个数Ｋ的时候，我们将排序后的数列中Sn-k去掉。这样，当K-Si(Ti)不属于集合Ｓ或者Sn-k不存在与排序后的数列时，就回溯。 这样得到的算法在最坏情况下扩展的节点为21000(实际中远远小于这个数)，并且由于在搜索过程中充分利用了题目约束条件，其程序运行结果如下： 在这道题目中，原始的搜索方法搜索量巨大，我们通过分析，选择适当的搜索对象，在搜索量减少的同时充分利用了题目的约束条件，成为了程序的一个有利的剪枝，使题目得到较好的解决。 二、广度优先搜索的优化技巧 相对于深度优先搜索的另外一类题目——给出起始和目标状态，以及状态转移的规那么，要求找到一条到达目标状态的的路径或者方法。这类问题我们叫它路径寻找问题〔例如走迷宫问题〕。解决这类问题最有效的手段是选取适宜的构造Hash表的方法。 Hash表的一般构造方法有： 状态压缩-------运用2进制来记录状态。 直接取余法-----选取一个素数M作为除数。 平方取中法-----计算关键值平方，再取中间r位形成一个大小为2r的表。 折叠法---------把所有字符的ASCII码加起来。 路径寻找问题中，经常会遇到走回头路的问题，所以在搜索的过程中都必须做一件事，就是判重。判重是决定程序效率的关键，而如何构造一个优秀的Hash表决定着这一切。一个好的Hash函数可以很大程度上提高程序的整体时间效率和空间效率。 (zju1301)： 黑先生新买了一栋别墅，可是里面的电灯线路的连接是很混乱的(每个房间的开关可能控制其他房间,房间数<=10)，有一天晚上他回家时发现所有的灯〔除了他出发的房间〕都是关闭的，而他想回卧室去休息。可是很不幸，他十分怕黑，因此他不会走入任何关着灯的房间，于是请你帮他找出一条路使他既能回到卧室又能关闭除卧室以外的所有灯。如果同时有好几条路线的话，请输出最短的路线。 分析　这是一道比拟简单的搜索题目，题目要求是一条路径，所以我们用广度优先搜索来解决。广度优先搜索不能防止的是重复状态，而用循环判断重复是得不偿失的，在状态多的情况下，循环法甚至比深度优先搜索的效率更低，而且低得多。而题目的难点在于Hash表的构造，经过分析发现，对于状态有影响的便是房间内电灯的开关与否，还有当时所在的房间。由于电灯只有开和关两种情况，我们考虑用２进制来储存状态，也就是大家熟悉的状态压缩。 将每个房间中电灯的状态用0和1来表示，然后将10个房间的状态排列起来就成了1000100101这样的形式。然后将他转换成10进制(1000100101)2=(549)10，这样一来就可以为唯一的表示出一个电灯开关的状态,再用一个数记录下黑先生当时所在的房间，就成功地构造出了所需的Hash表。总共的状态数为210x10=10240。 同时，在搜索中可以用位运算来判断某个房间的状态，使得Hash表的填充和查找变得简单。例如，假设当前状态为K，现在要判断第I个房间的状态。只需(2i-1 and K)是否为0就行了。这样一来，这道题就已经解决了。 (pku1729) 在一个NxN(N<=30)的地图上，有A和B两个人，地图上的一些地方为空地，一些地方有障碍不能通过。在每一个时刻A和B必须向四个方向移动 (‘N’,’E’,’W’,’S’)，并且AB两人彼此特别讨厌对方，他们希望在移动的时候尽可能的离对方远，现在知道两个人分别的起点和终点。求出一条使AB到达终点的路径，并且在途中AB间最近的距离最远，在此根底上使AB尽快到达终点。如图为N=10时的一种情况。 分析：此题是求路径的一道题，所以是一道很明显的广度优先搜索题目，题目的条件很多：首先是要AB都