动画演示广度优先算法寻找最短路径
动画演示广度优先算法寻找最短路径
上一节，我们刚刚介绍了使用深度优先算法(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))
最后再放一张效果图：
腾讯云开发者
