黄晓愉《深度优先搜索问题的优化技巧》

深度优先搜索问题的优化技巧重庆一中黄晓愉深度优先搜索的优化技巧在深度优先搜索中如何运用题目中的约束条件为我们提供剪枝是影响程序效率的关键。而搜索的顺序和搜索的对象对于这一点是十分重要的。搜索顺序的选择我们先来看一道比较简单的题目：(zju1937)已知一个数列a0,a1......am其中a0=1am=na0a1a2...am-1am对于每个k(1=k=m),ak=ai+aj(0=i,j=k-1)，这里i与j可以相等。现给定n的值，要求m的最小值简单的分析•依次搜索是很容易想到的方法，而对于每个数的取值，我们显然可以采用从小到大搜索和从大到小搜索两种搜索方法。由于题目要求的是m的最小值，也就是需要我们尽快构造出n，所以每次构造的数应当是尽可能大的数。不同搜索顺序效率比较两种搜索顺序比较：00.20.40.60.811.21.41.61.8210305060708012N时间/s显然，不同的顺序导致了程序效率的不同1、从小到大搜索每个数值2、从大到小搜索每个数值以往比赛中的情况•IOI2000中的BLOCK•NOI2005中的智慧珠将木块从大到小经过旋转和反转后，依次放入进行搜索满分！！将珠子从大到小进行搜索，不加任何其他剪枝90分！！搜索对象的选择•(USACO－weight)•已知原数列a1，a2……an中前1项,前2项,前3项……前n项的和,以及后1项,后2项,后3项……后n项的和,但是所有的数据都已经被打乱了顺序,还知道数列中的数存在集合Ｓ中，求原数列。当存在多组可能数列的时候求左边的数最小的数列。•其中n=1000,S∈{1..500}一个例子假如原数列为11525，S={1，2，4，5}那么知道的值就是：•1=1•2=1+1•7=1+1+5•9=1+1+5+2•14=1+1+5+2+5•5=5•7=2+5•12=5+2+5•13=1+5+2+5•14=1+1+5+2+5(12791457121314)一般方法•从左往右依次搜索原数列每个数可能的值，然后与所知道的值进行比较。如何改进？太慢了•但是这个算法最坏的情况下扩展的节点为5001000，这个算法从已知入手分析s2s0s1s3s4t4t3t2t1t0我们用Si表示前I个数的和Ti表示后I个数的和对题目中数据分类s0s1s2s3s4t4t3t2t1t0集合A集合B任意I满足：Si+Tn-I=Sn=Tn分析在集合A和集合B中：{S0S1S2……Sn}{T0T1T2……Tn}s0s1s2s3s4t4t3t2t1t0X1X2X3X5X6X7X8X4Xi∈SSi-Si-1Ti-Ti-1在搜索中从小到大搜索每个Si和Ti的位置。由具体分析对于原数列：11525，S=｛1,2,4,5｝由它得到的值为：12791457121314排序后为：125779121314141312977521原数列：11５２５这样，对于这个数据，我们已经构造出了原数列。改变搜索对象•题目的约束条件集中在Si和Ti中，我们改变搜索的对象，不再搜索原数列中每个数的值，而是搜索给出的数中出现在Si或者Ti中的位置。又由于Si+1与Si的约束关系，提示我们在搜索中按照Si中i递增或者递减的顺序进行搜索。推而广之当我们已经搜索出原数列的a1，a2……ai和an,an-1……aj，此时搜索排序后第k小的数W[k],只可能有两种存在的可能：Try(I,j)W[k]Try(I+1,j)Try(I,j-1)elseExitA[I+1]=W[k]A[j-1]=W[k]•这个算法在最坏情况下扩展的节点为21000(实际中远远小于这个数)，在搜索的同时可以利用Si+Tn-I=Sn=Tn这个约束条件进行剪枝。程序效率得到显著的提高。两个程序效率对比：00.511.522.5123456算法一算法二小结•原始的搜索方法搜索量巨大，我们通过分析，选择适当的搜索对象，在搜索量减少的同时充分利用了题目的约束条件，成为了程序的一个有利的剪枝，使题目得到较好的解决。总结我们在搜索得过程中，灵活得改变搜索的顺序和搜索的对象可以使程序效率得到很大的提升。而这需要我们在做题的过程中多思考、多分析、多总结。