7. 广度优先搜索

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,/48,第七讲,搜索专题,广度优先（,BFS,）,ACM,算法与程序设计,数学科学学院：汪小平,广度优先搜索算法,（,Breadth-First-Search,）,也被作,宽度优先搜索,，或,横向优先搜索,，简称,BFS,。,BFS,是从,根节点,开始，沿着树的宽度遍历树的,节点,。如果所有节点均被访问，则算法中止。（,稳扎稳打，步步推进,）,广度优先搜索的,实现一般采用队列,。,所有因为展开节点而得到的子节点都会被加进一个,先进先出,的队列中,。,因为所有节点都必须被储存，因此,BFS,的空间复杂度为,O(|V|,，其中,|V|,是节点的数目。,另一种说法称,BFS,的空间复杂度为,O,(,BM,),，其中,B,是最大分支系数，而,M,是树的最长路径长度。由于对空间的大量需求，因此,BFS,并不适合解非常大的问题,。,最差情形下，,BFS,必须寻找所有到可能节点的所有路径，因此其时间复杂度为,O(|V|+|E|),，其中,|V|,是节点的数目，而,|E|,是图中边的数目。,以,德国,城市为范例的地图，,城市间有数条道路相连接。,从,法兰克福,开始执行广度优先搜索算法，所产生的广度优先搜索算法树。,1,、首先将根节点放入队列中。,2,、从队列中取出第一个节点，并检验它是否为目标。,如果找到目标，则结束搜寻并回传结果。,否则将它所有尚未检验过的直接子节点加入队列中。,3,、若队列为空，表示整张图都检查过了,亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。,4,、重复步骤,2,。,算法：,void BFS(VLink G,int v),int w;,VISIT(v);/*,访问顶点,v*/,visitedv=1;/*,顶点,v,对应的访问标记置为,1*/,ADDQ(Q,v);,while(!QMPTYQ(Q),v=DELQ(Q);/*,退出队头元素,v*/,w=FIRSTADJ(G,v);/*,求,v,的第,1,个邻接点。无邻接点则返回,-1*/,while(w,!=-1),if(visitedw,=0)/*,未检验过*,/,VISIT(w,);/*,访问顶点,v*/,ADDQ(Q,w,);/*,当前被访问的顶点,w,进队*,/,visitedw,=1;/*,顶点,w,对应的访问标记置为,1*/,W=,NEXTADJ(G,v,);/*,求,v,的下一个邻接点。若无邻接点则返回,-1*/,进一步说明,以迷宫作为引入。可怜的小老鼠被困在了迷宫里面想要逃出去，但是它不知道到底该怎么走，无论如何还是先选定一个方向走一下再说。,我们对各个方向设定一个优先级，比如我们设定先向上走，再向右走，然后是向下，向左。这个顺序是顺时针排的。不难相到，通过设定一个优先级，我们可以保证在行进过程不会因为随机选择而出现重复情况。,深度优先搜索的思路是找到一条可能的路就一直那么走下去只到走不通为止。这个走不通可能的情况很多，也许是遇到了自然的障碍物，也就是到了死胡同走不下去了，这个时侯只有倒退回去。,但是现实总是充满了陷阱。或许就存在这么一种路，当你辛辛苦苦走了几十步甚至上百步之后才发现那是一个没有未来的选择。我们可以在迷宫中给老鼠设定，上帝也可以在人生里为我们设定。,我们发现固执的小老鼠就是那样子走下去了没有回头。该怎么办才能防止这种情况的发生呢？,对，我们可以叫住他！,“,喂，那条路不能走了，快回来！,”,实现起来其实很简单，就是在程序里面加一个深度判断，如果深度达到了一个上界，我们就不继续往下走了，也就是跳出返回。其实这里面要涉及的还有很多，比如迭代加深搜索，,A*,等。,其实我们可以让那只老鼠变得聪明一点的。假如我们的主角不是一只小老鼠，而是一大群，如果你是老鼠王，你会怎么安排让你的子民们尽快逃生？,Thinking,。,很简单，让老鼠们分头行动。我们给每一只老鼠都配一个对讲机。从出发点开始分成四个小队，四个小队分别分别负责四个方向，一起出发。每次只能选择没有去过的地方走，没有去过既包括自己没有去过也要包括别的老鼠没有去过，这个我们可以用一个布尔数组在去过的地方标记一下，对于小老鼠来说标记的方式可能会比较特殊。每次到一个位置都可能会有几种不同的走法，那好，我们把当前的这个小队再次划分，每个能走的方向都派一个小小队去。如果没有路可走了，就呆在那儿了。当有一队老鼠或者是一只找到了出口，这位英雄就在对讲机里大吼一声，,“,哈哈，我找到出口啦，大家到这里来,”,。,相信大家听问题的时候都注意到了关键词,“,尽快,”,。毋庸置疑，老鼠们的做法是肯定能在最快时间内找到出口。接下来我们分析一下其中原因。我们给老鼠能到的每个方块一个距离。初始位置的距离为,0,，由这个位置出发能到的距离为,1,，再有这些点能到的不重复的点的距离为,2,。如此下去，我们就可以给每一个可以到达的位置一个距离值。我们每次所做的都是把一个位置能够拓展的所有位置都拓展出来了，而且也没有走重复的路。可以保证在到达某一个位置的时候我们所走的距离肯定是最短的。,这就是宽度优先搜索。,恭喜老鼠们成功获救！可是现在的问题我们如何在程序里面实现？,BFS,的关键：队列,我们要模拟出小老鼠找路的过程就必须把每一个时刻每一队小老鼠所到的位置记录下来。对于我们来说，只有在知道当前老鼠的位置的前提下，我们才能产生下一时间的决策。而为了达到上面所说的拓展最短，我们就必须根据各个位置被到达的先后顺序来拓展。这就要用到队列。,我们把每一个到的位置叫做一个状态。象这样子来构造一个队列。最初队列里只有一个元素，那就是最初的状态。机器开始运行了。第一次我们从队列里面取出第一个元素。然后对它进行拓展，找到所有由它为基础能到的状态，然后我们把这些状态加入到队列里面。这样的操作不断重复，直到我们找到了我们想要的为止。当然操作不止这么简单。,我们还必须对过去已经到过的进行标记,。,另外，我们可以通过在状态之中添加一些信息而实现更多的东西，比如路径保存，方向记录等。,这样我们就可以实现,BFS,了。参考结构见下,(,伪代码,),Q0,QNum=1,;/,初始队列元素设定，,QNum,用于存储队列元素个数,I=0,;/,指针指向队列首位,While(I,QNum,),/,拓展,QI,；,QNum,可能会变化,I+,；,/,指针后移,以,德国,城市为范例的地图，,城市间有数条道路相连接。,从,法兰克福,开始执行广度优先搜索算法，所产生的广度优先搜索算法树。,1,、首先将根节点放入队列中。,2,、从队列中取出第一个节点，并检验它是否为目标。,如果找到目标，则结束搜寻并回传结果。,否则将它所有尚未检验过的直接子节点加入队列中。,3,、若队列为空，表示整张图都检查过了,亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。,4,、重复步骤,2,。,算法：,void BFS(VLink G,int v),int w;,VISIT(v);/*,访问顶点,v*/,visitedv=1;/*,顶点,v,对应的访问标记置为,1*/,ADDQ(Q,v);,while(!QMPTYQ(Q),v=DELQ(Q);/*,退出队头元素,v*/,w=FIRSTADJ(G,v);/*,求,v,的第,1,个邻接点。无邻接点则返回,-1*/,while(w,!=-1),if(visitedw,=0)/*,未检验过*,/,VISIT(w,);/*,访问顶点,v*/,ADDQ(Q,w,);/*,当前被访问的顶点,w,进队*,/,visitedw,=1;/*,顶点,w,对应的访问标记置为,1*/,W=,NEXTADJ(G,v,);/*,求,v,的下一个邻接点。若无邻接点则返回,-1*/,总结,BFS,的思路就是第,N,步就把,N,步所能达到的所有状态都找出来。当然这样子是有代价的，那就是可能需要比,DFS,多很多的空间。不过,BFS,的优势在于它,能够很快的找到最优解,。,BFS,和,DFS,一样都是很暴力的算法，因为它们都属于盲目搜索算法。,Find The Multiple,http:/,poj.org/problem?id,=1426,Description,Given a positive integer n,write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1.You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.,Input,The input file may contain multiple test cases.Each line contains a value of n(1=n=200).A line containing a zero terminates the input.,Output,For each value of n in the input print a line containing the corresponding value of m.The decimal representation of m must not contain more than 100 digits.If there are multiple solutions for a given value of n,any one of them is acceptable.,Sample Input,2,6,19,0,Sample Output,10,100100100100100100,111111111111111111,这等同于构造一颗二叉树，然后按层次去遍历这颗树；,1,10,11,100,101,110,111,#include,using namespace std;,int,n;,long long q9999999;,int,main(),while(scanf(%d,&n)&n,),BFS();,return 0;,void BFS(),int,front,rear,;,front=rear=0;,qrear,=1;,rear+;,long long top;,while(rear,front),top=,qfront,;,if(,top%n,=0),break;,top*=10;,qrear,+=top;,qrear,+=top+1;,front+;,printf(%lldn,top,);,Prime Path,http:/,poj.org/problem?id,=3126,Description,The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.,It is a matter of security to change such things every now and then,to keep the enemy in the dark.,But look,I have chosen my number 1033 for good reasons.I am the Prime minister,you know!,I know,so therefore your new number 8179 is also a prime.You will just have to p