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

《信息学奥赛宽搜及应用ppt课件》由会员分享，可在线阅读，更多相关《信息学奥赛宽搜及应用ppt课件（52页珍藏版）》请在装配图网上搜索。

1、宽搜及应用宽搜及应用本讲要点宽搜及其算法思想宽搜的算法实现宽搜应用初步本讲要点宽搜及其算法思想引言 搜索算法是基于计算机高速运算的特点而搜索算法是基于计算机高速运算的特点而使用的求解方法。它从问题的初始状态出发，根据使用的求解方法。它从问题的初始状态出发，根据约束条件，按照一定的策略，有序推进，不断深入，约束条件，按照一定的策略，有序推进，不断深入，最终到达所有符合条件的目标状态（或无解），或最终到达所有符合条件的目标状态（或无解），或者找出所有可行解中的最优解。者找出所有可行解中的最优解。按照推进的控制策略，搜索一般分为宽度优先按照推进的控制策略，搜索一般分为宽度优先搜索和深度优先搜索。搜索

2、和深度优先搜索。引 言 搜索算法是基于计算机高速运算的特 白色表示未访问的节点，黑色表示已经访问的白色表示未访问的节点，黑色表示已经访问的节点，灰色表示：节点，灰色表示：DFSDFS中为正在访问的节点，中为正在访问的节点，BFSBFS中中为已入队等待访问的节点。为已入队等待访问的节点。深度优先搜索（深度优先搜索（DFS）与宽度优先搜索（）与宽度优先搜索（BFS)的比较的比较DFSBFS 白色表示未访问的节点，黑色表示已经访问的节点，灰色表一、宽度优先搜索的算法思想宽度优先搜索（宽度优先搜索（Breadth First Search,BFS)，简，简称宽搜，又称为广度优先搜索。它是从初始结点开始

3、，称宽搜，又称为广度优先搜索。它是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中。若没有，再用查目标结点是否在这些生成的结点中。若没有，再用产生式规则将所有第一层结点逐一拓展，得到第二层产生式规则将所有第一层结点逐一拓展，得到第二层结点，并逐一检查第二层结点是否包含目标结点。若结点，并逐一检查第二层结点是否包含目标结点。若没有，再用产生式规则拓展第二层结点。如此依次拓没有，再用产生式规则拓展第二层结点。如此依次拓展，检查下去，直到发现目标结点为止。如果拓展完展，检查下去，直到发现目标结点为止。如果拓展

4、完所有结点，都没有发现目标结点，则问题无解。所有结点，都没有发现目标结点，则问题无解。对于同一层结点来说，它们对于问题的解的价值对于同一层结点来说，它们对于问题的解的价值是相同的，所以第一个找到的目标结点一定是应用产是相同的，所以第一个找到的目标结点一定是应用产生式规则最少的，因此，生式规则最少的，因此，宽搜适合求最少步骤或最短宽搜适合求最少步骤或最短解序列这类最优解问题。解序列这类最优解问题。一、宽度优先搜索的算法思想宽度优先搜索（Breadth 一、宽度优先搜索的算法思想abcdehfg第第0层层第第1层层第第2层层第第3层层一、宽度优先搜索的算法思想abcdehfg第0层第1层第2层二、

5、宽度优先搜索的算法分析 BFS问题解决的关键问题解决的关键状态表示状态表示：状态一般是指现场信息的描述，通常用T表示。一般用T0表示初始状态，Tn表示目标状态。状态转移状态转移：根据产生式规则和约束条件控制从当前状态转移到下一个状态。状态判重状态判重：大多数情况下，出现重复状态会造成死循环或空间的浪费。现在在哪儿？现在在哪儿？下一步去哪儿？下一步去哪儿？去过的就别再去了！去过的就别再去了！二、宽度优先搜索的算法分析 BFS问题解决的关键现在在哪儿三、宽度优先搜索的算法实现 为保证为保证“先生成的结点先扩展先生成的结点先扩展”，宽，宽搜需用到符合搜需用到符合“先进先出先进先出”特点的特点的 这种

