广度优先搜索.ppt
《广度优先搜索.ppt》由会员分享,可在线阅读,更多相关《广度优先搜索.ppt(46页珍藏版)》请在三一文库上搜索。
1、第九讲,搜索专题 广度优先(BFS),ACM算法与程序设计,广度优先搜索算法(Breadth -First-Search),也被作宽度优先搜索,或横向优先搜索,简称BFS。BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。 广度优先搜索的实现一般采用队列。所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。 因为所有节点都必须被储存,因此BFS的空间复杂度为 O(|V| + |E|),其中 |V| 是节点的数目,而 |E| 是图中边的数目。 另一种说法称BFS的空间复杂度为 O(BM),其中 B 是最大分支系数,而 M 是树的最长路径长度。由于对空间的
2、大量需求,因此BFS并不适合解非常大的问题。 最差情形下,BFS必须寻找所有到可能节点的所有路径,因此其时间复杂度为 O(|V| + |E|),其中 |V| 是节点的数目,而 |E| 是图中边的数目。,还是以迷宫作为引入。可怜的小老鼠被困在了迷宫里面想要逃出去,但是它不知道到底该怎么走,无论如何还是先选定一个方向走一下再说。 我们对各个方向设定一个优先级,比如我们设定先向上走,再向右走,然后是向下,向左。这个顺序是顺时针排的。不难相当,通过设定一个优先级,我们可以保证在行进过程不会因为随机选择而出现重复情况。 深度优先搜索的思路是找到一条可能的路就一直那么走下去只到走不通为止。这个走不通可能的
3、情况很多,也许是遇到了自然的障碍物,也就是到了死胡同走不下去了,这个时侯只有倒退回去。 但是现实总是充满了陷阱。或许就存在这么一种路,当你辛辛苦苦走了几十步甚至上百步之后才发现那是一个没有未来的选择。我们可以在迷宫中给老鼠设定,上帝也可以在人生里为我们设定。,我们发现固执的小老鼠就是那样子走下去了没有回头。该怎么办才能防止这种情况的发生呢? 对,我们可以叫住他!“喂,那条路不能走了,快回来!”实现起来其实很简单,就是在程序里面加一个深度判断,如果深度达到了一个上界,我们就不继续往下走了,也就是跳出返回。其实这里面要涉及的还有很多,比如迭代加深搜索,A*等。 其实我们可以让那只老鼠变得聪明一点的
4、。假如我们的主角不是一只小老鼠,而是一大群,如果你是老鼠王,你会怎么安排让你的子民们尽快逃生? Thinking。,很简单,让老鼠们分头行动。我们给每一只老鼠都配一个对讲机。从出发点开始分成四个小队,四个小队分别分别负责四个方向,一起出发。每次只能选择没有去过的地方走,没有去过既包括自己没有去过也要包括别的老鼠没有去过,这个我们可以用一个布尔数组在去过的地方标记一下,对于小老鼠来说标记的方式可能会比较特殊。每次到一个位置都可能会有几种不同的走法,那好,我们把当前的这个小队再次划分,每个能走的方向都派一个小小队去。如果没有路可走了,就呆在那儿了。当有一队老鼠或者是一只找到了出口,这位英雄就在对讲
5、机里大吼一声,“哈哈,我找到出口啦,大家到这里来”。,相信大家听问题的时候都注意到了关键词“尽快”。毋庸置疑,老鼠们的做法是肯定能在最快时间内找到出口。接下来我们分析一下其中原因。我们给老鼠能到的每个方块一个距离。初始位置的距离为0,由这个位置出发能到的距离为1,再有这些点能到的不重复的点的距离为2。如此下去,我们就可以给每一个可以到达的位置一个距离值。我们每次所做的都是把一个位置能够拓展的所有位置都拓展出来了,而且也没有走重复的路。可以保证在到达某一个位置的时候我们所走的距离肯定是最短的。 这就是宽度优先搜索。 恭喜老鼠们成功获救!可是现在的问题我们如何在程序里面实现?,BFS的关键:队列,
6、我们要模拟出小老鼠找路的过程就必须把每一个时刻每一队小老鼠所到的位置记录下来。对于我们来说,只有在知道当前老鼠的位置的前提下,我们才能产生下一时间的决策。而为了达到上面所说的拓展最短,我们就必须根据各个位置被到达的先后顺序来拓展。这就要用到队列。 我们把每一个到的位置叫做一个状态。象这样子来构造一个队列。最初队列里只有一个元素,那就是最初的状态。机器开始运行了。第一次我们从队列里面取出第一个元素。然后对它进行拓展,找到所有由它为基础能到的状态,然后我们把这些状态加入到队列里面。这样的操作不断重复,直到我们找到了我们想要的为止。当然操作不止这么简单。我们还必须对过去已经到过的进行标记。,另外,我
7、们可以通过在状态之中添加一些信息而实现更多的东西,比如路径保存,方向记录等。 这样我们就可以实现BFS了。参考结构见下(伪代码),Q0,QNum = 1;/初始队列元素设定,QNum用于存储队列元素个数 I = 0;/指针指向队列首位 While (I QNum) /拓展QI;QNum可能会变化 I+;/指针后移 ,以德国城市为范例的地图, 城市间有数条道路相连接。,从法兰克福开始执行广度优先搜索算法,所产生的广度优先搜索算法树。,1、首先将根节点放入队列中。 2、从队列中取出第一个节点,并检验它是否为目标。 如果找到目标,则结束搜寻并回传结果。 否则将它所有尚未检验过的直接子节点加入队列中。
8、 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,
9、w); /*当前被访问的顶点w进队*/ visitedw = 1; /*顶点w对应的访问标记置为1*/ W = NEXTADJ(G,v); /*求v的下一个邻接点。若无邻接点则返回-1*/ ,总结BFS的思路就是第N步就把N步所能达到的所有状态都找出来。当然这样子是有代价的,那就是可能需要比DFS多很多的空间。不过BFS的优势在于它能够很快的找到最优解。BFS和DFS一样都是很暴力的算法,因为它们都属于盲目搜索算法。,Find The Multiple http:/ Given a positive integer n, write a program to find out a nonzer
10、o 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
11、). 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
12、.,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“, ,void BFS() int front,rear; front=rear=0; qrear=1; rear+; long long top; while(rearfro
13、nt) top = qfront; if( top%n=0 ) break; top *= 10; qrear+=top; qrear+=top+1; front+; printf(“%lldn“,top); ,Prime Path http:/ 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.
14、 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 paste four new digits over
15、 the four old ones on your office door. No, its not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime! I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds. Correct! So I must inve
16、nt a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime,Now, the minister of finance, who had been eavesdropping, intervened. No unnecessary expenditure, please! I happen to know that the price of a digit is one pound. Hmm,
17、in that case I need a computer program to minimize the cost. You dont know some very cheap software gurus, do you? In fact, I do. You see, there is this programming contest going on. Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must
18、 be nonzero, of course. Here is a solution in the case above. 1033 1733 3733 3739 3779 8779 8179,The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step a new 1 must be purchased.,Input One line with a positive number: the numbe
19、r of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros). Output One line for each case, either with a number stating the minimal cost or containing the word Impossible.,Sample Input 3 1033 8179
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 广度 优先 搜索
链接地址:https://www.31doc.com/p-2533818.html