集训队讲座第一讲--搜索.ppt

ACM程序设计,杭州电子科技大学,2019/5/15,2,2011集训队讲座-第一讲,搜索入门 (Searching),2019/5/15,3,预备知识,1.什么是队列? 2.什么是树? 3.什么是图?,2019/5/15,4,队列,队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。(FIFO),2019/5/15,5,队列的实现方法,1.方法一： int(元素类型) QueueMAX_NUM; int top = 1,base = 0; 入队:Queue top + = 入队元素; 出队:int tmp = Queue base +; 2.方法二:(利用STL) #include using namespace std; queue Q; 入队:Q.push(入队元素); 出队:int tmp = Q.pop();,2019/5/15,6,树,2019/5/15,7,图,2019/5/15,8,图的表示法,2019/5/15,9,Index,BFS(宽度优先搜索) (双向广搜) DFS(深度优先搜索),2019/5/15,10,什么是搜索问题,2019/5/15,11,胜利大逃亡,2019/5/15,12,基本概念,状态 隐式图 状态空间 状态转移 解答树,(0,0,0),(1,0,0),(0,0,1),(0,1,0),(0,2,0),(0,0,2),(0,1,1),(1,0,1),(1,1,0),(2,0,0),节点:所有的状态,有向边:状态的转移 状态空间:所有状态的集合,可行解:一条从初始状态到目标状态的路径,2019/5/15,14,宽度优先搜索,BFS (breadth first search) 适用解决最优解问题 如:用时最少; 转弯次数最少; 代价最优;,2019/5/15,15,BFS,先遍历隐式图中通过一条边所能访问到的所有节点,然后访问通过两条边所能访问的所有节点,依次类推. 我们来看一个例子.,2019/5/15,16,(1,1,2),(1,2,3),(1,3,4),(3,1,4),(0,3,5),(2,3,5),(1,0,1),(2,1,3),(0,1,1),(2,0,2),(3,0,3),BFS的遍历方式,(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(0,3),(1,3),(2,3),(3,0),(3,1),(3,2),(3,3),0,1,1,2,2,3,Queue,(0,0,0),3,3,4,6,5,4,5,(3,3,6),2019/5/15,17,BFS队列的一些性质,1,2,3,有什么神奇的发现？,回忆一下几个细节,队列中的状态总是按按关键状态单调排列.,为什么?,这个性质非常重要. 这个性质保证了最先被搜索到的解一定是最优解。,2019/5/15,18,BFS的Hash的方法,你是否又曾注意到,为什么这里不得到状态(1,1,4)并使其重新入队?,剪枝!,2019/5/15,19,什么是剪枝?,即剪去解答树上已被证明不可能存在可行解或最优解的子树.,不存在解的子树,可以不进行遍历,2019/5/15,20,此题的剪枝方法,HASH（最常用） 标记已经遍历到的结点，若此后再出现该状态即可直接舍去，不对其进行入队操作。(关键:防止状态不必要的重复),2019/5/15,21,代码怎么写,关键字:队列的应用 状态的转移 Hash判重,2019/5/15,22,BFS代码框架,while(队列不为空) 弹出队列头结点 node temp = Q.pop(); 判断该状态是否为目的状态 if(temp.x = dx ,2019/5/15,23,Nightmare,Sample Input 3 3 3 2 1 1 1 1 0 1 1 3 4 8 2 1 1 0 1 1 1 0 1 0 4 1 1 0 4 1 1 0 0 0 0 0 0 1 1 1 1 4 1 1 1 3,Sample Output 4 -1 13,直接把经过的地方都hash掉行不行?,2019/5/15,24,反例,我们来看一个惊人的反例。,5 8 1 2 1 1 1 1 1 4 1 0 0 0 1 0 0 1 1 4 1 0 1 1 0 1 1 0 0 0 0 3 0 1 1 1 4 1 1 1 1 1,Hash的关键：状态的重复,增加一维记录炸弹剩余的时间 用hashxyt 记录到达(x,y)点时炸弹距离爆炸还有t秒的最优解.,状态只有位置和时间吗?,2019/5/15,25,再来理解一下状态,且看下一个有趣的问题.,2019/5/15,26,非常可乐,Sample Input 7 4 3 4 1 3 0 0 0 Sample Output NO 3,这连图都没有这也能搜索？,2019/5/15,27,状态是什么?,你能回答吗?,状态即是两个杯子和一个瓶子中各自装有的可乐体积. 有了状态如何转移呢?,有了状态有了转移(边),是否就能进行搜索了?,2019/5/15,28,还需要考虑,搜索的可行性： 可能被搜索到的状态数量:N*M*S = 1000000 如何防止相同状态不被重复搜索. 如何剪枝? 这里又是判断状态重复的Hash剪枝 怎么做? 利用hashnms = 记录(n,m,s)状态是否曾经出现过. 还有问题吗?直接开搜!,2019/5/15,29,Ocean Currents,Sample Input 5 5 04125 03355 64734 72377 02062 3 4 2 4 2 4 5 1 4 5 3 3 4,Sample Output 0 2 1,思考一下你想到了什么? 刚才讲的BFS能行吗?为什么,7 0 1 |/ 6-*-2 /| 5 4 3,2019/5/15,30,队列的性质,由于各个状态并不一定按照所用递增的时间入队,队列单调的性质遭到了破坏. 严重的后果,最先得到的解不一定是最优解. 怎么办? 维护队列的单调性. 使用优先队列:priority_queue.,2019/5/15,31,优先队列,使用优先队列维护队列单调性 使并不单调入队的状态按照用时递增的顺序出队,2019/5/15,32,Ignatius and the Princess I,Sample Input 5 6 .XX.1. X.2. 2.X. .XX. XXXXX.,Sample Output It takes 13 seconds to reach the target position, let me show you the way. 1s:(0,0)-(1,0) 2s:(1,0)-(1,1) 3s:(1,1)-(2,1) 4s:(2,1)-(2,2) 5s:(2,2)-(2,3) 6s:(2,3)-(1,3) 7s:(1,3)-(1,4) 8s:FIGHT AT (1,4) 9s:FIGHT AT (1,4) 10s:(1,4)-(1,5) 11s:(1,5)-(2,5) 12s:(2,5)-(3,5) 13s:(3,5)-(4,5) FINISH,怎么还需要输出路径！？,2019/5/15,33,记录路径,记录前驱！ 记录当前状态是由哪一个状态转移而来的,2019/5/15,34,其他优先问题-逃离迷宫,Sample Input 2 5 5 .* *.*. . . * 1 1 1 1 3,Sample Output no,与刚才的BFS有什么区别,又有什么相同点?,2019/5/15,35,转弯次数优先,既然要求转弯次数最少,我们就要保证队列里的状态按转弯次数单调递增排列,这就要求各个状态按照转弯次数递增的顺序入队.即转弯0次的全部入队以后,才允许转弯1次的入队.依次类推。 具体怎么操作? 将每个状态转一次弯所能达到的所有结点入队. 这样就保证了第一次搜到的目标状态即是所用转弯次数最少的答案.,2019/5/15,36,更加强劲的DTBFS,双向广搜(Double Threshold BFS),2019/5/15,37,双向广搜,一般来说,从初始结点和目标结点开始分别作两次BFS,每次选择队列中结点少的一边进行扩展,并且检测两边是否出现了状态重合. 有兴趣的同学可以试试 Solitaire,2019/5/15,38,来看另一类搜索问题,深度优先搜索(depth first search ),2019/5/15,39,深度优先搜索,DFS (depth first search )适用的范围: 用于快速寻找可行解,但不要求解为最优. 应用不局限于搜索题.,2019/5/15,40,能走出去吗?这个,2019/5/15,41,DFS的遍历方式,每次访问到一个结点（状态）时，检查其邻接结点，若存在可访问子结点时，则递归访问该结点，若无子节点可以访问或子节点已全部被访问完毕则返回上一层。,2019/5/15,42,DFS的遍历路径,遍历完成,2019/5/15,43,补充知识,什么是递归？ 关键字：调用自身 简单的例子: 阶层的递归实现 int func(int n) if(n = 1) return 1; else return n * func(n 1); ,递归的出口,优点：编码量小 缺点：效率低,2019/5/15,44,递归过程,2019/5/15,45,连连看,Sample Input 3 4 1 2 3 4 0 0 0 0 4 3 2 1 4 1 1 3 4 1 1 2 4 1 1 3 3 2 1 2 4,Sample Output NO,2019/5/15,46,解题,怎样判断是否可以消去？ 本质：从一个点出发是否存在一条转弯次数小于等于两次的路径可以达到另一个点。(不要求最少转弯次数) 明显的是否存在可行解问题。,2019/5/15,47,问题:如何判断是否发生转弯?,记录当前方向,并且传入下一步子程序. void DFS(int x,int y,int num,int dir) if(num 2) return; 如果发生转弯的行走 DFS(x,y,num + 1,dir); 如果未发生转弯 DFS(x,y,num,dir); ,2019/5/15,48,暴搜能解决问题吗?,不加任何剪枝的直接暴搜. Sample跑的还是挺快的么提交一下,2019/5/15,49,剪枝!剪枝!剪枝!,剪枝的重要性可见一斑。 那么有什么地方可以让我们剪枝呢？ 看下面这张战局图。,2019/5/15,50,已经转弯一次方向完全相反。 还有必要走下去吗？,2019/5/15,51,增加剪枝方案,Void DFS(int x,int y,int num,int dir) if(num = 1） if(dir 为x增大方向 ,既然这样?那么,2019/5/15,52,这种已经转了两次的情况呢?,2019/5/15,53,再次增加剪枝方案,效果非常明显,2019/5/15,54,再次强调剪枝的重要性,来看一下DFS在另一类题里的作用.,ACMer们： 为了ACM事业，努力地剪枝吧！,2019/5/15,55,Prime Ring Problem,Sample Input 6 8 Sample Output Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2,2019/5/15,56,如何用DFS解决这个问题？,用DFS枚举所有状态，判断该状态是否可行。,2019/5/15,57,代码框架,这样就行了吗？,void DFS(int 当前数字数量) if (当前数字数量 = 要求数字） if(符合条件) 输出(); else return; else 从未用过的数字中取一个加入到当前位置(); DFS(当前数字数量 + 1); ,2019/5/15,58,复杂度分析,注意到(0 n 20) 裸的DFS最多需要枚举19!(121645100408832000)次 怎么办? 剪枝！ 剪！怎么剪？,2019/5/15,59,剪枝,若枚举的前几项已经不满足条件，在这个序列的基础上枚举的所有序列还有可能是可行的吗？ 保证