《第九讲 搜索之BFSppt课件.ppt》由会员分享,可在线阅读,更多相关《第九讲 搜索之BFSppt课件.ppt(38页珍藏版)》请在三一办公上搜索。
1、搜索之BFS,广度优先搜索,广度优先搜索,基本思想:从初始状态S开始,利用规则,生成所有可能的状态。构成树的下一层节点,检查是否出现目标状态G,若未出现,就对该层所有状态节点,分别顺序利用规则。生成再下一层的所有状态节点,对这一层的所有状态节点检查是否出现G,若未出现,继续按上面思想生成再下一层的所有状态节点,这样一层一层往下展开。直到出现目标状态为止。,BFS算法,(1)把起始节点S线放到OPEN表中(2)如果OPEN是空表,则失败退出,否则继续。(3)在OPEN表中取最前面的节点node移到CLOSED 表中。(4)扩展node节点。若没有后继(即叶节点),则转向(2)循环。(5)把nod
2、e的所有后继节点放在OPEN表的末端。各后继结点指针指向node节点。(6)若后继节点中某一个是目标节点,则找到一个解,成功退出。否则转向(2)循环。,BFS 广度优先搜索,BFS在访问了起始顶点 A 之后, 由 A 出发, 依次访问 A 的各个未被访问过的邻接顶点 B, D, C, 然后再顺序访问 B, D, , C 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发,再访问它们的所有还未被访问过的邻接顶点, 如此做下去,直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点。,A,C,D,E,G,B,F,I,H,1,2,3,4,5,6,7,8,9
3、,BFS的代码分析,void BFS()queue q;/队列q.push(st);/初始点入队列while(!q.empty()/队列中还有要处理的点从队列中取出下一个处理的点p;for(p的所有邻接点)if(该邻接点满足搜索条件)q.push(邻接点);标记该邻接点为已访问;,BFS 广度优先搜索过程,A,C,D,E,G,B,F,I,H,1,2,3,4,5,6,7,8,9,F,E,D,C,A,B,G,H,I,队列变化情况,指针,箭头表示当前访问节点,搜索完成,BFS的另一种应用,假设图的每条边的权值都是1,因为BFS是分层进行的,所以,从起点到达同一层点的路经距离应该是相同的,如果在图中标
4、记一个起点和一个终点,从起点出发,用BFS逐层向终点靠近,那么当到达终点时,会形成一条路径,那么这条路径必定是这两点的最短路经。,A,C,D,E,G,B,F,I,H,1,2,3,4,5,6,7,8,9,BFS求最短路径,struct nodeint x,y,d;void BFS()queue q;/队列node st=sx,sy,0;q.push(st);/初始点入队列while(!q.empty()/队列中还有要处理的点从队列中取出下一个处理的点p;for(p的所有邻接点)if(该邻接点满足搜索条件)邻接点.d=p.d+1;if(该邻接点是目标点)return p.d+1;q.push(邻接
5、点);标记该邻接点为已访问;,BFS与队列,STL中队列基本用法:头文件:#include基本函数:建立队列:queue 队列名;向队列中(末尾)添加元素:队列名.push(元素名);去掉队列头元素:队列名.pop();队列头元素:队列名.front();返回队尾元素的引用:队列名.back();判断是否为空:队列名.empty(); 队列大小:队列名.size();,Find The Multiple http:/,题意:给出一个整数n,(1 = n = 200)。求出任意一个它的倍数m,要求m必须只由十进制的0或1组成。 Sample Input 2 6 19 0 Sample Outpu
6、t 10 100100100100100100 111111111111111111,思路:化为bfs求最短路径问题,关键有几点: 1.懂得用模拟除法运算的过程去做。 2.余数为 m (1n-1) 的情况若出现多次,则第一次出现时所构造路径肯定比后面的情况短,根据鸽巢原理,对余数重复出现的情况进行剪枝,否则会Memory Limit Exceeded,队列的长度只限制在Max = 200。 3.构造答案的输出过程有点费心思,现在为止没想到什么好方法,只能构造出一颗二叉树,找到最后的目标节点后,再递归到根部进行输出。,这等同于构造一颗二叉树,然后按层次去遍历这颗树;,1,10,11,100,10
7、1,110,111,#includeusing namespace std; int n; long long q9999999; int main() while(scanf(%d, ,void BFS() int front,rear; front=rear=0; qrear=1; rear+; long long top; while(rearfront) top = qfront; if( top%n=0 ) break; top *= 10; qrear+=top; qrear+=top+1; front+; printf(%lldn,top); ,Prime Path http:/
8、,题意:从一个四位素数到另一个四位素数,每次变换一个数字,变换之后仍为素数,最少的步骤。比如:1033 8179变换过程:1033173337333739377987798179最少步骤一共是6步。,Sample Input 3 1033 8179 1373 8017 1033 1033 Sample Output 6 7 0,从起始素数开始进行广搜,每轮将所有可行的改变(个位至千位,每个位置进行一次改变)放入搜寻队列一次进行素数判断。 用数组来记载转变路径,每个结点指向其父结点。达到纲标之后向上寻找到先人,即可求出转变了多少次 。,STL:queue,#include 定义一个queue的变
9、量 queue M查看是否为空队列 M.empty() 是的话返回1,不是返回0;从已有元素后面增加元素 M.push()输出现有元素的个数 M.size()显示第一个元素 M.front()显示最后一个元素 M.back()清除第一个元素 M.pop(),#include#include#includeusingnamespacestd;inta,b;intp9999=0;intvisited9999=0;boolisprime(intx)for(inti=2;i=sqrt(double)x);+i)if(x%i=0)returnfalse;returntrue; ,intBFS(ints,
10、intr)queueq;q.push(s);ps=0;visiteds=1;while(!q.empty()inttemp=q.front();q.pop();for(inti=0;i=9;i+)inty1=(temp/10)*10+i;if(isprime(y1) ,inty3=temp%100+(temp/1000)*1000+100*i;if(isprime(y3),intmain()intn; scanf (%d,例1 Knight Moves,国际象棋棋盘上有一个马,要从起点跳到指定目标,最少跳几步?,输入:a1 h8输出:To get from a1 to h8 takes 6 k
11、night moves.,跳马规则,a b c d e f g h,12345678,在23的矩形里:,例如:从a1到e4,当目标出现在所扩展出的结点里,结果就找到了。,To get from a1 to e4 takes 3 knight moves.,bool in(int a,int b)if(a0,#include #include using namespace std;struct xxxint x,y;Xxx dir8=-2,1,-2,-1,-1,-2,1,-2,2,-1,2,1,1,2,-1,2;char c6;int a6;queue qq;bool mp99;int ans
12、;,int main()register int i,j;while(gets(c)while(!qq.empty()qq.pop();for(i=0;i=8;i+)for(j=0;j=8;j+)mpij=false;a0=c0-a+1;/ start cola1=c1-0;/start rowa2=c3-a+1;/end cola3=c4-0;/end rowans=0;qq.push(a0);qq.push(a1);qq.push(ans);mpa1a0=true;ans=bfs();coutTo get from c0c1 to c3c4 takes ans knight moves.e
13、ndl;return 0;,双向BFS,从起点、终点同时开始,双向BFS,有效地提高了时空效率。,从起点找2步能跳到的点,从终点找1步能跳到的点,例2 Divisibility,输入N、K,然后输入N个整数,N个整数可列出若干加减运算式;若存在一个算式,它的值能被K整除,输出“Divisible”,否则输出“Not divisible”.,输入:24 717 5 -21 154 517 5 -21 15,输出:Divisible Not divisible,17,5,-21,15,17,5,5,-21,-21,-21,-21,15,15,15,15,15,15,15,15,+,+,+,17 +
14、 5 + -21 + 15,+,+,+,+,-,-,-,-,-,-,-,17 - 5 + -21 - 15,最坏情况N=10000,二叉树有10000层,结点总数210000-1。不可能枚举所有表达式,本题的目标:判断叶子结点上是否有值能被k 整除=判断是否有值,除以k的余数为零。 计算中间值取余,不影响结果。 (a + b) % k = ( a % k + b % k) % k,因此只需记录对k的余数。2=k=100,每层结点最多100个,不是指数级增加。,4 717 5 -21 15,每层最多7个结点 (定义数组):,首先加入起点,17 % 7 = 3,扩展第2层结点(3+5) % 7 =
15、 1(3 5 + 7) % 7 =5,+,-,扩展第3层结点(1+ -21) % 7 = 1(1 -21) % 7 = 1(5+ -21) % 7 = 5(5 -21) % 7 = 5,扩展第4层结点(1+ 15) % 7 = 2(1 15) % 7 = 0(5 + 15) % 7 = 6(5 15) % 7 = 4,例3 Holedox Moving,一条长度为L“贪吃蛇”在n*m的迷宫中,求它走到出口(1,1)的最少步数。 (2L 8;1n,m 20),输入:5 6 44 14 23 23 132 33 33 40 0 0,输出:Case 1: 9,蛇头在上、下、左、右四方向上的探索过程注意:蛇不能出界,不能撞自己,不能撞石头。,例4:Eight,八数码游戏,八数码问题的广度优先搜索,分析:所给输入为初始状态,终态是1 2 3 4 5 6 7 8 x。将x当作9,开一个数组a9!,存每种状态采取双向BFS,前后搜同时进行。初始时每种状态标记为0. 在数组a里查找从前边搜到的状态,标记是0, 则置标记为1;标记是-1,则说明这是个前后搜重合状态,同时说明input有解。 在数组a里查找从后边搜到的状态,标记是0,则置为-1;标记是1,则也说明这是个前后搜重合状态,同时说明input有解。,本课程结束,谢谢欣赏,大家多做题,