大家一起来广搜课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2010/5/24,#,谢家晔,00948126,大家一起来广搜,从,DFS,说起,广度优先搜索与深度优先搜索在控制结构和产生系统上都很相似（控制结构,状态搜索树；产生系统,状态转移规则）。不同点在于对节点的扩展顺序不同，因而采用了不同的数据结构实现。因此，这两种算法在性能和适用范围上有较大区别。,如可行解问题用深搜来解决，而最优解问题用广搜来解决。,另外，由于深度优先搜索一般用递归实现，调用栈的层数限制也在一定程度上限制了适用的问题规模。,以下就给大家介绍一下广度优先搜索算法及其优化。,主要内容,广搜的基本概念,广搜的基本操作（队列实现）,广搜的优化,广搜的应用,搜索的基本概念,状态,对问题在某一时刻进展情况的数学描述,。我们将一个状态简化为一个节点处理。,状态转移,问题从一种状态到转移到另一种（或几种,),状态的操作,。,状态空间,问题可以处于的所有状态,。,搜索树,将初始状态作为根节点，由状态转移操作扩展出其他节点作为其子节点，并对其他节点按一定规则重复同样的操作，得到的一个树结构。,广度优先搜索的思想,刚才我们在搜索树中提到“对其他节点,按一定规则,重复同样的操作”。,在广搜中，这个规则即为按层遍历。,即：从根节点（第,0,层）开始，依次扩展完该层的所有节点，再扩展下一层的节点。,由此可知广搜可以用来解决最少步数的问题：同一层的步数都是相等的（都等于层数），而每次都是搜完较浅层的才搜较深层的，因此最先搜索到的解一定是最少步数的解。,广度优先搜索的基本操作,现在我们来看广搜与队列的关系：,由广搜扩展节点的顺序可知，应当用先进先出的队列实现。初始时队列仅包括初始节点，每次以队头节点作为父节点扩展，扩展出的子节点入队，已扩展出所有子节点的父节点出队。另外，对于已经进过队的状态，应进行标记以避免重复搜索。,伪代码如下：,Initialize(queue),while(!empty_queue),state-queue_front,push every possible state extended from current state,pop current state,Poj 2882 Food cubes,给定三维空间内若干个单位立方体的坐标，求这些立方体围成了多少个空穴。空穴指在空间的,6,个方向被包围的连续空间。坐标范围在,1100,之间。,典型的搜索题，不过用深搜的话，,1003,层调用栈是会爆的,=_=|,所以,由于数据范围不大，简单的广搜就可以过。,O(_)O,每次搜索连续空间，搜到队列为空时空穴数,+1.,此题还有一个需要处理的细节就是外围不被包围的空间是不算在空穴里的。我的处理方法是在最外围包一层立方体，最后将空穴数,-1.,Lets turn to BFS!,以下为伪代码,Input&initialize/create a wall outside the/whole space,For every(i,j),initialize mapij/record if(i,j)can be visited,ans-0,For every unvisited(i,j),BFS(i,j)/extend from(i,j)to the largest hole,ans+,ans-,Output(ans),广搜的优化,广搜的平均时间复杂度是平均搜索到的状态数的常数倍，最坏时间复杂度是所有可能搜索到的状态数的常数倍。,因此，广搜的优化方法比较有限，主要是从减少平均搜索到的状态数入手。,且优化后不能改变解的性质，仍然要得到最优解。,广搜的优化,一种效率比较高、但适用范围较窄的优化就是双向广搜，它有效地减少了平均搜索到的节点数，大大提高了广搜的效率。,双向广搜的一般方法是：分别从初始节点和目标节点开始广搜，每次检查两边的节点是否有重合，若有重合即为最优解。,可以按顺序交替扩展两个方向的队列，但在很多情况下我们也可以进行这样的优化，即每次扩展完之后总是选择节点数较少的一边进行下一次扩展，而不是机械地两边交替，这样一般能提高搜索的效率。,广搜的优化,双向广搜的伪代码如下：,Initialize(queue0),Initialize(queue1),while(!empty_queue0&!empty_queue1&solution_not_found),find the queue with the least nodes queuem,while queuem_front belongs to current layer,state-queuem_front,push every possible state extended from current state,pop queuem_front,Poj 1915 Knight moves,骑士的走法是沿某个方向走两格，再向垂直方向走一格。如图所示。,给定一个,nn,的棋盘、骑士的起点和终点，求最快几步能从起点走到终点。,(n=300),Poj 1915 Knight moves,此题我用了没有加优化的广搜,A,了,但是有群众表示纯广搜过不了,并且我的单向广搜运行时间也比较长,所以,建两个队列，分别从起点和终点开始搜索，相遇则结束搜索。,Lets turn to two-way BFS!,以下为伪代码,Input&initialize,queue0.push(src_pnt),queue1.push(dst_pnt),while(!empty_queue0&!empty_queue1&solution_not_found),Find m so that queuem has the least nodes,k-queuem_front.step,while queuem.front.step=k,extend all possible nodes from it,if an extended node has been visited in queue1-m,Solution_found,Output,广搜的一些其他应用,因为广搜通常用来找最优解，所以在很多地方都很有实际应用的价值,如：,定义曼哈顿距离：,Dist(x1,x2),(y1,y2)=|x1-x2|+|y1-y2|.,则从一个点出发广搜能得到它到所有点的曼哈顿距离。,（,Why,？）,Poj 3501 Escape From Enemy Territory,给定一个长,X,，宽,Y(1=X,Y=1000),的矩形地图，给定起点、终点坐标，以及,N,个敌方基地,(N=10000),的坐标。现在要寻找一条从起点到终点的路径，路径经过的每一点距离敌方基地的最小距离称为这条路径距离敌方的距离。其中，点与点的距离为曼哈顿距离。求与敌方相距最远的最短路径长度。,时限：,5000ms,Poj 3501 Escape From Enemy Territory,这个问题有两个限制条件，一是路径到敌方基地的最短距离要最大，二是符合条件的路径长度要最短。,很显然应该分步考虑这两个因素。,一个比较清晰的思路：,对路径到敌方基地的最短距离进行二分；,根据该距离的限制进行广搜。,Poj 3501 Escape From Enemy Territory,因此，我们需要做的就是：,预处理：计算并保存,X*Y,的矩阵中每一点到敌人的最短距离,二分路径到敌人的最短距离，并根据该距离限制进行广搜,其中，预处理，根据我们刚才的结论，可以用广搜解决。初始队列包含,N,个敌人的位置。,以下为伪代码,Input&initialize,Queue.push N enemy_base,BFS/find out the min dist from every/point on board to enemy bases,Initialize left,right,while left right,mid-(left+right)/2,BFS with limit mid/find the shortest path/with min_dist mid,if mid is feasible,renew ans,left-mid,else,right-mid,Output,