《广度优先搜索》PPT课件.ppt_第1页
《广度优先搜索》PPT课件.ppt_第2页
《广度优先搜索》PPT课件.ppt_第3页
《广度优先搜索》PPT课件.ppt_第4页
《广度优先搜索》PPT课件.ppt_第5页
已阅读5页,还剩21页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第八章 广度优先搜索,广度优先搜索的过程,广度优先搜索算法(又称宽度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。 广度优先算法的核心思想是:从初始节点开始,应用算符生成第一层节点,检查目标节点是否在这些后继节点中,若没有,再用产生式规则将所有第一层的节点逐一扩展,得到第二层节点,并逐一检查第二层节点中是否包含目标节点。若没有,再用算符逐一扩展第二层的所有节点,如此依次扩展,检查下去,直到发现目标节点为止。即 从图中的某一顶点V0开始,先访问V0; 访问所有与V0相邻接的顶点V1,V2,Vt; 依次访问与V1,V2,Vt相邻接的所有未曾访问过的顶点; 循此以往,直至所有的顶点都被访问过为止。 这种搜索的次序体现沿层次向横向扩展的趋势,所以称之为广度优先搜索。,广度优先搜索算法描述:,int Bfs() 初始化,初始状态存入队列; 队列首指针head=0; 尾指针tail=1; do 指针head后移一位,指向待扩展结点; for (int i=1;i=max;+i) /max为产生子结点的规则数 if (子结点符合条件) tail指针增1,把新结点存入列尾; if (新结点与原已产生结点重复) 删去该结点(取消入队,tail减1); else if (新结点是目标结点) 输出并退出; while(headtail); /队列为空 ,广度优先搜索注意事项:,1、每生成一个子结点,就要提供指向它们父亲结点的指针。当解出现时候,通过逆向跟踪,找到从根结点到目标结点的一条路径。当然不要求输出路径,就没必要记父亲。 2、生成的结点要与前面所有已经产生结点比较,以免出现重复结点,浪费时间和空间,还有可能陷入死循环。 3、如果目标结点的深度与“费用”(如:路径长度)成正比,那么,找到的第一个解即为最优解,这时,搜索速度比深度搜索要快些,在求最优解时往往采用广度优先搜索;如果结点的“费用”不与深度成正比时,第一次找到的解不一定是最优解。 4、广度优先搜索的效率还有赖于目标结点所在位置情况,如果目标结点深度处于较深层时,需搜索的结点数基本上以指数增长。,下面我们看看怎样用宽度优先搜索来解决八数码问题。 例如 图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态,每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出,扩展第个结点,总共生成个结点之后,才求得这个解。此外,直接观察此图表明,不存在有更短走步序列的解。,【例1】图4表示的是从城市A到城市H的交通图。从图中可以看出,从城市A到城市H要经过若干个城市。现要找出一条经过城市最少的一条路线。,【算法分析】 看到这图很容易想到用邻接距阵来表示,0表示能走,1表示不能走。如图。,首先想到的是用队列的思想。a数组是存储扩展结点的队列,ai记录经过的城市,bi记录前趋城市,这样就可以倒推出最短线路。具体过程如下: (1) 将城市A入队,队首为0、队尾为1。 (2)将队首所指的城市所有可直通的城市入队(如果这个城市在队列中出现过就不入队,可用一布尔数组si来判断),将入队城市的前趋城市保存在bi中。然后将队首加1,得到新的队首城市。重复以上步骤,直到搜到城市H时,搜索结束。利用bi可倒推出最少城市线路。,【参考程序】 #include #include using namespace std; int ju99=0,0,0,0,0,0,0,0,0, 0,1,0,0,0,1,0,1,1, 0,0,1,1,1,1,0,1,1, 0,0,1,1,0,0,1,1,1, 0,0,1,0,1,1,1,0,1, 0,1,1,0,1,1,1,0,0, 0,0,0,1,1,1,1,1,0, 0,1,1,1,0,0,1,1,0, 0,1,1,1,1,0,0,0,1; int a101,b101; bool s9; /初始化 int out(int d) /输出过程 coutchar(ad+64); while (bd) d=bd; cout“-“char(ad+64); coutendl; ,void doit() int head,tail,i; head=0;tail=1; /队首为0、队尾为1 a1=1; /记录经过的城市 b1=0; /记录前趋城市 s1=1; /表示该城市已经到过 do /步骤2 head+; /队首加一,出队 for (i=1;i=8;i+) /搜索可直通的城市 if (juaheadi=0) ,【例2】一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如: 阵列 4 10 0234500067 1034560500 2045600671 0000000089 有4个细胞。 【算法分析】 从文件中读入m*n矩阵阵列,将其转换为boolean矩阵存入bz数组中; 沿bz数组矩阵从上到下,从左到右,找到遇到的第一个细胞; 将细胞的位置入队h,并沿其上、下、左、右四个方向上的细胞位置入队,入队后的位置bz数组置为flase; 将h队的队头出队,沿其上、下、左、右四个方向上的细胞位置入队,入队后的位置bz数组置为flase; 重复4,直至h队空为止,则此时找出了一个细胞; 重复2,直至矩阵找不到细胞; 输出找到的细胞数。,【参考程序】 #include using namespace std; int dx4=-1,0,1,0, dy4=0,1,0,-1; int bz100100,num=0,n,m; void doit(int p,int q) int x,y,t,w,i; int h100010; num+;bzpq=0; t=0;w=1;h11=p;h12=q; /遇到的第一个细胞入队 do t+; /队头指针加1 for (i=0;i=0) /直至队空为止 ,int main() int i,j; char s100,ch; scanf(“%d%dn“, ,【例3】最短路径(1995年高中组第4 题) 如下图所示,从入口(1)到出口(17)的可行路线图中,数字标号表示关卡。,现将上面的路线图,按记录结构存储如下图6:,请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。,【算法分析】 该题是一个路径搜索问题,根据图示,从入口(1)到出口(17)可能有多条途径,其中最短的路径只有一条,那么如何找最短路径呢?根据题意,用数组NO存储各关卡号,用数组PRE存储访问到某关卡号的前趋关卡号。其实本题是一个典型的图的遍历问题,我们可以采用图的广度优先遍历,并利用队列的方式存储顶点之间的联系。从入口(1)开始先把它入队,然后把(1)的所有关联顶点都入队,即访问一个顶点,将其后继顶点入队,并存储它的前趋顶点,直到访问到出口(17)。最后,再从出口的关卡号(17)开始回访它的前趋关卡号,直到入口的关卡号(1),则回访的搜索路径便是最短路径。从列表中可以看出出口关卡号(17)的被访问路径最短的是: (17) (16)(19)(18)(1) 由此,我们得到广度优先遍历求最短路径的基本方法如下: 假设用邻接矩阵存放路线图(aIj=1表示I与j连通,aIj=0表示I与j不连通)。 再设一个队列和一个表示拓展到哪个顶点的指针变量pos。 (1)从入口开始,先把(1)入队,并且根据邻接矩阵,把(1)的后继顶点全部入队,并存储这些后继顶点的前趋顶点为(1);再把pos后移一个,继续拓展它,将其后继顶点入队,并存储它们的前趋顶点,直到拓展到出口(目的地(17);,注意后继顶点入队前,必须要检查这个顶点是否已在队列中,如果已经在了就不要入队了;这一步可称为图的遍历或拓展; (2)从队列的最后一个关卡号(出口(17)开始,依次回访它的前驱顶点,倒推所得到的路径即为最短路径。主要是依据每个顶点的前趋顶点倒推得到的。实现如下: i=1 ; WHILE (NOI!=17) +i ; DO cout“(“noi“)“; cout“ “; i=prei ; while ( I!=0); 【参考程序】留给同学们完成,文件名ex8_3.cpp。,【例4】迷宫问题 如下图所示,给出一个N*M的迷宫图和一个入口、一个出口。 编一个程序,打印一条从迷宫入口到出口的路径。这里黑色方块的单元表示走不通(用-1表示),白色方块的单元表示可以走(用0表示)。只能往上、下、左、右四个方向走。如果无路则输出“no way.”。,【算法分析】 只要输出一条路径即可,所以是一个经典的回溯算法问题,本例给出了回溯(深搜)程序和广搜程序。实现见参考程序。,【深搜参考程序】 #include using namespace std; int n,m,desx,desy,soux,souy,totstep,a51,b51,map5151; bool f; int move(int x, int y,int step) mapxy=step; /走一步,作标记,把步数记下来 astep=x; bstep=y; /记路径 if (x=desx) /往上 ,int main() int i,j; cinnm; /n行m列的迷宫 for (i=1;imapij; coutsouxsouy; /入口 coutdesxdesy; /出口 f=0; /f=0表示无解;f=1表示找到了一个解 move(soux,souy,1); if (f) for (i=1;i=totstep;i+) /输出直迷宫的路径 coutai“,“biendl; else cout“no way.“endl; return 0; ,【广搜参考程序】 #include using namespace std; int u5=0,0,1,0,-1, w5=0,1,0,-1,0; int n,m,i,j,desx,desy,soux,souy,head,tail,x,y,a51,b51,pre51,map5151; bool f; int print(int d) if (pred!=0) print (pred); /递归输出路径 coutnm; /n行m列的迷宫 for (i=1;imapij; coutsouxsouy; /入口 coutdesxdesy; /出口 head=0; tail=1;,f=0; mapsouxsouy=-1; atail=soux; btail=souy; pretail=0; while (head!=tail) /队列不为空 head+; for (i=1;i0) ,【上机练习】,1、编程计算由“*”号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示,在10*10的二维数组中,有“*”围住了15个点,因此面积为15。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 * * * 0 0 0 0 0 0 0 * 0 0 * 0 0 0 0 0 0 0 * 0 0 * 0 0 0 * 0 0 0 * 0 * 0 0 * 0 * 0 * 0 0 * 0 0 * 0 0 * * 0 * * 0 0 0 * 0 0 0 0 * 0 0 0 0 0 * * * * * 0 0 0 0 0 0 0 0 0 0 0 0,【样例输入】area.in 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0,【样例输出】area.out 15,2、细胞(cell) 【问题描述】 一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如阵列: 0234500067 1034560500 2045600671 0000000089 有4个细胞。 【输入格式】 整数m,n(m行,n列)矩阵 【输出格式】 细胞的个数。 【输入样例】cell.in 4 10 0234500067 1034560500 2045600671 0000000089 【输出样例】cell.out 4,3、营救 【问题描述】 铁塔尼号遇险了!他发出了求救信号。距离最近的哥伦比亚号收到了讯息,时间就是生命,必须尽快赶到那里。 通过侦测,哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成n*n个比较小的单位,其中用1标明的是陆地,用0标明是海洋。船只能从一个格子,移到相邻的四个格子。 为了尽快赶到出事地点,哥伦比亚号最少需要走多远的距离。 【输入格式】 第一行为n,下面是一个n*n的0、1矩阵,表示海洋地图 最后一行为四个小于n的整数,分别表示哥伦比亚号和铁塔尼号的位置。 【输出格式】 哥伦比亚号到铁塔尼号的最短距离,答案精确到整数。 【输入样例】save.in 3 001 101 100 1 1 3 3 【数据范围】 N=1000,【输出样例】save.out 4,4、最少转弯问题(TURN) 【问题描述】 给出一张地图,这张地图被分为nm(n,m=100)个方块,任何一个

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论