动画演示广度优先算法寻找最短路径

来自:Python高效编程,作者:借我一生执拗

上一节,我们刚刚介绍了使用深度优先算法(DFS)解决迷宫问题,这一节我们来介绍广度优先算法(BFS)。BFS 算法与 DFS 十分相似,唯一的区别就是 DFS 算法使用后进先出的栈来保存节点,而 BFS 算法使用先进先出的队列来存储节点,除此之外简直就是一母同胞的亲兄弟。当然,这两种方案各有千秋。DFS 算法找到的路径往往不是最短路径,速度慢但占用内存较少,而 BFS 算法找到的总是最短路径,速度较快但占用内存较多。

下图是使用 BFS 算法搜寻出来的一条路径:

使用广度优先算法搜寻迷宫路径的过程如下:从迷宫入口出发,查询下一步走得通的节点,将这些可能的节点压入队列中,已经走过的节点不再尝试。查询完毕之后,从队列中取出一个节点,查询该节点周围是否存在走得通的节点。如果不存在可能的节点,就继续从队列中取一个节点。重复以上操作,直到当前节点为迷宫出口,或者队列中再无节点。如果迷宫是走得通的话,广度优先搜索会找到一条最短路径。

总结一下,深度优先搜索会一直前进,直到走到死胡同为止,再回退到上一个节点,改变之前的选择。而广度优先搜索每次前进的时候,会把前后左右行得通的节点都尝试一遍,相当于每前进一个节点都要尝试多种可能,因此每次挑选的路径会是最短路径。

定义数据:

  • 起始节点与目标节点

  • 存储节点的队列

定义辅助函数

  • 获取下一节点的函数: successor

  • 判断是否为终点的函数: test_goal

我们把上一篇的 dfs 函数稍稍改动一下,就是我们这一次使用到的 BFS 算法。

首先来看 Queue 的定义,让 Queue 类继承我们定义的 Stack 类,重写 pop 函数,改成删除头部元素即可。

class Queue(Stack):
    def pop(self):
        return self._container.popleft()

接下来,我们来扩展上一次定义的 dfs 函数为 search 函数。新增了 container 参数,选择 ‘Queue’ 则为 BFS 算法,选择 ‘Stack’ 则为 DFS 算法,其余的定义并没有改变。

def search(initial, container = 'Queue', _next=successor, _test=test_goal):
    if container == 'Queue' or 'queue':
        s = Queue()
    elif container == 'Stack' or 'stack':
        s = Stack()
    else:
        raise NotImplemented
    marked = {initial}
    s.push(initial)
    while s:
        parent = s.pop()
        if _test(parent):
            return parent
        children = _next(parent)
        for child in children:
            if child not in marked:
                marked.add(child)
                s.push(child)

接下来,我们使用 BFS 算法寻找迷宫路径,并对搜寻到的迷宫路径进行可视化演示。

和上次的定义基本相同,唯一的变化就是将存储节点的栈改成了先进先出的队列,这里我只展示改动的部分,具体内容可以参考上一篇文章的内容。

显然改动的地方只是将 stack 换成了 queue 而已。

class BreadthFirstSearch(Maze):
    def _search(self):
        queue = Queue()
        initial = self._Node(self._start, None)
        marked = {initial.state}
        queue.push(initial)
        while queue:
            parent = queue.pop()
            state = parent.state
            if self._test_goal(state):
                return parent
            children = self._success(state)
            for child in children:
                if child not in marked:
                    marked.add(child)
                    queue.push(self._Node(child, parent))

最后再放一张效果图:

推荐↓↓↓
算法与数据结构
上一篇:你写的二分法可能有个bug 下一篇:宋仲基宋慧乔没能找到对的人,算法能帮我们找到么?