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

深度优先搜索的优化技巧
在深度优先搜索中如何运用题目中的约束条件为我们提供剪枝是影响程序效率的关键。而搜索的顺序和搜索的对象对于这一点是十分重要的。
黄晓愉《深度优先搜索问题的优化技巧》
2021/1/16
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的最小值
黄晓愉《深度优先搜索问题的优化技巧》
2021/1/16
2
简单的分析
依次搜索是很容易想到的方法，而对于每个数的取值，我们显然可以采用从小到大搜索和从大到小搜索两种搜索方法。
由于题目要求的是m的最小值，也就是需要我们尽快构造出n，所以每次构造的数应当是尽可能大的数 。
黄晓愉《深度优先搜索问题的优化技巧》
2021/1/16
3
不同搜索顺序效率比较
两种搜索顺序比较：
N
时间/s
显然，不同的顺序导致了程序效率的不同
1、从小到大搜索每个数值
2、从大到小搜索每个数值
黄晓愉《深度优先搜索问题的优化技巧》
2021/1/16
4
以往比赛中的情况
IOI2000中的BLOCK
NOI2005中的智慧珠
将木块从大到小经过旋转和反转后，依次放入进行搜索
满分！！
将珠子从大到小进行搜索，不加任何其他剪枝
90分！！
黄晓愉《深度优先搜索问题的优化技巧》
2021/1/16
5
搜索对象的选择
(USACO－weight)
已知原数列a1，a2……an中前1项,前2项,前3项……前n项的和,以及后1项,后2项,后3项……后n项的和,但是所有的数据都已经被打乱了顺序,还知道数列中的数存在集合Ｓ中，求原数列。当存在多组可能数列的时候求左边的数最小的数列。
其中n<=1000,S∈{1..500}
黄晓愉《深度优先搜索问题的优化技巧》
2021/1/16
6
一个例子
假如原数列为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)
黄晓愉《深度优先搜索问题的优化技巧》
2021/1/16
7
一般方法
从左往右依次搜索原数列每个数可能的值，然后与所知道的值进行比较。
如何改进？
太慢了
但是这个算法最坏的情况下扩展的节点为5001000，这个算法
黄晓愉《深度优先搜索问题的优化技巧》
2021/1/16
8
从已知入手分析
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
黄晓愉《深度优先搜索问题的优化技巧》
2021/1/16
9
分析
在集合A和集合B中：
{S0<S1<S2<……<Sn}
{T0<T1<T2<……<Tn}
s0
s1
s2
s3
s4
t4
t3
t2
t1
t0
X1
X2
X3
X5
X6
X7
X8
X4
Xi∈S
Si-Si-1
Ti-Ti-1
猜想？
在搜索中从小到大搜索每个Si和Ti的位置。
黄晓愉《深度优先搜索问题的优化技巧》
2021/1/16
10