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

宽搜及应用1本讲要点•宽搜及其算法思想•宽搜的算法实现•宽搜应用初步2￿￿￿引￿言 搜索算法是基于计算机高速运算的特点而搜索算法是基于计算机高速运算的特点而使用的求解方法它从问题的初始状态出发，根据使用的求解方法它从问题的初始状态出发，根据约束条件，按照一定的策略，有序推进，不断深入，约束条件，按照一定的策略，有序推进，不断深入，最终到达所有符合条件的目标状态（或无解），或最终到达所有符合条件的目标状态（或无解），或者找出所有可行解中的最优解者找出所有可行解中的最优解 按照推进的控制策略，搜索一般分为宽度按照推进的控制策略，搜索一般分为宽度优先搜索和深度优先搜索优先搜索和深度优先搜索3 白色表示未访问的节点，黑色表示已经访问的白色表示未访问的节点，黑色表示已经访问的节点，灰色表示：节点，灰色表示：DFSDFS中为正在访问的节点，中为正在访问的节点，BFSBFS中中为已入队等待访问的节点为已入队等待访问的节点深度优先搜索（深度优先搜索（DFS）与宽度优先搜索（）与宽度优先搜索（BFS) 的比较的比较DFSBFS4一、宽度优先搜索的算法思想　　宽度优先搜索（　　宽度优先搜索（Breadth First Search,BFS)，简，简称宽搜，又称为广度优先搜索。

它是从初始结点开始，称宽搜，又称为广度优先搜索它是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中若没有，再用查目标结点是否在这些生成的结点中若没有，再用产生式规则将所有第一层结点逐一拓展，得到第二层产生式规则将所有第一层结点逐一拓展，得到第二层结点，并逐一检查第二层结点是否包含目标结点若结点，并逐一检查第二层结点是否包含目标结点若没有，再用产生式规则拓展第二层结点如此依次拓没有，再用产生式规则拓展第二层结点如此依次拓展，检查下去，直到发现目标结点为止如果拓展完展，检查下去，直到发现目标结点为止如果拓展完所有结点，都没有发现目标结点，则问题无解所有结点，都没有发现目标结点，则问题无解　　对于同一层结点来说，它们对于问题的解的价值　　对于同一层结点来说，它们对于问题的解的价值是相同的，所以第一个找到的目标结点一定是应用产是相同的，所以第一个找到的目标结点一定是应用产生式规则最少的，因此，生式规则最少的，因此，宽搜适合求最少步骤或最短宽搜适合求最少步骤或最短解序列这类最优解问题解序列这类最优解问题　　　　5一、宽度优先搜索的算法思想abcdehfg第第0 0层层第第1 1层层第第2 2层层第第3 3层层逐层遍历逐层遍历6二、宽度优先搜索的算法分析 BFS问题解决的关键问题解决的关键•状态表示状态表示：状态一般是指现场信息的描述，通常用T表示。

一般用T0表示初始状态，Tn表示目标状态•状态转移状态转移：根据产生式规则和约束条件控制从当前状态转移到下一个状态•状态判重状态判重：大多数情况下，出现重复状态会造成死循环或空间的浪费现在在哪儿？现在在哪儿？下一步去哪儿？下一步去哪儿？去过的就别再去了！去过的就别再去了！7三、宽度优先搜索的算法实现 为保证为保证““先生成的结点先扩展先生成的结点先扩展””，宽，宽搜需用到符合搜需用到符合““先进先出先进先出””特点的特点的 这种重要的数据结构这种重要的数据结构队列队列8队列的概念队列队列队列队列：：：：限定仅在限定仅在一端一端一端一端进行插进行插入入，而在，而在另一端另一端另一端另一端进行进行删除操删除操作的线性表作的线性表 允许删除的一端称为允许删除的一端称为队队头头(front)(front)，允许插入的一，允许插入的一端称为端称为队尾队尾(rear)(rear) 当队列中没有元素时称当队列中没有元素时称为为空队列空队列空队列空队列在空队列中依次。

