信息学奥赛宽搜及应用复习进程

宽搜及应用本讲要点•宽搜及其算法思想•宽搜的算法实现•宽搜应用初步引言搜索算法是基于计算机高速运算的特点而使用的求解方法。它从问题的初始状态出发，根据约束条件，按照一定的策略，有序推进，不断深入，最终到达所有符合条件的目标状态（或无解），或者找出所有可行解中的最优解。按照推进的控制策略，搜索一般分为宽度优先搜索和深度优先搜索。白色表示未访问的节点，黑色表示已经访问的节点，灰色表示：DFS中为正在访问的节点，BFS中为已入队等待访问的节点。深度优先搜索（DFS）与宽度优先搜索（BFS)的比较DFSBFS一、宽度优先搜索的算法思想宽度优先搜索（BreadthFirstSearch,BFS)，简称宽搜，又称为广度优先搜索。它是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中。若没有，再用产生式规则将所有第一层结点逐一拓展，得到第二层结点，并逐一检查第二层结点是否包含目标结点。若没有，再用产生式规则拓展第二层结点。如此依次拓展，检查下去，直到发现目标结点为止。如果拓展完所有结点，都没有发现目标结点，则问题无解。对于同一层结点来说，它们对于问题的解的价值是相同的，所以第一个找到的目标结点一定是应用产生式规则最少的，因此，宽搜适合求最少步骤或最短解序列这类最优解问题。一、宽度优先搜索的算法思想abcdehfg第0层第1层第2层第3层逐层遍历二、宽度优先搜索的算法分析BFS问题解决的关键•状态表示：状态一般是指现场信息的描述，通常用T表示。一般用T0表示初始状态，Tn表示目标状态。•状态转移：根据产生式规则和约束条件控制从当前状态转移到下一个状态。•状态判重：大多数情况下，出现重复状态会造成死循环或空间的浪费。现在在哪儿？下一步去哪儿？去过的就别再去了！三、宽度优先搜索的算法实现为保证“先生成的结点先扩展”，宽搜需用到符合“先进先出”特点的这种重要的数据结构。队列队列的概念队列：限定仅在一端进行插入，而在另一端进行删除操作的线性表。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。队列(Queues)是生活中“排队”的抽象。三、宽度优先搜索的算法实现队列(Queue)允许用户从表的一端(队尾)入队，从表的另一端(队头)出队。因此，队列也被称作先进先出线性表(FIFO-FirstInFirstOut)。三、宽度优先搜索的算法实现队列实现：数组模拟、STL（queue）用数组模拟队列•头指针front、尾指针rear•入队与出队•队空三、宽度优先搜索的算法实现constintMAXN=1010;//队列的容量上限intq[MAXN];//队列的元素类型intfront,rear;//头指针、尾指针rearfront•队列定义（数组）三、宽度优先搜索的算法实现•队列初始化，初始状态入队front=0;rear=1;q[1]=1;//q[rear]=1;rearfront11约定：从1号结点开始存放队列元素三、宽度优先搜索的算法实现•取队首元素，准备扩展front++;x=q[front];rearfront11三、宽度优先搜索的算法实现•扩展队首结点，新状态入队rear++;q[rear]=x;rearfront123123三、宽度优先搜索的算法实现•队首结点扩展完毕，出队front++;x=q[front];指针后移一位，指向待扩展节点。rearfront123123三、宽度优先搜索的算法实现•判断队列是否为空队列不空：frontrearrearfront123队列空：front=rear三、宽度优先搜索的算法实现•队列基本操作constintMAXN=101;intq[MAXN];intfront,rear;intmain(){front=0;rear=1;q[1]=1;rear++;q[rear]=2;rear++;q[rear]=3;while(frontrear)//队列非空{front++;//队首出队intx=q[front];coutx;}return0;}123三、宽度优先搜索的算法实现•BFS算法模板（数组模拟）front0;rear1;初始状态入队;while(frontrear)//当队列不为空{取队首元素进行扩展;for(对所有可能的拓展状态){if(新状态合法)入队;if(当前状态是目标状态)处理(输出解或比较解的优劣);}}1.将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；用循环队列节约存储空间2.将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就翻转为１。在结构上采用这种技巧来存储的队列称为循环队列。STL中队列queue的常用函数介绍q.pop()删除queue的队首元素q.front()返回队列的队首元素，但不删除该元素q.back()返回队列的队尾元素，但不删除该元素q.push(tmp)将元素tmp插入到队列的队尾q.size()返回队列中元素的个数q.empty()当队列为空时返回true，否则返回falsewhile(!q.empty())q.pop();清空队列三、宽度优先搜索的算法实现队列queue的定义和使用queueintq;intmain(){for(inti=0;i6;i++)q.push(i);//入队列q.push(20);coutq.size()endl;//队列元素个数while(!q.empty())//队列不空时循环{coutq.front()‘’;//输出队首元素q.pop();//删除队首元素}return0;}三、宽度优先搜索的算法实现三、宽度优先搜索的算法实现•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]抓住那头牛【样例输入】35{农夫起始位置牛起始位置}【样例输出】2{农夫抓到牛所要花费的最小分钟数}四、宽度优先搜索的算法应用[问题分析-抓住那头牛]初始状态N目标状态K状态转移规则1：XX-1规则2：XX+1规则3：X2*X约束条件：0=X=100000状态表示位置四、宽度优先搜索的算法应用[问题分析-抓住那头牛]12345678910303246当前位置最少时间15rearfront2141611252找到目标状态四、宽度优先搜索的算法应用【思考】为什么BFS找到的第一个目标结点一定是最优解？在搜索的过程中，BFS对于结点总是沿着深度的断层逐层扩展的，即要扩展第n+1层结点，必须先将第n层结点全部扩展完毕。且对于同一层结点而言，它们对于问题解的价值是相同的。所以BFS一定能保证：第一个找到的目标结点，一定是应用产生式规则最少的。因此，宽度优先搜索较适合求最优解的问题。四、宽度优先搜索的算法应用[例2]小明抄答案有一次上数学课，老师布置了课堂作业。小明在写作业时睡着了。他梦见自己站在一个迷宫里，一个圣人给了他迷宫的地图，说：“你现在位于迷宫的左上角，迷宫的右下角有数学作业的答案。你只能上下左右走，但你放心，我没有耍你，迷宫是一定能走得通的。”小明很想拿到答案，但他太笨了，所以找来了会编程的你，叫你帮他找到答案。他需要知道找到答案的最少步数。四、宽度优先搜索的算法应用[例2]小明抄答案【输入】第一行是两个整数，Ｒ和Ｃ，代表迷宫的行数和列数（2=R,C=100）。接下来的Ｒ行，每行Ｃ个字符，代表整个迷宫。空地格子用'.'表示，有障碍物的格子用'#'表示。迷宫左上角和右下角都是'.'。【输出】一行包含一个整数，输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。注：计算步数要包括起点和终点。四、宽度优先搜索的算法应用[问题分析-小明抄答案]•状态表示：初始状态：目标状态：(1,1)(r,c)11StartEndrc当前所在迷宫的位置（行号,列号）左上角右下角四、宽度优先搜索的算法应用[问题分析-小明抄答案]•状态转移：转移规则：约束条件：1=x=r1=y=c④③(x,y)①②①(x,y+1)②(x+1,y)③(x,y-1)④(x-1,y)四、宽度优先搜索的算法应用[问题分析-小明抄答案]123456789111行号最少步数12341●●##2#●●#3#●#●4#●●●列号(1,1)(1,2)(2,2)(2,3)(3,2)(4,2)(4,3)(4,4)122223234324425436447找到目标状态四、宽度优先搜索的算法应用[问题分析-小明抄答案]思考：如果要输出其中一条最短路径，怎么办？1234567811223444122322341234456701233567行号最少步数列号前驱节点(1,1)(1,2)(2,2)(3,2)(4,2)(4,3)(4,4)12341●●##2#●●#3#●#●4#●●●四、宽度优先搜索的算法应用第二类应用：求连通块问题四、宽度优先搜索的算法应用[例3]宝岛探险【题目描述】某海域航拍图由一个R行C列的数字矩阵组成，图中数字表示海拔，0表示海洋，1~9表示陆地。求该海域共有多少岛屿，最大的岛屿面积多大（即包含多少格子）。我们把上下左右相邻接的陆地视为同一岛屿。四、宽度优先搜索的算法应用[例3]宝岛探险【样例输入】【样例输出】4104110234500067103456050020456006710000000089【数据范围】1=R，C=20四、宽度优先搜索的算法应用[问题分析-宝岛探险]求连通块问题的基本思路是：从某关键点（不是海洋的点）开始BFS，形成的连通区域即为一连通块。四、宽度优先搜索的算法应用[问题分析-宝岛探险]1234567891010234500067210345605003204560067140000000089每找到一个岛屿，个数就+1四、宽度优先搜索的算法应用[问题分析-宝岛探险]123456789101112123456789101023450006721034560500320456006714000000008913142315243325342635rear即为当前岛屿大小ijfor(inti=1;i=n;i++)for(intj=0;jm;j++){if(s[i][j]!='0'){ans++;//岛屿个数tot=1;//岛屿大小s[i][j]='0';tmp.x=i;tmp.y=j;q.push(tmp);bfs();if(totimax)imax=tot;}}voidbfs(){while(!q.empty()){for(inti=0;i4;i++){tmp.x=q.front().x+dx[i];tmp.y=q.front().y+dy[i];if(tmp.x=1&&tmp.x=n&&tmp.y=0&&tmp.ym&&s[tmp.x][tmp.y]!='0'){q.push(tmp);s[tmp.x][tmp.y]='0';tot++;}}q.