文档介绍：该【黄晓愉《深度优先搜索问题的优化技巧》公开课一等奖课件赛课获奖课件 】是由【业精于勤】上传分享，文档一共【18】页，该文档可以免费在线阅读，需要了解更多关于【黄晓愉《深度优先搜索问题的优化技巧》公开课一等奖课件赛课获奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。深度优先搜索问题的优化技巧
重庆一中 黄晓愉
深度优先搜索的优化技巧
在深度优先搜索中怎样运用题目中的约束条件为我们提供剪枝是影响程序效率的关键。而搜索的次序和搜索的对象对于这一点是十分重要的。
搜索次序的选择
我们先来看一道比较简单的题目：
(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的最小值
简单的分析
依次搜索是很容易想到的措施，而对于每个数的取值，我们显然可以采用从小到大搜索和从大到小搜索两种搜索措施。
由于题目规定的是m的最小值，也就是需要我们尽快构造出n，因此每次构造的数应当是尽量大的数 。
不一样搜索次序效率比较
两种搜索次序比较：
N
时间/s
显然，不一样的次序导致了程序效率的不一样
1、从小到大搜索每个数值
2、从大到小搜索每个数值
以往比赛中的状况
IOI中的BLOCK
NOI中的智慧珠
将木块从大到小通过旋转和反转后，依次放入进行搜索
满分！！
将珠子从大到小进行搜索，不加任何其他剪枝
90分！！
搜索对象的选择
(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 = 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
(1 2 7 9 14 5 7 12 13 14)
一般措施
从左往右依次搜索原数列每个数也许的值，然后与所懂得的值进行比较。
怎样改善？
太慢了
不过这个算法最坏的状况下扩展的节点为5001000，这个算法
从已知入手分析
s2
s0
s1
s3
s4
t4
t3
t2
t1
t0
我们用
Si表达前I个数的和
Ti表达后I个数的和
对题目中数据分类
s0
s1
s2
s3
s4
t4
t3
t2
t1
t0
集合A
集合B
任意I满足：Si+Tn-I=Sn=Tn