在空队列中依次加入元素加入元素a a1 1,a,a2 2, ,…a an n之后，之后，a a1 1是是队头元素队头元素队头元素队头元素，，a an n是是队尾元队尾元队尾元队尾元素素素素 队列(Queues)是生活中“排队” 的抽象9三、宽度优先搜索的算法实现　　队列　　队列(Queue)(Queue)允许用户从表的一端允许用户从表的一端( (队尾队尾) )入队，从表的另一端入队，从表的另一端( (队头队头) )出队因此，队列出队因此，队列也被称作先进先出线性表也被称作先进先出线性表( (FIFOFIFO-First In -First In First Out)First Out)10三、宽度优先搜索的算法实现队列实现：数组模拟、队列实现：数组模拟、STLSTL（（queuequeue））用数组模拟队列用数组模拟队列• 头指针头指针frontfront、尾指针、尾指针rearrear• 入队与出队入队与出队• 队空队空11三、宽度优先搜索的算法实现 const int MAXN = 1010; //队列的容量队列的容量上限上限 int q [MAXN]; ////队列的元素类型队列的元素类型 int front, rear; ////头指针、尾指针头指针、尾指针rearfront• 队列定义（数组）队列定义（数组）12三、宽度优先搜索的算法实现• 队列初始化，初始状态入队队列初始化，初始状态入队front = 0; rear = 1; q[1] = 1; //q[rear]=1;rearfront11约定：从1号结点开始存放队列元素13三、宽度优先搜索的算法实现•取队首元素，准备扩展取队首元素，准备扩展front++; x = q[front];rearfront1114三、宽度优先搜索的算法实现•扩展队首结点，新状态入队扩展队首结点，新状态入队rear++; q[rear] = x ; rearfront12312315三、宽度优先搜索的算法实现•队首结点扩展完毕，出队队首结点扩展完毕，出队front++;x=q[front];指针后移一位，指向待扩展节点。

