第九讲-搜索之BFS

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

搜索之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的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发,再访问它们的所有还未被访问过的邻接顶点,…如此做下去,直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点。ACDEGBFIH123456789BFS的代码分析voidBFS(){queuepointq;//队列q.push(st);//初始点入队列while(!q.empty())//队列中还有要处理的点{从队列中取出下一个处理的点p;for(p的所有邻接点)if(该邻接点满足搜索条件){q.push(邻接点);标记该邻接点为已访问;}}}BFS广度优先搜索过程ACDEGBFIH123456789FEDCABGHI队列变化情况指针箭头表示当前访问节点搜索完成BFS的另一种应用假设图的每条边的权值都是1,因为BFS是分层进行的,所以,从起点到达同一层点的路经距离应该是相同的,如果在图中标记一个起点和一个终点,从起点出发,用BFS逐层向终点靠近,那么当到达终点时,会形成一条路径,那么这条路径必定是这两点的最短路经。ACDEGBFIH123456789BFS求最短路径structnode{intx,y,d;};voidBFS(){queuenodeq;//队列nodest={sx,sy,0};q.push(st);//初始点入队列while(!q.empty())//队列中还有要处理的点{从队列中取出下一个处理的点p;for(p的所有邻接点)if(该邻接点满足搜索条件){邻接点.d=p.d+1;if(该邻接点是目标点)returnp.d+1;q.push(邻接点);标记该邻接点为已访问;}}}BFS与队列•STL中队列基本用法:•头文件:•#includequeue•基本函数:•建立队列:queue元素类型队列名;•向队列中(末尾)添加元素:队列名.push(元素名);•去掉队列头元素:队列名.pop();•队列头元素:队列名.front();•返回队尾元素的引用:队列名.back();•判断是否为空:队列名.empty();•队列大小:队列名.size();FindTheMultiple=1426•题意:给出一个整数n,(1=n=200)。求出任意一个它的倍数m,要求m必须只由十进制的'0'或'1'组成。•SampleInput26190•SampleOutput10100100100100100100111111111111111111思路:化为bfs求最短路径问题,关键有几点:1.懂得用模拟除法运算的过程去做。2.余数为m(1~n-1)的情况若出现多次,则第一次出现时所构造路径肯定比后面的情况短,根据鸽巢原理,对余数重复出现的情况进行剪枝,否则会MemoryLimitExceeded,队列的长度只限制在Max=200。3.构造答案的输出过程有点费心思,现在为止没想到什么好方法,只能构造出一颗二叉树,找到最后的目标节点后,再递归到根部进行输出。•这等同于构造一颗二叉树,然后按层次去遍历这颗树;11011100101110111………#includeiostreamusingnamespacestd;intn;longlongq[9999999];intmain(){while(scanf(%d,&n)&&n){BFS();}return0;}voidBFS(){intfront,rear;front=rear=0;q[rear]=1;rear++;longlongtop;while(rearfront){top=q[front];if(top%n==0){break;}top*=10;q[rear++]=top;q[rear++]=top+1;front++;}printf(%lld\n,top);}PrimePath=3126题意:从一个四位素数到另一个四位素数,每次变换一个数字,变换之后仍为素数,最少的步骤。比如:10338179变换过程:1033173337333739377987798179最少步骤一共是6步。•SampleInput3103381791373801710331033•SampleOutput670•从起始素数开始进行广搜,每轮将所有可行的改变(个位至千位,每个位置进行一次改变)放入搜寻队列一次进行素数判断。•用数组来记载转变路径,每个结点指向其父结点。达到纲标之后向上寻找到先人,即可求出转变了多少次。STL:queue•#includequeue•定义一个queue的变量queueTypeM查看是否为空队列M.empty()是的话返回1,不是返回0;从已有元素后面增加元素M.push()输出现有元素的个数M.size()显示第一个元素M.front()显示最后一个元素M.back()清除第一个元素M.pop()#includeiostream#includequeue#includemath.husingnamespacestd;inta,b;intp[9999]={0};intvisited[9999]={0};boolisprime(intx){for(inti=2;i=sqrt((double)x);++i){if(x%i==0)returnfalse;}returntrue;}intBFS(ints,intr){queueintq;q.push(s);p[s]=0;visited[s]=1;while(!q.empty()){inttemp=q.front();q.pop();for(inti=0;i=9;i++){inty1=(temp/10)*10+i;if(isprime(y1)&&!visited[y1]){q.push(y1);p[y1]=p[temp]+1;visited[y1]=1;}inty2=temp%10+(temp/100)*100+i*10;if(isprime(y2)&&!visited[y2]){q.push(y2);p[y2]=p[temp]+1;visited[y2]=1;}inty3=temp%100+(temp/1000)*1000+100*i;if(isprime(y3)&&!visited[y3]){q.push(y3);p[y3]=p[temp]+1;visited[y3]=1;}if(i!=0){inty4=temp%1000+i*1000;if(isprime(y4)&&!visited[y4]){q.push(y4);p[y4]=p[temp]+1;visited[y4]=1;}}if(visited[r])returnp[r];}}return0;}intmain(){intn;scanf(%d,&n);while(n--){memset(visited,0,sizeof(visited));memset(p,0,sizeof(p));scanf(%d%d,&a,&b);printf(%d\n,BFS(a,b));}return0;}例1KnightMoves•国际象棋棋盘上有一个马,要从起点跳到指定目标,最少跳几步?输入:a1h8输出:Togetfroma1toh8takes6knightmoves.abcdefgh12345678h8a1跳马规则abcdefgh12345678在2×3的矩形里:•例如:从a1到e4当目标出现在所扩展出的结点里,结果就找到了。Togetfroma1toe4takes3knightmoves.abcdefgh1234567803321322312332233323333333233332boolin(inta,intb){if(a0&&a=8&&b0&&b=8)returntrue;returnfalse;}intbfs(){intcol,row,i;while(!qq.empty()){col=qq.front();qq.pop();row=qq.front();qq.pop();ans=qq.front();qq.pop();if(col==a[2]&&row==a[3])returnans;for(i=0;i8;i++){if(in(row+dir[i].x,col+dir[i].y)&&!mp[row+dir[i].x][col+dir[i].y]){qq.push(col+dir[i].y);qq.push(row+dir[i].x);qq.push(ans+1);mp[row+dir[i].x][col+dir[i].y]=true;}}}}#includeiostream#includequeueusingnamespacestd;structxxx{intx,y;};Xxxdir[8]={{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2}};charc[6];inta[6];queueintqq;boolmp[9][9];intans;intmain(){registerinti,j;while(gets(c)){while(!qq.empty())qq.pop();for(i=0;i=8;i++)for(j=0;j=8;j++)mp[i][j]=false;a[0]=c[0]-'a'+1;//startcola[1]=c[1]-'0';//startrowa[2]=c[3]-'a'+1;//endcola[3]=c[4]-'0';//endrowans=0;qq.push(a[0]);qq.push(a[1]);qq.push(ans);mp[a[1]][a[0]]=true;ans=bfs();coutTogetfromc[0]c[1]toc[3]c[4]takesansknightmoves.endl;}return0;}双向BFSabcdefgh123456780212212122211112012•从起点、终点同时开始双向BFS,有效地提高了时空效率。从起点找2步能跳到的点从终点找1步能跳到的点例2Divisibility•输入N、K,然后输入N个整数,N个整数可列出若干加减运算式;若存在一个算式,它的值能被K整除,输出“Divisible”,否则输出“Notdivisible”.输入:247175-211545175-2115输出:DivisibleNotdivisible•{17,5,-21,15}1755-21-21-21-211515151515151515+++17+5+-21+15++++-------17-5+-21-15•最坏情况N=10000,

1 / 38
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功