11-广度优先搜索

2.2.4　广度优先搜索

或许大家会注意到，用深度优先遍历找到的迷宫路径似乎有点儿不尽如人意，通常它们不是最短路径。广度优先搜索（breadth-first search，BFS）则总是会查找最短路径，它从起始状态开始由近到远，在搜索时的每次迭代中依次查找每一层节点。针对某些问题，深度优先搜索可能会比广度优先搜索更快找到解，反之亦然。因此，要在两者之间进行选择，有时就是在可能快速求解与确定找到最短路径（如果存在）之间做出权衡。图2-5演示了迷宫中正在进行的广度优先搜索。

深度优先搜索有时会比广度优先搜索更快地返回结果，要想理解其中的原因，不妨想象一下在洋葱的一层皮上寻找标记。采用深度优先策略的搜索者可以把小刀插入洋葱的中心并随意检查切出的块。如果标记所在的层刚好邻近切出的块，那么就有可能比采用广度优先策略的搜索者更快地找到它，广度优先策略的搜索者会费劲地每次“剥一层洋葱皮”。

为了更好地理解为什么广度优先搜索始终都会找出最短路径（如果存在的话），可以考虑一下要找到波士顿和纽约之间停靠车站数最少的火车路径。如果不断朝同一个方向前进并在遇到死路时进行回溯（如同深度优先搜索），就有可能在回到纽约之前先找到一条通往西雅图的路线。但在广度优先搜索时，首先会检查距离波士顿1站路的所有车站，然后检查距离波士顿2站路的所有车站，再检查距离波士顿3站路的所有车站，一直持续至找到纽约为止。因此在找到纽约时，就能知道已找到了车站数最少的路线，因为离波士顿较近的所有车站都已经查看过了，且其中没有纽约。

1．队列

实现BFS需要用到名为队列（queue）的数据结构。栈是LIFO，而队列是FIFO（先进先出）。队列就像是排队使用洗手间的一队人。第一个进入队列的人可以先进入洗手间。队列至少具有与栈类似的 push() 方法和 pop() 方法。实际上， Queue 的实现（底层由Python的 deque 支持）几乎与 Stack 的实现完全相同，只有一点儿变化，即从 _container 的左端而不是右端移除元素，并用 deque 替换了 list 。这里用“左”来代表底层存储结构的起始位置。左端的元素是在 deque 中停留时间最长的元素（依到达时间而定），所以它们是首先弹出的元素。具体代码如代码清单2-22所示。

代码清单2-22　generic_search.py（续）

class Queue(Generic[T]):
    def __init__(self) -> None:
         self._container: Deque[T] = Deque()
    @property
    def empty(self) -> bool:
        return not self._container  # not is true for empty container
    def push(self, item: T) -> None:
        self._container.append(item)
    def pop(self) -> T:
        return self._container.popleft()  # FIFO
    def __repr__(self) -> str:
        return repr(self._container)

提示 　为什么 Queue 的实现要用 deque 作为其底层存储结构，而 Stack 的实现则使用 list 作为其底层存储结构呢？这与弹出数据的位置有关。在栈中，是右侧压入右侧弹出。在队列中，也是右侧压入，但是从左侧弹出。Python的 list 数据结构从右侧弹出的效率较高，但从左侧弹出则不然。 deque 则从两侧都能够高效地弹出数据。因此，在 deque 上有一个名为 popleft() 的内置方法，但在 list 上则没有与其等效的方法。当然可以找到其他方法来用 list 作为队列的底层存储结构，但效率会比较低。在 deque 上从左侧弹出数据的操作复杂度为O(1)，而在 list 上则为O(n)。在用 list 的时候，从左侧弹出数据后，每个后续元素都必须向左移动一个位置，效率也就降低了。

2．BFS算法

广度优先搜索的算法与深度优先搜索的算法惊人地一致，只是 frontier 由栈变成了队列。把 frontier 由栈改为队列会改变对状态进行搜索的顺序，并确保离起点状态最近的状态最先被搜索到。具体代码如代码清单2-23所示。

代码清单2-23　generic_search.py（续）

def bfs(initial: T, goal_test: Callable[[T], bool], successors: Callable[[T], List[T]]) 
 -> Optional[Node[T]]:
    # frontier is where we've yet to go
    frontier: Queue[Node[T]] = Queue()
    frontier.push(Node(initial, None))
    # explored is where we've been
    explored: Set[T] = {initial}
    # keep going while there is more to explore
    while not frontier.empty:
        current_node: Node[T] = frontier.pop()
        current_state: T = current_node.state
        # if we found the goal, we're done
        if goal_test(current_state):
            return current_node
        # check where we can go next and haven't explored
        for child in successors(current_state):
            if child in explored:  # skip children we already explored
                continue
            explored.add(child)
            frontier.push(Node(child, current_node))
    return None  # went through everything and never found goal

运行一下 bfs() ，就会看到它总会找到当前迷宫的最短路径。在 if __name__ == "__main__" 部分中，在之前的测试代码后面加入代码清单2-24所示的语句，以便能对同一个迷宫对比两种算法的结果。

代码清单2-24　maze.py（续）

# Test BFS
solution2: Optional[Node[MazeLocation]] = bfs(m.start, m.goal_test, m.successors)
if solution2 is None:
    print("No solution found using breadth-first search!")
else:
    path2: List[MazeLocation] = node_to_path(solution2)
    m.mark(path2)
    print(m)
    m.clear(path2)

令人惊讶的是，算法可以保持不变，只需修改其访问的数据结构即可得到完全不同的结果。以下是在之前名为 dfs() 的同一个迷宫上调用 bfs() 的结果。请注意，用星号标记出来的从起点到目标点的路径比上一个示例中的路径更为直接。

S    X X
*X
*      X
*XX      X
* X
* X  X
*X
*
*     X   X
*********G