第九讲-搜索之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，