信息学奥赛宽搜及应用ppt课件.ppt

,宽搜及应用,本讲要点,宽搜及其算法思想宽搜的算法实现宽搜应用初步,引 言,搜索算法是基于计算机高速运算的特点而使用的求解方法。它从问题的初始状态出发，根据约束条件，按照一定的策略，有序推进，不断深入，最终到达所有符合条件的目标状态（或无解），或者找出所有可行解中的最优解。 按照推进的控制策略，搜索一般分为宽度优先搜索和深度优先搜索。,白色表示未访问的节点，黑色表示已经访问的节点，灰色表示：DFS中为正在访问的节点，BFS中为已入队等待访问的节点。,深度优先搜索（DFS）与宽度优先搜索（BFS) 的比较,DFS,BFS,一、宽度优先搜索的算法思想,宽度优先搜索（Breadth First Search,BFS)，简称宽搜，又称为广度优先搜索。它是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中。若没有，再用产生式规则将所有第一层结点逐一拓展，得到第二层结点，并逐一检查第二层结点是否包含目标结点。若没有，再用产生式规则拓展第二层结点。如此依次拓展，检查下去，直到发现目标结点为止。如果拓展完所有结点，都没有发现目标结点，则问题无解。对于同一层结点来说，它们对于问题的解的价值是相同的，所以第一个找到的目标结点一定是应用产生式规则最少的，因此，宽搜适合求最少步骤或最短解序列这类最优解问题。,一、宽度优先搜索的算法思想,a,b,c,d,e,h,f,g,第0层,第1层,第2层,第3层,逐层遍历,二、宽度优先搜索的算法分析,BFS问题解决的关键状态表示：状态一般是指现场信息的描述，通常用T表示。一般用T0表示初始状态，Tn表示目标状态。状态转移：根据产生式规则和约束条件控制从当前状态转移到下一个状态。状态判重：大多数情况下，出现重复状态会造成死循环或空间的浪费。,现在在哪儿？,下一步去哪儿？,去过的就别再去了！,三、宽度优先搜索的算法实现,为保证“先生成的结点先扩展”，宽搜需用到符合“先进先出”特点的 这种重要的数据结构。,队列,队列的概念,队列：限定仅在一端进行插入，而在另一端进行删除操作的线性表。 允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。,队列(Queues)是生活中“排队” 的抽象。,三、宽度优先搜索的算法实现,队列(Queue)允许用户从表的一端(队尾)入队，从表的另一端(队头)出队。因此，队列也被称作先进先出线性表(FIFO-First In First Out)。,三、宽度优先搜索的算法实现,队列实现：数组模拟、STL（queue）用数组模拟队列 头指针front、尾指针rear 入队与出队 队空,三、宽度优先搜索的算法实现,const int MAXN = 1010; /队列的容量上限 int q MAXN; /队列的元素类型 int front, rear; /头指针、尾指针,队列定义（数组）,三、宽度优先搜索的算法实现,队列初始化，初始状态入队,front = 0; rear = 1; q1 = 1; /qrear=1;,1,1,约定：从1号结点开始存放队列元素,三、宽度优先搜索的算法实现,取队首元素，准备扩展,front+; x = qfront;,1,1,三、宽度优先搜索的算法实现,扩展队首结点，新状态入队,rear+; qrear = x ;,1,2,3,1,2,3,三、宽度优先搜索的算法实现,队首结点扩展完毕，出队,front+;x=qfront;指针后移一位，指向待扩展节点。,1,2,3,1,2,3,三、宽度优先搜索的算法实现,判断队列是否为空,队列不空：front rear,1,2,3,队列空： front = rear,三、宽度优先搜索的算法实现,队列基本操作,const int MAXN = 101;int qMAXN;int front, rear;int main() front = 0; rear = 1; q1 = 1; rear+; qrear = 2; rear+; qrear = 3;,while(front rear) /队列非空 front+; /队首出队 int x = qfront; cout x ; return 0; ,1,2,3,三、宽度优先搜索的算法实现,BFS算法模板（数组模拟）,front 0; rear 1; 初始状态入队; while(front rear) /当队列不为空 取队首元素进行扩展; for(对所有可能的拓展状态)if(新状态合法) 入队;if(当前状态是目标状态) 处理(输出解或比较解的优劣); ,1.将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；,用循环队列节约存储空间,2.将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就翻转为。在结构上采用这种技巧来存储的队列称为循环队列。,STL中队列queue的常用函数介绍,q.pop() 删除queue的队首元素q.front() 返回队列的队首元素，但不删除该元素q.back() 返回队列的队尾元素，但不删除该元素q.push(tmp) 将元素tmp插入到队列的队尾q.size() 返回队列中元素的个数q.empty() 当队列为空时返回true，否则返回falsewhile(!q.empty() q.pop(); 清空队列,三、宽度优先搜索的算法实现,队列queue的定义和使用,queue q;int main() for(int i=0;i6;i+) q.push(i); /入队列 q.push(20); coutq.size()endl; /队列元素个数 while(!q.empty() /队列不空时循环 coutq.front() ; /输出队首元素 q.pop(); /删除队首元素 return 0;,三、宽度优先搜索的算法实现,三、宽度优先搜索的算法实现,BFS算法模板（queue）,queue q; /定义一个名为q的队列q.push(初始状态); while(!q.empty() /当队列不为空 取队首元素进行扩展; for(对所有可能的拓展状态)if(新状态合法) q.push(新状态);if(当前状态是目标状态) 处理(输出解或比较解的优劣); q.pop(); /出队,四、宽度优先搜索的算法应用（入门）,求最优解问题 求连通块问题,四、宽度优先搜索的算法应用,第一类应用：求最优解问题,四、宽度优先搜索的算法应用,例1 抓住那头牛 农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0=N=100000)，牛位于点K(0=K=100000)。 农夫有两种移动方式： 1、从X移动到X-1或X+1，每次移动花费一分钟 2、从X移动到2*X，每次移动花费一分钟 假设牛没有意识到农夫的行动，站在原地不动。问：农夫最少需要花多少时间才能抓住那头牛？,四、宽度优先搜索的算法应用,例1 抓住那头牛【样例输入】 3 5 农夫起始位置 牛起始位置【样例输出】 2 农夫抓到牛所要花费的最小分钟数,四、宽度优先搜索的算法应用,问题分析-抓住那头牛,初始状态 N,目标状态 K,状态转移,规则1：X X - 1,规则2： X X + 1,规则3： X 2 * X,约束条件： 0 = X =100000,状态表示,位置,四、宽度优先搜索的算法应用,问题分析-抓住那头牛,3,2,4,6,当前位置,最少时间,1,5,2,1,4,1,6,1,1,2,5,2,找到目标状态,四、宽度优先搜索的算法应用,【思考】为什么BFS找到的第一个目标结点一定是最优解？,在搜索的过程中，BFS对于结点总是沿着深度的断层逐层扩展的，即要扩展第n+1层结点，必须先将第n层结点全部扩展完毕。且对于同一层结点而言，它们对于问题解的价值是相同的。 所以BFS一定能保证：第一个找到的目标结点，一定是应用产生式规则最少的。因此，宽度优先搜索较适合求最优解的问题。,四、宽度优先搜索的算法应用,例2 小明抄答案 有一次上数学课，老师布置了课堂作业。小明在写作业时睡着了。他梦见自己站在一个迷宫里，一个圣人给了他迷宫的地图，说：“你现在位于迷宫的左上角，迷宫的右下角有数学作业的答案。你只能上下左右走，但你放心，我没有耍你，迷宫是一定能走得通的。”小明很想拿到答案，但他太笨了，所以找来了会编程的你，叫你帮他找到答案。他需要知道找到答案的最少步数。,四、宽度优先搜索的算法应用,例2 小明抄答案 【输入】 第一行是两个整数，和，代表迷宫的行数和列数（2=R,C =100）。接下来的行，每行个字符，代表整个迷宫。空地格子用.表示，有障碍物的格子用#表示。迷宫左上角和右下角都是.。【输出】 一行包含一个整数，输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。注：计算步数要包括起点和终点。,四、宽度优先搜索的算法应用,问题分析-小明抄答案 状态表示： 初始状态： 目标状态：,(1,1),(r,c),1,1,Start,End,r,c,当前所在迷宫的位置（行号, 列号）,左上角,右下角,四、宽度优先搜索的算法应用,问题分析-小明抄答案 状态转移： 转移规则： 约束条件：,1 = x = r 1 = y = c, (x,y+1), (x+1,y), (x,y-1), (x-1,y),四、宽度优先搜索的算法应用,问题分析-小明抄答案,行号,最少步数,列号,(1,1),(1,2),(2,2),(2,3),(3,2),(4,2),(4,3),(4,4),122,223,234,324,425,436,447,找到目标状态,四、宽度优先搜索的算法应用,问题分析-小明抄答案思考：如果要输出其中一条最短路径，怎么办？,行号,最少步数,列号,前驱节点,(1,1) (1,2)(2,2)(3,2)(4,2)(4,3)(4,4),四、宽度优先搜索的算法应用,第二类应用：求连通块问题,四、宽度优先搜索的算法应用,例3 宝岛探险【题目描述】 某海域航拍图由一个R行C列的数字矩阵组成，图中数字表示海拔，0表示海洋，19表示陆地。求该海域共有多少岛屿，最大的岛屿面积多大（即包含多少格子）。我们把上下左右相邻接的陆地视为同一岛屿。,四、宽度优先搜索的算法应用,例3 宝岛探险【样例输入】 【样例输出】 4 10 4 11 0234500067 1034560500 2045600671 0000000089【数据范围】 1= R，C = 20,四、宽度优先搜索的算法应用,问题分析-宝岛探险,求连通块问题的基本思路是：从某关键点（不是海洋的点）开始BFS，形成的连通区域即为一连通块。,四、宽度优先搜索的算法应用,问题分析-宝岛探险,每找到一个岛屿，个数就+1,四、宽度优先搜索的算法应用,问题分析-宝岛探险,13,14,23,15,24,33,25,34,26,35,rear即为当前岛屿大小,i,j,for(int i=1;iimax)imax=tot; ,void bfs() while(!q.empty() for(int i=0;i=1 ,输出什么?,例4 分油问题 有三个容量分别是10升、7升、3升的桶，开始时只有10升的桶都是满的，而7升和3升桶是空的。我们可以把油从一个桶倒到另一个桶中，每一次的倒油过程都以原始桶空或目标桶满为结束，且倒油过程中不会产生任何的浪费。那么最少需要几步可在10升桶和7升桶中各装入5升的油？,五、课后讨论,问题分析-倒油问题状态的表示 初始状态： 目标状态：,用一个三元组T（x10,x7,x3）表示状态，其中x10，x7，x3分别表示三个瓶子中的当前油量。,（10,0,0）,（5,5,0）,五、课后讨论,问题分析-倒油问题状态的转移（规则） 三个瓶子（x10,x7,x3）有6种倒油规则：,10升瓶7升瓶,10升瓶3升瓶,7升瓶10升瓶,7升瓶3升瓶,3升瓶10升瓶,3升瓶7升瓶,五、课后讨论,问题分析-倒油问题状态的转移（约束条件）,当 且 时：如果 ,那么 倒满7升瓶 新状态T( )入队否则 倒空10升瓶 新状态T ( ) 入队,10升瓶7升瓶,10升瓶有油,7升瓶未满,10升瓶油+7升瓶油 = 7,10升瓶油+7升瓶油-7,7,不变,0,10升瓶油+7升瓶油 ,不变,五、课后讨论,问题分析-倒油问题状态的转移（约束条件）,当 且 时：如果 ,那么 倒满7升瓶 新状态T( )入队否则 倒空10升瓶 新状态T ( )入队,10升瓶7升瓶,x10 0,x7 7,x10 + x7 = 7,x10+x7-7,7,x3,0,x10+x7,x3,五、课后讨论,10,0,0,9,0,1,2,7,1,2,5,3,5,5,0,五、课后讨论,小 结 - 宽度优先搜索的特点,一般来讲，宽度优先搜索需要储存所产生的所有节点。因此，占用的空间比较多，必须考虑溢出和节约内存的问题。必须注意判重，宽搜会产生重复节点，因此一定要把重复节点删除。无回溯的操作。因此，在搜索速度上比较快。若问题的解要一条路径，则需对每个节点都要保存其父节点，以便输出那条路径。,小 结,建议一、队列元素使用结构体表示；建议二、可直接利用STL中的queue方便完成,Thank you!,