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

信息学竞赛中搜索问题常用优化技巧
重庆一中 黄晓愉

【摘要】结合例题分析归纳了信息学竞赛中处理搜索问题所常用思索措施与解题措施，从深度优先搜索和广度优先搜索两个方面探讨了提高程序效率合用技巧。

【关键词】１信息学；２搜索次序；３搜索对象；４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
　　显然，后一种搜索次序得到程序效率大大地优于第一种搜索次序得到程序。
当然，这道题尚有很大优化余地，不过搜索次序这种思想在搜索题目中是广泛运用。也许人们会觉得这种单一运用搜索次序来优化程序措施很一般，不过这种看似简朴措施在考试中出现得也不少，例如IOI中BLOCK，只要将木块从大到小通过旋转和反转后，依次放入进行搜索，对于比赛中数据就可以得到满分。近来一次出现是NOI中智慧珠，同样只是将珠子从大到小进行搜索，不加任何其她剪枝就可以在比赛中获得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个房间状态排列起来就成了这样形式。然后将她转换成10进制()2=(549)10，这样一来就可觉得唯一体现出一种电灯开关状态,再用一种数记录下黑先生当时所在房间，就成功地构造出了所需Hash表。总共状态数为210*10=10240。
同步，在搜索中可以用位运算来判断某个房间状态，使得Hash表填充和查找变得简朴。例如，假设目前状态为K，目前要判断第I个房间状态。只需(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要尽快抵达。
咱们首先尝试用Hash表将所有信息存下，然后进行搜索，我首先想到了两种构造Hash表措施：
1、 用Hash[x1,y1,x2,y2,t]体现通过了t个时间点，A抵达坐标(x1,y1)，B抵达(x2,y2)，它们在途中近来距离。
2、 用Hash[x1,y1,x2,y2,k]当A抵达坐标(x1,y1)，B抵达坐标(x2,y2)，它们在途中近来距离为k时至少时间。
　　这两种措施构造措施共同特点是Hash表中储存了大量信息，并且在编程实现中比较困难。
由于大量条件在Hash表中堆积，咱们尝试将其中一种条件从Hash表中去掉，用其她措施来分担。
假设咱们已经懂得了两人在途中近来距离，那么剩余将会简朴许多。不过怎样才能懂得两人在途中最短距离呢？咱们想到了二分。
在两个人在地图上距离差最多只也许有304＝810000种也许，假如咱们采用２分法，最多只需要log2810000<20次，然后在用广度优先搜索来处理剩余问题，那么最坏状况下扩展节点数为20*304=1600。完全可以在规定期间内得出成果。
考虑到在AB移动过程中，同一种状态(x1,y1,x2,y2)不也许出现两次，那么可以考虑直接用Hash表将状态(x1,y1,x2,y2)状况存下，于是Hash表中应当储存下A抵达坐标(x1,y1)，B抵达坐标(x2,y2)，它们途中近来距离并且在此基本上最短时间。

小结　Hash表是非常重要广度优先搜索优化方式之一，它可以把搜索算法效率从大指数级提高到小指数级、多项式级甚至常数级。

三、深度优先搜索和广度优先搜索有力工具----剪枝
USACO-Cryptcowgraphy(解密牛语)
农民Brown和John牛们筹划协同逃出它们各自农场。它们设计了一种加密措施用来保护它们通讯不被她人懂得。
假如一头牛有信息要加密，例如"International Olympiad in Informatics"，它会随机地把C，O，W三个字母插到到信息中（其中C在O前面，O在W前面），然后它把C与O之间文字和 O与W之间文字位置换过来。这里是两个例子：
International Olympiad in Informatics->CnOIWternational Olympiad in Informatics
International Olympiad in Informatics-> International Cin　InformaticsOOlympiad W
为了使解密更复杂，牛们会在一条消息里多次采用这个加密措施（把上次加密成果再进行加密）。一天夜里，John牛们收到了一条通过多次加密信息。请你写一种程序判断它是不是这条信息通过加密（或没有加密）而得到：
Begin the Escape execution at the Break of Dawn

分析 基于密码编译规则，咱们很轻易地可以想出一种非常简朴dfs措施，当然，那是明显要超时，而分析题目咱们可以发现，题目规定是一种得到信息加密措施，也就是求一种加密途径。于是咱们不得不采用宽度优先搜索算法。
对于Hash表构造措施，可以采用ELFhash函数或者SDBMhash(参见李羽修论文)。这里跳过。
题目规定加密信息不超过75个字符，而原始信息一共有47个字符，那么按照正规方式在信息中最多也许加入9组’C’,’O’,’W’字符。假如使用原始算法进行搜索，将最多扩展(9!)3个接点，大大超过了时间容许，因此剪枝是必要行为。
题目已经将原始信息提供应了咱们，因此怎样运用好已知信息对搜索进行剪枝将直接影响程序效率。
１、密文每次加密都会加入’C’,’O’,’W’三个字母，因此输入密文长度必要是47+3n，这样可以迅速排除某些数据。
２、已知密文中每个字符个数除了’C’,’’O,’W’外必然都是固定，并且’C’,’O’,’W’三个字符个数也必然在原始信息基本上增长了(n-47)/3　(n为输入信息长度)。
３、原文中出现’C’,’O’,’W’均为小写，那么在加密后信息里面，持续’C’,’O’和’’O,’W’之间字符必然是原文序列。
４、第一种字符和加密字符(’C’)之间必要是原文，同样，最终一种字符和最终一种加密字符(’W’)之间也必要是原文。

在程序实现中，为了更快了搜索，将把字符串里面加密字符，按索引存储。这样每次扩展节点时间大大减少，最坏状况为93。否则每次扩展节点将花去(length(s)3)。
使用了这些优化后来，程序效率将大大提高。

小结　剪枝是所有搜索中必不可少一种重点，充足运用题目特性进行剪枝可以很大程度提高程序效率。

参照文献：
[1] 刘汝佳，黄亮. 《算法艺术与信息学竞赛》()
[2] AngleForYou 《搜索算法通用优化措施》
[3] USACO 《解密牛语解题汇报》