第九讲 搜索之BFSppt课件.ppt
搜索之BFS,广度优先搜索,广度优先搜索,基本思想：从初始状态S开始，利用规则，生成所有可能的状态。构成树的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。,BFS算法,（1）把起始节点S线放到OPEN表中（2）如果OPEN是空表，则失败退出，否则继续。（3）在OPEN表中取最前面的节点node移到CLOSED 表中。（4）扩展node节点。若没有后继（即叶节点），则转向（2）循环。（5）把node的所有后继节点放在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,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是分层进行的，所以，从起点到达同一层点的路经距离应该是相同的，如果在图中标记一个起点和一个终点，从起点出发，用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(邻接点);标记该邻接点为已访问；,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 Output 10 100100100100100100 111111111111111111,思路：化为bfs求最短路径问题，关键有几点： 1.懂得用模拟除法运算的过程去做。 2.余数为 m (1n-1) 的情况若出现多次，则第一次出现时所构造路径肯定比后面的情况短，根据鸽巢原理，对余数重复出现的情况进行剪枝，否则会Memory Limit Exceeded，队列的长度只限制在Max = 200。 3.构造答案的输出过程有点费心思，现在为止没想到什么好方法，只能构造出一颗二叉树，找到最后的目标节点后，再递归到根部进行输出。,这等同于构造一颗二叉树，然后按层次去遍历这颗树；,1,10,11,100,101,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:/,题意：从一个四位素数到另一个四位素数，每次变换一个数字，变换之后仍为素数，最少的步骤。比如：1033 8179变换过程：1033173337333739377987798179最少步骤一共是6步。,Sample Input 3 1033 8179 1373 8017 1033 1033 Sample Output 6 7 0,从起始素数开始进行广搜，每轮将所有可行的改变（个位至千位，每个位置进行一次改变）放入搜寻队列一次进行素数判断。 用数组来记载转变路径，每个结点指向其父结点。达到纲标之后向上寻找到先人，即可求出转变了多少次 。,STL：queue,#include 定义一个queue的变量 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,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 knight 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;,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.endl;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 + 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 = 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有解。,本课程结束，谢谢欣赏,大家多做题,
