《广度优先搜索》ppt课件

《《广度优先搜索》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九讲搜索专题广度优先（BFS）ACM算法与程序设计广度优先搜索算法（Breadth-First-Search）也被作宽度优先搜索，或横向优先搜索，简称BFS。BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用队列。所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。因为所有节点都必须被储存，因此BFS的空间复杂度为O(

2、V

3、+

4、E

5、)，其中

6、V

7、是节点的数目，而

8、E

9、是图中边的数目。另一种说法称BFS的空间复杂度为O(BM)，其中B是最大分支系数，而M

10、是树的最长路径长度。由于对空间的大量需求，因此BFS并不适合解非常大的问题。最差情形下，BFS必须寻找所有到可能节点的所有路径，因此其时间复杂度为O(

11、V

12、+

13、E

14、)，其中

15、V

16、是节点的数目，而

17、E

18、是图中边的数目。还是以迷宫作为引入。可怜的小老鼠被困在了迷宫里面想要逃出去，但是它不知道到底该怎么走，无论如何还是先选定一个方向走一下再说。我们对各个方向设定一个优先级，比如我们设定先向上走，再向右走，然后是向下，向左。这个顺序是顺时针排的。不难相当，通过设定一个优先级，我们可以保证在行进过程不会因为随机选择而出现重复情况。

19、深度优先搜索的思路是找到一条可能的路就一直那么走下去只到走不通为止。这个走不通可能的情况很多，也许是遇到了自然的障碍物，也就是到了死胡同走不下去了，这个时侯只有倒退回去。但是现实总是充满了陷阱。或许就存在这么一种路，当你辛辛苦苦走了几十步甚至上百步之后才发现那是一个没有未来的选择。我们可以在迷宫中给老鼠设定，上帝也可以在人生里为我们设定。我们发现固执的小老鼠就是那样子走下去了没有回头。该怎么办才能防止这种情况的发生呢？对，我们可以叫住他！“喂，那条路不能走了，快回来！”实现起来其实很简单，就是在程序里面加一个深度判断，如

20、果深度达到了一个上界，我们就不继续往下走了，也就是跳出返回。其实这里面要涉及的还有很多，比如迭代加深搜索，A*等。其实我们可以让那只老鼠变得聪明一点的。假如我们的主角不是一只小老鼠，而是一大群，如果你是老鼠王，你会怎么安排让你的子民们尽快逃生？Thinking。。。很简单，让老鼠们分头行动。我们给每一只老鼠都配一个对讲机。从出发点开始分成四个小队，四个小队分别分别负责四个方向，一起出发。每次只能选择没有去过的地方走，没有去过既包括自己没有去过也要包括别的老鼠没有去过，这个我们可以用一个布尔数组在去过的地方标记一下，对于小

21、老鼠来说标记的方式可能会比较特殊。每次到一个位置都可能会有几种不同的走法，那好，我们把当前的这个小队再次划分，每个能走的方向都派一个小小队去。如果没有路可走了，就呆在那儿了。当有一队老鼠或者是一只找到了出口，这位英雄就在对讲机里大吼一声，“哈哈，我找到出口啦，大家到这里来”。相信大家听问题的时候都注意到了关键词“尽快”。毋庸置疑，老鼠们的做法是肯定能在最快时间内找到出口。接下来我们分析一下其中原因。我们给老鼠能到的每个方块一个距离。初始位置的距离为0，由这个位置出发能到的距离为1，再有这些点能到的不重复的点的距离为2。。

22、。如此下去，我们就可以给每一个可以到达的位置一个距离值。我们每次所做的都是把一个位置能够拓展的所有位置都拓展出来了，而且也没有走重复的路。可以保证在到达某一个位置的时候我们所走的距离肯定是最短的。这就是宽度优先搜索。恭喜老鼠们成功获救！可是现在的问题我们如何在程序里面实现？BFS的关键：队列我们要模拟出小老鼠找路的过程就必须把每一个时刻每一队小老鼠所到的位置记录下来。对于我们来说，只有在知道当前老鼠的位置的前提下，我们才能产生下一时间的决策。而为了达到上面所说的拓展最短，我们就必须根据各个位置被到达的先后顺序来拓展。这就

23、要用到队列。我们把每一个到的位置叫做一个状态。象这样子来构造一个队列。最初队列里只有一个元素，那就是最初的状态。机器开始运行了。第一次我们从队列里面取出第一个元素。然后对它进行拓展，找到所有由它为基础能到的状态，然后我们把这些状态加入到队列里面。这样的操作不断重复，直到我们找到了我们想要的为止。当然操作不止这么简单。我们还必须对过去已经到过的进行标记。另外，我们可以通过在状态之中添加一些信息而实现更多的东西，比如路径保存，方向记录等。这样我们就可以实现BFS了。参考结构见下(伪代码)Q[0],QNum=1;//初始队列元

24、素设定，QNum用于存储队列元素个数I=0;//指针指向队列首位While(I