6、重要的数据结构。这种重要的数据结构。三、宽度优先搜索的算法实现 为保证“先生成的队列的概念队列队列队列队列：限定仅在限定仅在一端一端一端一端进行插进行插入入，而在，而在另一端另一端另一端另一端进行进行删除操删除操作的线性表作的线性表。允许删除的一端称为允许删除的一端称为队队头头(front)(front)，允许插入的一，允许插入的一端称为端称为队尾队尾(rear)(rear)。当队列中没有元素时称当队列中没有元素时称为为空队列空队列空队列空队列。在空队列中依次。在空队列中依次加入元素加入元素a a1 1,a,a2 2,a an n之后，之后，a a1 1是是队头元素队头元素队头元素队头元素，a

7、 an n是是队尾元队尾元队尾元队尾元素素素素。队列(Queues)是生活中“排队”的抽象。队列的概念队列：限定仅在一端进行插入，而在另一端进行删除操作三、宽度优先搜索的算法实现队列队列(Queue)允许用户从表的一端允许用户从表的一端(队尾队尾)入入队，从表的另一端队，从表的另一端(队头队头)出队。因此，队列也出队。因此，队列也被称作先进先出线性表被称作先进先出线性表(FIFO-First In First Out)。三、宽度优先搜索的算法实现队列(Queue)允许用户从表三、宽度优先搜索的算法实现队列实现：数组模拟、队列实现：数组模拟、STL（queue）用数组模拟队列用数组模拟队列 头指

8、针头指针front、尾指针、尾指针rear 入队与出队入队与出队 队空队空三、宽度优先搜索的算法实现队列实现：数组模拟、STL（que三、宽度优先搜索的算法实现 const int MAXN=1010;/队列的容量上限队列的容量上限 int q MAXN;/队列的元素类型队列的元素类型 int front,rear;/头指针、尾指针头指针、尾指针rearfront 队列定义（数组）队列定义（数组）三、宽度优先搜索的算法实现 const int MAXN 三、宽度优先搜索的算法实现 队列初始化，初始状态入队队列初始化，初始状态入队front=0;rear=1;q1=1;/qrear=1;rear

9、front11约定：从1号结点开始存放队列元素三、宽度优先搜索的算法实现 队列初始化，初始状态入队fron三、宽度优先搜索的算法实现取队首元素，准备扩展取队首元素，准备扩展front+;x=qfront;rearfront11三、宽度优先搜索的算法实现取队首元素，准备扩展front+三、宽度优先搜索的算法实现扩展队首结点，新状态入队扩展队首结点，新状态入队rear+;qrear=x;rearfront123123三、宽度优先搜索的算法实现扩展队首结点，新状态入队rear+三、宽度优先搜索的算法实现队首结点扩展完毕，出队队首结点扩展完毕，出队front+;x=qfront;指针后移一位，指向待扩

10、展节点。rearfront123123三、宽度优先搜索的算法实现队首结点扩展完毕，出队front+三、宽度优先搜索的算法实现判断队列是否为空判断队列是否为空队列不空：队列不空：front=rear三、宽度优先搜索的算法实现判断队列是否为空队列不空：fron三、宽度优先搜索的算法实现队列基本操作队列基本操作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+;/队首出队队首出队 i

11、nt x=qfront;cout x ;return 0;123三、宽度优先搜索的算法实现队列基本操作const int M三、宽度优先搜索的算法实现BFS算法模板（数组模拟）算法模板（数组模拟）front 0;rear 1;初始状态入队初始状态入队;while(front rear)/当队列不为空当队列不为空 取队首元素进行扩展取队首元素进行扩展;for(对所有可能的拓展状态对所有可能的拓展状态)if(新状态合法新状态合法)入队入队;if(当前状态是目标状态当前状态是目标状态)处理处理(输出解或比较解的优劣输出解或比较解的优劣);三、宽度优先搜索的算法实现BFS算法模板（数组模拟）fron1

12、.1.将队列中的所有元素均向低地址区移动，显然这种将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；方法是很浪费时间的；用循环队列节约存储空间2.2.将数组存储区看成是一个首尾相接的环形区域。将数组存储区看成是一个首尾相接的环形区域。当存放到当存放到n n地址后，下一个地址就地址后，下一个地址就 翻转翻转 为。在结为。在结构上采用这种技巧来存储的队列称为循环队列。构上采用这种技巧来存储的队列称为循环队列。1.将队列中的所有元素均向低地址区移动，显然这种方法是很浪费STL中队列queue的常用函数介绍q.pop()删除删除queue的队的队首首元素元素q.front()返回队列的队

