9. 广度优先搜索.ppt

第九届，检索主题广度优先(BFS )，ACM算法和程序设计，2020/6/10，2012年波兰华沙大学： UESTC_Athena团队代表本校参加第四届ACM全球决赛？ 赵命令、李春骏、徐渊鸿、宽度优先搜索算法(Breadth-First-Search )也被简称为BFS作为宽度优先搜索或者横向优先搜索。 BFS是从根节点沿着树的宽度横穿树的节点。 当所有节点都被访问时，该算法将中止。 宽度优先搜索的实现一般采用队列。 通过展开节点得到的所有子节点被添加到高级先进先出队列中。 因为必须存储所有节点，所以BFS的空间复杂性是O(|V| |E|)，其中|V|是节点的数目，|E|是图中边缘的数目。 另一种说法是BFS的空间复杂度为O(BM )，b是最大分支系数，m是树的最长路径长度。 因为对空间的需求很多，所以BFS不适合解决很大的问题。 在最坏的情况下，由于BFS需要查找指向可能节点的所有路径，因此时间复杂度为O(|V| |E|)，其中|V|是节点的数量，|E|是图边的数量。 还是引入迷宫。 可怜的老鼠被困在迷宫里试图逃脱，但不知道该去哪里。 总之先定好方向再说。 我们会在各个方向设定优先级。 例如，先向上，然后向右，再向下，再向左。 这个顺序是顺时针方向。 并不难，但通过设置优先级，可以确保进行中随机选择不会重复。 深度优先探索的想法，一旦找到可能的道路，就无法走到那里。 这个死胡同多，是遇到自然障碍，还是死胡同，这个时候只能倒退。 但是现实总是充满陷阱。 可能有这样的路。 你辛苦地走了几十步，然后走了几百步，才发现这是一个没有未来的选择。 我们可以在迷宫中设定老鼠，神可以在人生中为我们设定。 我们发现顽固的老鼠不会那样走回来。 怎样才能防止这种情况发生呢？ 啊，我们可以叫他！ “喂，那条路走不了，快回来！ 实现是很简单的，通过对程序加以深度判断，当深度达到上边界时，我们就不会再往下走，也就是说跳回来。 其实，这还涉及很多事情。 例如，反复加深搜索，A*。 其实我们可以让那只老鼠变聪明。 如果我们的主角不是一群小老鼠，而是一群大老鼠，那么如果你是老鼠王的话，怎么能尽快让你的子民逃走呢Thinking？ 的双曲馀弦值。 的双曲馀弦值。 简单，让老鼠们分开行动。 我们给所有的老鼠都装上了对讲机。 从出发点分为四个队，四个队各负责四个方向，一起出发。 只挑一次没去过的地方去，没去过的既没有自己去过，也没有包括别的老鼠去过。 这可以用布尔数组标记在过去的地方。 对于老鼠来说标记的方法可能是特殊的。 每到一个地方，可能有几种不同的方法。 那么，再分割现在的队伍，向任何方向派遣小队。 没有路我就在那里。 一群老鼠，一找到出口，这位英雄就用对讲机大声喊道：“哈哈，找到出口了，大家都到这里来了。” 我相信大家在询问问题的时候发现了关键词“尽快”。 当然，老鼠们的做法是尽快找到出口。 接下来，我们来分析一下其原因。 我们给老鼠能做的每一块都加上距离。 初始位置的距离为0，从该位置可出发的距离为1，并且，从这些点到不重复点的距离为2。 的双曲馀弦值。 的双曲馀弦值。 以这种方式，能够为每个可达到的位置给出距离值。我们每次都在努力扩大可以扩大一个地方的所有地方。 此外，也没有重复的道路。 可以保证到达某个地方时我们行走的距离一定是最短的。 这是宽度优先搜索。 恭喜老鼠们得救了！ 但是现在的问题是如何在程序中实现的呢？ BFS的关键：行列，我们为了模拟老鼠寻路的过程，必须记录各队老鼠到达的位置。 对我们来说，只要知道鼠标当前的位置，就可以作出下一个时间的决定。 并且，为了使上述展开最短，必须按照各个位置到达的顺序展开。 这使用队列。 我们把各自的到达位置称为一种状态。 这样排队。 第一个队列只有一个元素。 那是最初的状态。 机器开始运转了。 首先从队列中检索出第一个元素。 然后将其扩展，找到所有可能的状态，并将这些状态排队。 这样的操作一直重复着，直到我们找到想要的。 当然，操作还不止这些。 你必须标记过去做过的事情。 另外，通过给状态添加信息，能够实现更多的，例如路径保存、方向记录等。 现在可以实现BFS了。 参考结构如下(伪码)、Q0、QNum=1； /初始队列元素设置，qum用于存储队列元素的数量I=0/指针位于队列顶部While(I24； h )，void get _ coauthor _ activities () intn； scanf(%d”，voidabfs()std:3360queueeq； q .推(en hash ( erds )； Q.front()-dist=0； while (！ q.empty () typedef STD :30 list :30 iterator IP； intd=Q.front()-dist 1； STD :3360列表，voiddo_query()intM； scanf(%d”， )，作业练习题：授课成绩评价标准，一，成绩构成1，平日成绩：