黄晓愉《深度优先搜索问题的优化技巧》省公开课金奖全国赛课一等奖微课获奖

深度优先搜索问题优化技巧

重庆一中

黄晓愉

1/18深度优先搜索优化技巧

在深度优先搜索中怎样利用题目中约束条件为我们提供剪枝是影响程序效率关键。而搜索次序和搜索对象对于这一点是十分主要。2/18搜索次序选择

我们先来看一道比较简单题目：(zju1937)已知一个数列a0,a1......am其中a0=1am=na0<a1<a2<...<am-1<am对于每个k(1<=k<=m),ak=ai+aj(0<=i,j<=k-1)，这里i与j能够相等。现给定n值，要求m最小值

3/18简单分析依次搜索是很轻易想到方法，而对于每个数取值，我们显然能够采取从小到大搜索和从大到小搜索两种搜索方法。因为题目要求是m最小值，也就是需要我们尽快结构出n，所以每次结构数应该是尽可能大数。4/18不一样搜索次序效率比较两种搜索次序比较：N时间/s显然，不一样次序造成了程序效率不一样1、从小到大搜索每个数值2、从大到小搜索每个数值5/18以往比赛中情况IOI中BLOCKNOI中智慧珠将木块从大到小经过旋转和反转后，依次放入进行搜索满分！！将珠子从大到小进行搜索，不加任何其它剪枝90分！！6/18搜索对象选择

(USACO－weight)已知原数列a1，a2……an中前1项,前2项,前3项……前n项和,以及后1项,后2项,后3项……后n项和,不过全部数据都已经被打乱了次序,还知道数列中数存在集合Ｓ中，求原数列。当存在多组可能数列时候求左边数最小数列。其中n<=1000,S∈{1..500}7/18一个例子假如原数列为11525，S={1，2，4，5}那么知道值就是：1=12=1+17=1+1+59=1+1+5+214=1+1+5+2+55=57=2+512=5+2+513=1+5+2+514=1+1+5+2+5(12791457121314)8/18普通方法从左往右依次搜索原数列每个数可能值，然后与所知道值进行比较。怎样改进？太慢了不过这个算法最坏情况下扩展节点为5001000，这个算法9/18从已知入手分析s2s0s1s3s4t4t3t2t1t0我们用Si表示前I个数和Ti表示后I个数和对题目中数据分类s0s1s2s3s4t4t3t2t1t0集合A集合B任意I满足：Si+Tn-I=Sn=Tn10/18分析在集合A和集合B中：{S0<S1<S2<……<Sn}{T0<T1<T2<……<Tn}s0s1s2s3s4t4t3t2t1t0X1X2X3X5X6X7X8X4Xi∈SSi-Si-1Ti-Ti-1猜想？在搜索中从小到大搜索每个Si和Ti位置。11/18由详细分析对于原数列：11525，S=｛1,2,4,5｝由它得到值为：12791457121314排序后为：

12577912131414

1312977521原数列：11５２５这么，对于这个数据，我们已经结构出了原数列。12/18改变搜索对象题目标约束条件集中在Si和Ti中，我们改变搜索对象，不再搜索原数列中每个数值，而是搜索给出数中出现在Si或者Ti中位置。又因为Si+1与Si约束关系，提醒我们在搜索中按照Si中i递增或者递减次序进行搜索。

13/18推而广之

当我们已经搜索出原数列a1，a2……ai和an,an-1……aj，此时搜索排序后第k小数W[k],只可能有两种存在可能：Try(I,j)W[k]W[k]－Si∈S?W[k]－Tj∈S?Try(I+1,j)Try(I,j-1)elseExitA[I+1]=W[k]A[j-1]=W[k]14/18这个算法在最坏情况下扩展节点为21000(实际中远远小于这个数)，在搜索同时能够利用Si+Tn-I=Sn=Tn这个约束条件进行剪枝。程序效率得到显著提升。两个程序效率对比：15/18小结原始搜索方法搜索量巨大，我们经过分析，选择适当搜索对象，在搜索量降低同时充分利用了题目标约束条件，成为了程序一个有利剪枝