rearfront12312316三、宽度优先搜索的算法实现•判断队列是否为空判断队列是否为空队列不空：队列不空：front < rearrearfront123队列空：队列空： front >= rear17三、宽度优先搜索的算法实现•队列基本操作队列基本操作const int MAXN = 101;const int MAXN = 101;int q[MAXN];int q[MAXN];int front, rear;int front, rear;int main()int main(){ { front = 0; front = 0; rear = 1; rear = 1; q[1] = 1; q[1] = 1; rear++; q[rear] = 2; rear++; q[rear] = 2; rear++; q[rear] = 3; rear++; q[rear] = 3; while(front < rear) // while(front < rear) //队队列非空列非空 { { front++; front++; ////队首出队队首出队 int x = int x = q[front]; q[front]; cout << x << " ";cout << x << " "; } } return 0; return 0; } }12318三、宽度优先搜索的算法实现•BFSBFS算法模板（数组模拟）算法模板（数组模拟）front front  0; rear 0; rear  1; 1; 初始状态入队初始状态入队; ; while(front < rear) //while(front < rear) //当队列不为空当队列不为空{ { 取队首元素进行扩展取队首元素进行扩展; ; for(for(对所有可能的拓展状态对所有可能的拓展状态) ){ {if(if(新状态合法新状态合法) ) 入队入队; ;if(if(当前状态是目标状态当前状态是目标状态) ) 处理处理( (输出解输出解或比较解的优劣或比较解的优劣); ); } }} }191.1.将队列中的所有元素均向低地址区移动，显然这种将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；方法是很浪费时间的； 用循环队列节约存储空间2.2.将数组存储区看成是一个首尾相接的环形区域。

将数组存储区看成是一个首尾相接的环形区域当存放到当存放到n n地址后，下一个地址就地址后，下一个地址就" "翻转翻转" "为１在结为１在结构上采用这种技巧来存储的队列称为循环队列构上采用这种技巧来存储的队列称为循环队列20STL中队列queue的常用函数介绍Øq.pop() 删除删除queue的队的队首首元素元素Øq.front() 返回队列的队返回队列的队首首元素，但不删除该元素元素，但不删除该元素Øq.back() 返回队列的队尾元素，但不删除该元素返回队列的队尾元素，但不删除该元素Øq.push(tmp) 将元素将元素tmp插入到队列的队尾插入到队列的队尾Øq.size() 返回队列中元素的个数返回队列中元素的个数Øq.empty() 当队列为空时返回当队列为空时返回true，否则返回，否则返回falseØwhile(!q.empty()) q.pop(); 清清空队列空队列三、宽度优先搜索的算法实现21队列queue的定义和使用queue q;int main(){ for(int i=0;i<6;i++) q.push(i); //入队列 q.push(20); cout< q; > q; ////定义一个名为定义一个名为q q的队列的队列q.push(q.push(初始状态初始状态); ); while(!q.empty()) //while(!q.empty()) //当队列不为空当队列不为空{ { 取队首元素进行扩展取队首元素进行扩展; ; for(for(对所有可能的拓展状态对所有可能的拓展状态) ){ {if(if(新状态合法新状态合法) q.push() q.push(新状态新状态););if(if(当前状态是目标状态当前状态是目标状态) ) 处理处理( (输出解输出解或比较解的优劣或比较解的优劣); ); } } q.pop(); // q.pop(); //出队出队} }23四、宽度优先搜索的算法应用（入门）• 求最优解问题求最优解问题• 求连通块问题求连通块问题24四、宽度优先搜索的算法应用 第一类应用：求最优解问题第一类应用：求最优解问题25四、宽度优先搜索的算法应用[ [例例1]1] 抓住那头牛抓住那头牛 农夫知道一头牛的位置，想要抓住它。

农农夫知道一头牛的位置，想要抓住它农夫和牛都位于数轴上，农夫起始位于点夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)N(0<=N<=100000)，牛位于点，牛位于点K(0<=K<=100000)K(0<=K<=100000) 农夫有两种移动方式：农夫有两种移动方式： 1 1、从、从X X移动到移动到X-1X-1或或X+1X+1，每次移动花费一分钟，每次移动花费一分钟 2 2、从、从X X移动到移动到2*X2*X，每次移动花费一分钟，每次移动花费一分钟 假设牛没有意识到农夫的行动，站在原地不动假设牛没有意识到农夫的行动，站在原地不动问：农夫问：农夫最少最少需要花多少时间才能抓住那头牛？需要花多少时间才能抓住那头牛？26四、宽度优先搜索的算法应用[ [例例1]1] 抓住那头牛抓住那头牛【【样例输入样例输入】】 3 5 { 3 5 {农夫起始位置农夫起始位置 牛起始位置牛起始位置} }【【样例输出样例输出】】 2 {2 {农夫抓到牛所要花费的最小分钟数农夫抓到牛所要花费的最小分钟数} }27四、宽度优先搜索的算法应用[问题分析问题分析-抓住那头牛抓住那头牛]初始状态初始状态 N N目标状态目标状态 K K状态转移状态转移规则规则1 1：：X X  X - X - 1 1规则规则2 2：： X X  X X + + 1 1规则规则3 3：： X X  2 * 2 * X X 约束条件：约束条件： 0 <= X <=100000100000状态表示状态表示 位置位置28四、宽度优先搜索的算法应用[问题分析问题分析-抓住那头牛抓住那头牛]123456789 10303246当前位置当前位置最少时间最少时间15rearfront2141611252找到目标状态找到目标状态29四、宽度优先搜索的算法应用【【思考思考】】为什么为什么BFSBFS找到的第一个目标结点一找到的第一个目标结点一定是最优解？定是最优解？ 在搜索的过程中，在搜索的过程中，BFSBFS对于结点总是沿着深对于结点总是沿着深度的断层逐层扩展的，即要扩展第度的断层逐层扩展的，即要扩展第n+1n+1层结点，层结点，必须先将第必须先将第n n层结点全部扩展完毕。

且对于同一层结点全部扩展完毕且对于同一层结点而言，它们对于问题解的价值是相同的层结点而言，它们对于问题解的价值是相同的 所以所以BFSBFS一定能保证：第一个找到的目标结点，一定能保证：第一个找到的目标结点，一定是应用产生式规则最少的因此，一定是应用产生式规则最少的因此，宽度优宽度优先搜索较适合求最优解的问题先搜索较适合求最优解的问题30四、宽度优先搜索的算法应用[ [例例2]2] 小明抄答案小明抄答案 有一次上数学课，老师布置了课堂作有一次上数学课，老师布置了课堂作业小明在写作业时睡着了他梦见自己站在业小明在写作业时睡着了他梦见自己站在一个迷宫里，一个圣人给了他迷宫的地图，说：一个迷宫里，一个圣人给了他迷宫的地图，说：““你现在位于你现在位于迷宫的左上角迷宫的左上角，，迷宫的右下角迷宫的右下角有有数学作业的答案你只能数学作业的答案你只能上下左右上下左右走，但你放走，但你放心，我没有耍你，迷宫是一定能走得通的心，我没有耍你，迷宫是一定能走得通的小明很想拿到答案，但他太笨了小明很想拿到答案，但他太笨了，所以找来了会编程的你，叫你，所以找来了会编程的你，叫你帮他找到答案。

他需要知道找到帮他找到答案他需要知道找到答案的答案的最少步数最少步数31四、宽度优先搜索的算法应用[ [例例2]2] 小明抄答案小明抄答案 【【输入输入】】 第一行是两个整数，Ｒ和Ｃ，代表迷宫的行第一行是两个整数，Ｒ和Ｃ，代表迷宫的行数和列数（数和列数（2<=R,C <=1002<=R,C <=100）接下来的Ｒ行，每行Ｃ）接下来的Ｒ行，每行Ｃ个字符，代表整个迷宫空地格子用个字符，代表整个迷宫空地格子用'.''.'表示，有障表示，有障碍物的格子用碍物的格子用'#''#'表示迷宫左上角和右下角都是表示迷宫左上角和右下角都是'.''.'输出输出】】 一行包含一个整数，输出从左上角走到右下一行包含一个整数，输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）角至少要经过多少步（即至少要经过多少个空地格子）注：计算步数要包括起点和终点计算步数要包括起点和终点32四、宽度优先搜索的算法应用[ [问题分析问题分析- -小明抄答案小明抄答案] ] • 状态表示：状态表示： 初始状态：初始状态： 目标状态：目标状态： (1,1)(r,c)11StartEndrc当前所在迷宫的位置（行号当前所在迷宫的位置（行号, , 列号）列号）左上角左上角右下角右下角33四、宽度优先搜索的算法应用[ [问题分析问题分析- -小明抄答案小明抄答案] ] •状态转移：状态转移： 转移规则：转移规则： 约束条件：约束条件：1 <= x <= r 1 <= y <= c④③ (x,y)① ②①① (x,y+1)②② (x+1,y)③③ (x,y-1)④④ (x-1,y)34四、宽度优先搜索的算法应用[ [问题分析问题分析- -小明抄答案小明抄答案] ] 1 2 3 4 5 6 7 8 9111行号行号最少步数最少步数12341●●##2#●●#3#●#●4#●●●列号列号(1,1)(1,2)(2,2)(2,3)(3,2)(4,2)(4,3)(4,4)122223234324425436447找到目标状态找到目标状态35四、宽度优先搜索的算法应用[问题分析问题分析-小明抄答案小明抄答案]思思考考：：如如果果要要输输出出其其中中一一条条最最短短路路径径，，怎怎么么办办？？1234567811 22344412 23223412 34456701 233567行号行号最少步数最少步数列号列号前驱节点前驱节点(1,1) (1,2)(2,2)(3,2)(4,2)(4,3)(4,4) 12341●●##2#●●#3#●#●4#●●●36四、宽度优先搜索的算法应用 第二类应用：求连通块问题第二类应用：求连通块问题37四、宽度优先搜索的算法应用[ [例例3]3] 宝岛探险宝岛探险【【题目描述题目描述】】 某海域航拍图由一个某海域航拍图由一个R R行行C C列列的数字的数字矩阵组成，图中数字表示海拔，矩阵组成，图中数字表示海拔，0 0表示海洋，表示海洋，1~91~9表示陆地表示陆地。

求该海域共有多少岛屿，最大求该海域共有多少岛屿，最大的岛屿面积多大（即包含多少格子）我们把的岛屿面积多大（即包含多少格子）我们把上下左右相邻接上下左右相邻接的陆地视为同一岛屿的陆地视为同一岛屿38四、宽度优先搜索的算法应用[ [例例3]3] 宝岛探险宝岛探险【【样例输入样例输入】】 【【样例输出样例输出】】 4 10 4 11 0234500067 1034560500 2045600671 0000000089【【数据范围数据范围】】 1<= R，C <= 2039四、宽度优先搜索的算法应用[ [问题分析问题分析- -宝岛探险宝岛探险] ] 求连通块问题的基本思路是：从某求连通块问题的基本思路是：从某关键点（不是海洋的点）开始关键点（不是海洋的点）开始BFSBFS，形成的，形成的连通区域即为一连通块连通区域即为一连通块40四、宽度优先搜索的算法应用[ [问题分析问题分析- -宝岛探险宝岛探险] ]1234567891010234500067210345605003204560067140000000089每找到一个岛每找到一个岛屿，个数就屿，个数就+141四、宽度优先搜索的算法应用[ [问题分析问题分析- -宝岛探险宝岛探险] ]123456789 10 1112123456789101023450006721034560500320456006714000000008913142315243325342635rear即为当前即为当前岛屿大小岛屿大小ij42for(int i=1;i<=n;i++)for(int i=1;i<=n;i++) for(int j=0;jimax)imax=tot;if(tot>imax)imax=tot; } } } }void bfs()void bfs(){ { while(!q.empty()) while(!q.empty()) { { for(int i=0;i<4;i++)for(int i=0;i<4;i++) { { tmp.x=q.front().x+dx[i]tmp.x=q.front().x+dx[i]; ; tmp.y=q.front().y+dy[i]tmp.y=q.front().y+dy[i]; ; if(tmp.x>=1&&tmp.x<=n&&if(tmp.x>=1&&tmp.x<=n&&tmp.y>=0&&tmp.y=0&&tmp.y

我们可以把油从一个桶倒到另一升桶是空的我们可以把油从一个桶倒到另一个桶中，每一次的倒油过程都以原始桶空或目个桶中，每一次的倒油过程都以原始桶空或目标桶满为结束，且倒油过程中不会产生任何的标桶满为结束，且倒油过程中不会产生任何的浪费那么最少需要几步可在浪费那么最少需要几步可在1010升桶和升桶和7 7升桶升桶中各装入中各装入5 5升的油？升的油？五、课后讨论44[ [问题分析问题分析- -倒油问题倒油问题] ]•状态的表示状态的表示 初始状态：初始状态： 目标状态：目标状态： 用一个三元组用一个三元组T T（（x10,x7,x3x10,x7,x3）表示状态，）表示状态，其中其中x10x10，，x7x7，，x3x3分别表示分别表示三个瓶子中的三个瓶子中的当前当前油量10,0,0）（5,5,0）五、课后讨论45[ [问题分析问题分析- -倒油问题倒油问题] ]•状态的转移（规则）状态的转移（规则） 三个瓶子（三个瓶子（x10,x7,x3x10,x7,x3））有有6 6种种倒油倒油规则规则：：10升瓶7升瓶10升瓶3升瓶7升瓶10升瓶7升瓶3升瓶3升瓶10升瓶3升瓶7升瓶五、课后讨论46[问题分析问题分析-倒油问题倒油问题]•状态的转移（约束条件）状态的转移（约束条件） 当当 且且 时：时：如果如果 , ,那么那么 倒满倒满7 7升瓶升瓶 新状态新状态T’( T’( ) )入队入队否则否则 倒空倒空1010升瓶升瓶 新状态新状态T ’( T ’( ) ) 入队入队10升瓶7升瓶10升瓶有油 7升瓶未满10升瓶油+7升瓶油 >= 7 10升瓶油+7升瓶油-7,7,不变 0,10升瓶油+7升瓶油 ,不变 五、课后讨论47[问题分析问题分析-倒油问题倒油问题]•状态的转移（约束条件）状态的转移（约束条件） 当当 且且 时：时：如果如果 , ,那么那么 倒满倒满7 7升瓶升瓶 新状态新状态T’( T’( ) )入队入队否则否则 倒空倒空1010升瓶升瓶 新状态新状态T ’( T ’( ) )入队入队10升瓶7升瓶x10 > 0 x7 < 7x10 + x7 >= 7 x10+x7-7,7,x3 0,x10+x7,x3五、课后讨论4810,0,03,7,07,0,30,7,33,4,37,3,06,4,04,3,36,1,34,6,09,1,01,6,39,0,12,7,12,5,35,5,0五、课后讨论49小￿结￿-￿宽度优先搜索的特点•一般来讲，宽度优先搜索需要储存所产生的一般来讲，宽度优先搜索需要储存所产生的所有节点。

因此，占用的空间比较多，必须考所有节点因此，占用的空间比较多，必须考虑溢出和节约内存的问题虑溢出和节约内存的问题•必须注意判重，宽搜会产生重复节点，因此必须注意判重，宽搜会产生重复节点，因此一定要把重复节点删除一定要把重复节点删除•无回溯的操作因此，在搜索速度上比较快无回溯的操作因此，在搜索速度上比较快•若问题的解要一条路径，则需对每个节点都若问题的解要一条路径，则需对每个节点都要保存其父节点，以便输出那条路径要保存其父节点，以便输出那条路径50小￿结建议一、队列元素使用结构体表示；建议一、队列元素使用结构体表示；建议二、可直接利用建议二、可直接利用STLSTL中的中的queuequeue方便完成方便完成51Thank you!52。