《9. 广度优先搜索》由会员分享，可在线阅读，更多相关《9. 广度优先搜索（46页珍藏版）》请在金锄头文库上搜索。
1、第九讲搜索专题广度优先（BFS）ACM算法与程序设计2/31广度优先搜索算法（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/31 还是以迷宫作为引入。可怜的小老鼠被困在了迷宫里面想 要逃出去，但是它不知道到底该怎么走，无论如何还是先 选定一个方向走一下再说。 我们对各个方向设定一个优先级，比如我们设定先向上走 ，再向右走，然后是向下，向左。这个顺序是顺时针排的 。不难相当，通过设定一个优先级，我们可以保证在行进 过程不会因为随机选择而出现重复情况。 深度优先搜索的思路是找到一条可能的路就一直那么
3、走下 去只到走不通为止。这个走不通可能的情况很多，也许是 遇到了自然的障碍物，也就是到了死胡同走不下去了，这 个时侯只有倒退回去。 但是现实总是充满了陷阱。或许就存在这么一种路，当你 辛辛苦苦走了几十步甚至上百步之后才发现那是一个没有 未来的选择。我们可以在迷宫中给老鼠设定，上帝也可以 在人生里为我们设定。 4/31 我们发现固执的小老鼠就是那样子走下去了没有 回头。该怎么办才能防止这种情况的发生呢？ 对，我们可以叫住他！“喂，那条路不能走了，快 回来！”实现起来其实很简单，就是在程序里面加 一个深度判断，如果深度达到了一个上界，我们 就不继续往下走了，也就是跳出返回。其实这里 面要涉及的还有
4、很多，比如迭代加深搜索，A*等 。 其实我们可以让那只老鼠变得聪明一点的。假如 我们的主角不是一只小老鼠，而是一大群，如果 你是老鼠王，你会怎么安排让你的子民们尽快逃 生？ Thinking。5/31 很简单，让老鼠们分头行动。我们给每一只老鼠 都配一个对讲机。从出发点开始分成四个小队， 四个小队分别分别负责四个方向，一起出发。每 次只能选择没有去过的地方走，没有去过既包括 自己没有去过也要包括别的老鼠没有去过，这个 我们可以用一个布尔数组在去过的地方标记一下 ，对于小老鼠来说标记的方式可能会比较特殊。 每次到一个位置都可能会有几种不同的走法，那 好，我们把当前的这个小队再次划分，每个能走 的
5、方向都派一个小小队去。如果没有路可走了， 就呆在那儿了。当有一队老鼠或者是一只找到了 出口，这位英雄就在对讲机里大吼一声，“哈哈， 我找到出口啦，大家到这里来”。 6/31 相信大家听问题的时候都注意到了关键词“尽快” 。毋庸置疑，老鼠们的做法是肯定能在最快时间 内找到出口。接下来我们分析一下其中原因。我 们给老鼠能到的每个方块一个距离。初始位置的 距离为0，由这个位置出发能到的距离为1，再有 这些点能到的不重复的点的距离为2。如此下 去，我们就可以给每一个可以到达的位置一个距 离值。我们每次所做的都是把一个位置能够拓展 的所有位置都拓展出来了，而且也没有走重复的 路。可以保证在到达某一个位置
6、的时候我们所走 的距离肯定是最短的。 这就是宽度优先搜索。 恭喜老鼠们成功获救！可是现在的问题我们如何 在程序里面实现？7/31BFS的关键：队列 我们要模拟出小老鼠找路的过程就必须把每一个 时刻每一队小老鼠所到的位置记录下来。对于我 们来说，只有在知道当前老鼠的位置的前提下， 我们才能产生下一时间的决策。而为了达到上面 所说的拓展最短，我们就必须根据各个位置被到 达的先后顺序来拓展。这就要用到队列。 我们把每一个到的位置叫做一个状态。象这样子 来构造一个队列。最初队列里只有一个元素，那 就是最初的状态。机器开始运行了。第一次我们 从队列里面取出第一个元素。然后对它进行拓展 ，找到所有由它为基
7、础能到的状态，然后我们把 这些状态加入到队列里面。这样的操作不断重复 ，直到我们找到了我们想要的为止。当然操作不 止这么简单。我们还必须对过去已经到过的进行 标记。 8/31 另外，我们可以通过在状态之中添加一些信息而 实现更多的东西，比如路径保存，方向记录等。 这样我们就可以实现BFS了。参考结构见下(伪代 码)Q0,QNum = 1;/初始队列元素设定，QNum用于存储队列元素个数 I = 0;/指针指向队列首位 While (I using namespace std; int n; long long q9999999; int main() while(scanf(“%d“, ret
8、urn 0; 18/31void 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); 19/31Prime Path http:/ Description The ministers of the cabinet were quite upset by the message from
9、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 kno
10、w! I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over 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 mi
11、nister you cannot stand having a non -prime number on your door even for a few seconds. Correct! So I must invent 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 20/31Now, the minister of finance, who had been eavesdrop
12、ping, intervened. No unnecessary expenditure, please! I happen to know that the price of a digit is one pound. Hmm, 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. H
13、elp the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above. 1033 1733 3733 3739 3779 8779 8179The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in st
14、ep 2 can not be reused in the last step a new 1 must be purchased. 21/31 Input One line with a positive number: the number 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
15、 for each case, either with a number stating the minimal cost or containing the word Impossible.22/31 Sample Input3 1033 8179 1373 8017 1033 1033 Sample Output6 70 23/31 首先区分the prime minister 和prime number中的 prime的不同意思。 从起始素数开始进行广搜，每轮将所有可行的改 变（个位至千位，每个位置进行一次改变）放入 搜寻队列一次进行素数判断。 用数组来记载转变路径，每个结点指向其父结点 。达到纲标之后向上寻找到先人，即可求出转变 了多少次 。24/31STL：queue #include 定义一个queue的变量 queue M 查看是否为空队列 M.empty() 是的话返回 1，不是返回0; 从已有元素后面增加元素 M.push() 输出现有元素的个数 M.size() 显示第一个元素 M.front() 显示最后一个元素 M.back() 清除第一个元素 M.pop()25/31#include #include #