13、返回队列的队首首元素，但不删除该元素元素，但不删除该元素q.back()返回队列的队尾元素，但不删除该元素返回队列的队尾元素，但不删除该元素q.push(tmp)将元素将元素tmp插入到队列的队尾插入到队列的队尾q.size()返回队列中元素的个数返回队列中元素的个数q.empty()当队列为空时返回当队列为空时返回true，否则返回，否则返回falsewhile(!q.empty()q.pop();清清空队列空队列三、宽度优先搜索的算法实现STL中队列queue的常用函数介绍q.pop()队列queue的定义和使用queue q;int main()for(int i=0;i6;i+)q.p

14、ush(i);/入队列 q.push(20);coutq.size()endl;/队列元素个数 while(!q.empty()/队列不空时循环 coutq.front();/输出队首元素 q.pop();/删除队首元素 return 0;三、宽度优先搜索的算法实现队列queue的定义和使用queue q;三、宽度三、宽度优先搜索的算法实现BFS算法模板（算法模板（queue）queue q;/定义一个名为定义一个名为q的队列的队列q.push(初始状态初始状态);while(!q.empty()/当队列不为空当队列不为空 取队首元素进行扩展取队首元素进行扩展;for(对所有可能的拓展状态对所

15、有可能的拓展状态)if(新状态合法新状态合法)q.push(新状态新状态);if(当前状态是目标状态当前状态是目标状态)处理处理(输出解或比较解的优劣输出解或比较解的优劣);q.pop();/出队出队三、宽度优先搜索的算法实现BFS算法模板（queue）que四、宽度优先搜索的算法应用（入门）求最优解问题求最优解问题 求连通块问题求连通块问题四、宽度优先搜索的算法应用（入门）求最优解问题四、宽度优先搜索的算法应用 第一类应用：求最优解问题第一类应用：求最优解问题四、宽度优先搜索的算法应用 第一类应用：求最优解问题四、宽度优先搜索的算法应用例例1 抓住那头牛抓住那头牛 农夫知道一头牛的位置，想要

16、抓住它。农农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点夫和牛都位于数轴上，农夫起始位于点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，每次移动花费一分钟，每次移动花费一分钟 假设牛没有意识到农夫的行动，站在原地不动。假设牛没有意识到农夫的行动，站在原地不动。问：农夫问：农夫最少最少需要花多少时间才能抓住那

17、头牛？需要花多少时间才能抓住那头牛？四、宽度优先搜索的算法应用例1 抓住那头牛四、宽度优先搜索的算法应用例例1 抓住那头牛抓住那头牛【样例输入样例输入】3 5 农夫起始位置农夫起始位置 牛起始位置牛起始位置【样例输出样例输出】2 农夫抓到牛所要花费的最小分钟数农夫抓到牛所要花费的最小分钟数四、宽度优先搜索的算法应用例1 抓住那头牛四、宽度优先搜索的算法应用问题分析问题分析-抓住那头牛抓住那头牛初始状态初始状态 N目标状态目标状态 K状态转移状态转移规则规则1：X X-1规则规则2：X X+1规则规则3：X 2*X 约束条件：约束条件：0=X=100000100000状态表示状态表示 位置位置四

18、、宽度优先搜索的算法应用问题分析-抓住那头牛初始状态 四、宽度优先搜索的算法应用问题分析问题分析-抓住那头牛抓住那头牛123456789 10303246当前位置当前位置最少时间最少时间15rearfront2141611252找到目标状态找到目标状态四、宽度优先搜索的算法应用问题分析-抓住那头牛12345四、宽度优先搜索的算法应用【思考思考】为什么为什么BFS找到的第一个目标结点一找到的第一个目标结点一定是最优解？定是最优解？在搜索的过程中，在搜索的过程中，BFSBFS对于结点总是沿着深对于结点总是沿着深度的断层逐层扩展的，即要扩展第度的断层逐层扩展的，即要扩展第n+1n+1层结点，层结点，

19、必须先将第必须先将第n n层结点全部扩展完毕。且对于同一层结点全部扩展完毕。且对于同一层结点而言，它们对于问题解的价值是相同的。层结点而言，它们对于问题解的价值是相同的。所以所以BFSBFS一定能保证：第一个找到的目标结点，一定能保证：第一个找到的目标结点，一定是应用产生式规则最少的。因此，一定是应用产生式规则最少的。因此，宽度优宽度优先搜索较适合求最优解的问题先搜索较适合求最优解的问题。四、宽度优先搜索的算法应用【思考】为什么BFS找到的第一个目四、宽度优先搜索的算法应用例例2 小明抄答案小明抄答案 有一次上数学课，老师布置了课堂作有一次上数学课，老师布置了课堂作业。小明在写作业时睡着了。他

20、梦见自己站在业。小明在写作业时睡着了。他梦见自己站在一个迷宫里，一个圣人给了他迷宫的地图，说：一个迷宫里，一个圣人给了他迷宫的地图，说：“你现在位于你现在位于迷宫的左上角迷宫的左上角，迷宫的右下角迷宫的右下角有有数学作业的答案。你只能数学作业的答案。你只能上下左右上下左右走，但你放走，但你放心，我没有耍你，迷宫是一定能走得通的。心，我没有耍你，迷宫是一定能走得通的。”小明很想拿到答案，但他太笨了小明很想拿到答案，但他太笨了，所以找来了会编程的你，叫你，所以找来了会编程的你，叫你帮他找到答案。他需要知道找到帮他找到答案。他需要知道找到答案的答案的最少步数最少步数。四、宽度优先搜索的算法应用例2

21、小明抄答案四、宽度优先搜索的算法应用例例2 小明抄答案小明抄答案 【输入输入】第一行是两个整数，和，代表迷宫的行数和第一行是两个整数，和，代表迷宫的行数和列数（列数（2=R,C=100）。接下来的行，每行个字）。接下来的行，每行个字符，代表整个迷宫。空地格子用符，代表整个迷宫。空地格子用.表示，有障碍物的表示，有障碍物的格子用格子用#表示。迷宫左上角和右下角都是表示。迷宫左上角和右下角都是.。【输出输出】一行包含一个整数，输出从左上角走到右下角至一行包含一个整数，输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。少要经过多少步（即至少要经过多少个空地格子）。注：注：计算步数

22、要包括起点和终点。计算步数要包括起点和终点。四、宽度优先搜索的算法应用例2 小明抄答案四、宽度优先搜索的算法应用问题分析问题分析-小明抄答案小明抄答案 状态表示：状态表示：初始状态：初始状态：目标状态：目标状态：(1,1)(r,c)11StartEndrc当前所在迷宫的位置（行号当前所在迷宫的位置（行号,列号）列号）左上角左上角右下角右下角四、宽度优先搜索的算法应用问题分析-小明抄答案 四、宽度优先搜索的算法应用问题分析问题分析-小明抄答案小明抄答案 状态转移：状态转移：转移规则：转移规则：约束条件：约束条件：1=x=r 1=y=c(x,y)(x,y+1)(x+1,y)(x,y-1)(x-1,

23、y)四、宽度优先搜索的算法应用问题分析-小明抄答案 四、宽度优先搜索的算法应用问题分析问题分析-小明抄答案小明抄答案 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找到目标状态找到目标状态四、宽度优先搜索的算法应用问题分析-小明抄答案 四、宽度优先搜索的算法应用问题分析问题分析-小明抄答案小明抄答案思思考考：如如果果要要输出出其其中中一一条条最最短短路路径径，怎怎么么办？1234567811 22344412 2322341

24、2 34456701 233567行号行号最少步数最少步数列号列号前驱节点前驱节点(1,1)(1,2)(2,2)(3,2)(4,2)(4,3)(4,4)12341#2#3#4#四、宽度优先搜索的算法应用问题分析-小明抄答案12345四、宽度优先搜索的算法应用 第二类应用：求连通块问题第二类应用：求连通块问题四、宽度优先搜索的算法应用 第二类应用：求连通块问题四、宽度优先搜索的算法应用例例3 宝岛探险宝岛探险【题目描述题目描述】某海域航拍图由一个某海域航拍图由一个R R行行C C列列的数字的数字矩阵组成，图中数字表示海拔，矩阵组成，图中数字表示海拔，0 0表示海洋，表示海洋，1919表示陆地表示

25、陆地。求该海域共有多少岛屿，最大。求该海域共有多少岛屿，最大的岛屿面积多大（即包含多少格子）。我们把的岛屿面积多大（即包含多少格子）。我们把上下左右相邻接上下左右相邻接的陆地视为同一岛屿。的陆地视为同一岛屿。四、宽度优先搜索的算法应用例3 宝岛探险四、宽度优先搜索的算法应用例例3 宝岛探险宝岛探险【样例输入样例输入】【样例输出样例输出】4 10 4 11 0234500067 1034560500 2045600671 0000000089【数据范围数据范围】1=R，C=20四、宽度优先搜索的算法应用例3 宝岛探险四、宽度优先搜索的算法应用问题分析问题分析-宝岛探险宝岛探险 求连通块问题的基本

26、思路是：从某求连通块问题的基本思路是：从某关键点（不是海洋的点）开始关键点（不是海洋的点）开始BFS，形成的，形成的连通区域即为一连通块。连通区域即为一连通块。四、宽度优先搜索的算法应用问题分析-宝岛探险 四、宽度优先搜索的算法应用问题分析问题分析-宝岛探险宝岛探险1234567891010234500067210345605003204560067140000000089每找到一个岛每找到一个岛屿，个数就屿，个数就+1四、宽度优先搜索的算法应用问题分析-宝岛探险123456四、宽度优先搜索的算法应用问题分析问题分析-宝岛探险宝岛探险123456789 10 11121234567891010

27、23450006721034560500320456006714000000008913142315243325342635rear即为当前即为当前岛屿大小岛屿大小ij四、宽度优先搜索的算法应用问题分析-宝岛探险123456for(int i=1;i=n;i+)for(int j=0;jimax)imax=tot;void bfs()while(!q.empty()for(int i=0;i=1&tmp.x=0&tmp.ym&stmp.xtmp.y!=0)q.push(tmp);stmp.xtmp.y=0;tot+;q.pop();输出什么输出什么输出什么输出什么?for(int i=1;i=

28、7 10升瓶油+7升瓶油-7,7,不变 0,10升瓶油+7升瓶油,不变 五、课后讨论问题分析-倒油问题当 问题分析问题分析-倒油问题倒油问题状态的转移（约束条件）状态的转移（约束条件）当当 且且 时：时：如果如果 ,那么那么 倒满倒满7升瓶升瓶 新状态新状态T()入队入队否则否则 倒空倒空10升瓶升瓶 新状态新状态T()入队入队10升瓶7升瓶x10 0 x7=7 x10+x7-7,7,x3 0,x10+x7,x3五、课后讨论问题分析-倒油问题当 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,

29、35,5,0五、课后讨论10,0,03,7,07,0,30,7,33,4,37,3,小结-宽度优先搜索的特点一般来讲，宽度优先搜索需要储存所产生的一般来讲，宽度优先搜索需要储存所产生的所有节点。因此，占用的空间比较多，必须考所有节点。因此，占用的空间比较多，必须考虑溢出和节约内存的问题。虑溢出和节约内存的问题。必须注意判重，宽搜会产生重复节点，因此必须注意判重，宽搜会产生重复节点，因此一定要把重复节点删除。一定要把重复节点删除。无回溯的操作。因此，在搜索速度上比较快。无回溯的操作。因此，在搜索速度上比较快。若问题的解要一条路径，则需对每个节点都若问题的解要一条路径，则需对每个节点都要保存其父节点，以便输出那条路径。要保存其父节点，以便输出那条路径。小 结-宽度优先搜索的特点一般来讲，宽度优先搜索需要储存小结建议一、队列元素使用结构体表示；建议一、队列元素使用结构体表示；建议二、可直接利用建议二、可直接利用STL中的中的queue方便完成方便完成小 结建议一、队列元素使用结构体表示；Thank you!Thank you!