BFS & DFS 迷宫

上一篇“一文弄懂递归”中，埋了一个使用递归来找到迷宫的解的坑。这篇文章记录一下如何使用 BFS 和 DFS 来找到迷宫的解。

迷宫

这篇文章主要是针对一种被称为“完美迷宫”的特殊迷宫类型。一个完美迷宫是一个没有环路和不可进入的区域，起点和终点都由一条路径连接的迷宫。
下图显示了一个完美的迷宫，以及从左上角的入口到右下角的出口的路径:

-------
[e-mail]@@@@-
[e-mail]
[e-mail]@@[e-mail]
[e-mail]@-

你会接收到这样的一个输入，其中-代表通路，@代表墙。

针对这个输入，会提供一个 readMazeFile() 方法来读取数据，它会把数据读成一个二维向量，为了方便，我们这里用 grid 简称。其中每一个元素可以用 grid[row][col] 来进行访问。如果是通路，那么就会返回 true， 如果是思路就会返回 false。

接下来，这篇文章将讲解如何使用 BFS（ 广度优先搜索） 与 DFS（ 深度优先搜索） 来让计算机找到这个迷宫的解。

BFS 广度优先搜索

特征与要求

特征：
- Nearly exhaustive search
- 如果在当前长度没有搜索到采取搜索下一层：如搜索了所有的两步内的结果，没有找到，采取寻找第三步

需要的数据结构：

A data structure to represent (partial word) ladders

• 我们需要一个能够记录我们走了什么路径的数据结构 —— Stack

A data structure to store all the partial word ladders that we have generated so far and have yet to explore

• 我们需要记录我们还要探索哪些路径 —— Queue

A data structure to keep track of all the words that we've explored so far, so that we avoid getting stuck in loops

• 我们需要有一个能够记录我们已经走了哪些位置的数据结构 ——Set

有了如上的数据结构，我们可以看一下如何使用它们

例子

假设我们要走如下这个迷宫，我们的起点是左下角，并且我们只能向上或者向右走。

首先，在探索可以走的点（邻近）之前，我们先要把起始点存入 set， 这样可以保证日后我们生成邻近时不会又回到某个点，从而生成循环。

然后，针对这个起始点我们需要创建一个栈。在这里使用栈是因为它的 LIFO 的结构，这可以帮助我们快速确定我们是否已经到达终点（我们只需要使用 peek 方法检查栈顶元素是否是终点）。

由于我们要不断地探索不同路径，所以我们需要有一个数据结构能够存储我们需要探索的路径，然后我们只需要不断地检查这个数据结构的所有内容，判断是不是有一条能走向终点的路径即可。

这个数据结构就是队列。而我们则需要把我们的栈加入队列之中。

针对如上叙述，我们可以划出一个这样的图：

Queue 存储整体的需要探索的路径 ，Stack 存储已经走过的路径。除此之外，还有一个 set 存储已经走过的点。

有了这个结构，在我们把起始点压入栈之后，我们首先从队列中 dequeue 出来我们压入的那个只包含起始点的栈。然后我们可以判断得出——它并不是终点。所以，我们需要继续探索它的邻近，也就是：①向上；②向右

由于我们有两条路径，我们就把这两个方向分别存入到不同的两个栈里，然后把这两个新的栈压入队列。

由于现在队列里又有了两个栈，所以我们需要继续 dequeue， 按照以上同样的方法判断是否到达终点，没有即继续探索邻近……

将上面描述的内容抽象化我们可以总结出如下步骤：

1. 先创造一个空队列以及空集合
2. 创建一个空栈，然后将起始内容压入栈，和空集合
3. 把栈加入队列
4. 然后只要队列不为空
   • Dequeue
   • 如果栈顶内容已经是最终内容 ，return path； 如果不是执行如下
   • search 所有栈顶内容的邻近
   • 对于每一个邻近，检查是否出现，如果没出现将创建一个栈，把原有的内容，以及这个邻近点压入栈；然后将栈压入队列，并且将这个邻近点存入 set

我们可以看到，这种搜索策略非常“广”，因为针对每一个邻近，我们都会单独为它生成一个栈，然后将这个栈压入队列。下面就是 BFS 在探索迷宫时的具体实现。

实现

struct GirdLocation{
    int row;
    int col;
}

Set<GridLocation> generateValidMoves(Grid<bool>& maze, GridLocation cur) {
    Set<GridLocation> neighbors;
    if(maze.inBounds(cur.row + 1, cur.col) && maze[cur.row + 1][cur.col] == true)
        neighbors.add({cur.row + 1, cur.col});
    if(maze.inBounds(cur.row - 1, cur.col) && maze[cur.row - 1][cur.col] == true)
        neighbors.add({cur.row - 1, cur.col});
    if(maze.inBounds(cur.row, cur.col + 1) && maze[cur.row][cur.col + 1] == true)
        neighbors.add({cur.row, cur.col + 1});
    if(maze.inBounds(cur.row, cur.col - 1) && maze[cur.row][cur.col - 1] == true)
        neighbors.add({cur.row, cur.col - 1});
    return neighbors;
}

Stack<GridLocation> solveMaze(string& input) {

    Grid<bool> maze = readMaze(input);
    Queue<Stack<GridLocation>> pathCollection;
    Set<GridLocation> visitedLocation = {{0, 0}};
    GridLocation endPoint = {maze.numRows() - 1, maze.numCols() - 1};

    Stack<GridLocation> entry = {{0, 0}};
    pathCollection.enqueue(entry);

    while(!pathCollection.isEmpty()){
        Stack<GridLocation> currentPath = pathCollection.dequeue();

        if(currentPath.peek() == endPoint){
            return currentPath;
        }

        Set<GridLocation> neighbors = generateValidMoves(maze, currentPath.peek());
        for(GridLocation g : neighbors){
            if(!visitedLocation.contains(g)){
                Stack<GridLocation> auxiliary = currentPath;
                auxiliary.push(g);
                pathCollection.enqueue(auxiliary);
                visitedLocation.add(g);
            }
        }
    }

    return {};
}

DFS 深度优先搜索

特征与要求

深度优先搜索与广度优先搜索不同，它采用了一种基于递归回溯的搜索策略。如果不了解递归回溯的，可以查看一文弄懂递归。

简单来说，他采取如下这种方法：

深度优先搜索的步骤分为 1. 递归下去 2. 回溯上来。顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。

否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来。

下面结合具体例子来理解。

如图所示，在一个迷宫中，黑色块代表玩家所在位置，红色块代表终点，问是否有一条到终点的路径

我们用深度优先搜索的方法去解这道题，由图可知，我们可以走上下左右四个方向，我们规定按照左下右上的方向顺序走，即，如果左边可以走，我们先走左边。然后递归下去，没达到终点，我们再回溯上来，等又回溯到这个位置时，左边已经走过了，那么我们就走下边，按照这样的顺序与方向走。并且我们把走过的路标记一下代表走过，不能再走。

所以我们从黑色起点首先向左走，然后发现还可以向左走，最后我们到达图示位置

已经连续向左走到左上角的位置了，这时发现左边不能走了，这时我们就考虑往下走，发现也不能走，同理，上边也不能走，右边已经走过了也不能走，这时候无路可走了，代表这条路是死路不能帮我们解决问题，所以现在要回溯上去，回溯到上一个位置，

在这个位置我们由上可知走左边是死路不行，上下是墙壁不能走，而左边又是走过的路，已经被标记过了，不能走。所以只能再度回溯到上一个位置寻找别的出路。

最终我们回溯到最初的位置，同理，左边证明是死路不必走了，上和右是墙壁，所以我们走下边。然后递归下去

![DFS - 迷宫 - 下

到了这个格子，因为按照左下右上的顺序，我们走左边，递归下去

一直递归下去到最左边的格子，然后左边行不通，走下边。

然后达到目标 。[2]

实现

struct GirdLocation{
    int row;
    int col;
}

bool solveMazeHelper(Grid<bool>& maze, Stack<GridLocation& path, GridLocation cur) {
    GridLocation exitLoc = {maze.numRows() -1, maze.numCols() - 1}; 
    if (cur = exitLoc) {
        return true; 
    }

    Set<GridLocation> validNeighbors = generateValidMoves(maze, cur); 

    for (GridLocation loc : validNeighbors) {
        path.push(loc);
        maze[loc] = false;
        if (solveMazeHelper(maze, path, loc)) {
            return true;
        }
        path.pop() //如果这条路不对，那么我们则需要取消选择这条路。
        maze[loc] = true;
    }
    return false;
}
Stack<GridLocation> solveMaze(Grid<bool>& maze){
    GridLocation start = maze[0][0];
    maze[0][0] = false;
    Stack<GridLocation> path = {start};
    solveMazeHelper(maze, path, start);

    return path;
}

BFS & DFS 对比

BFS 通常是迭代的，而 DFS 是递归的。

在移动到较长的路径之前 ，BFS 会查看所有特定长度的路径，所以它保证会找到最短路径。

DFS不需要存储所有的局部路径，因此它比 BFS 占用的内存更少。

DFS 在搜索这种只有一条路径的迷宫之中，通常会比 BFS 更快，因为 DFS 不需要存储所有走过的路线，它只需要找到一条正确的路线即可

注：本文由 @Serence @半人半疯 原创发布，未经作者许可，禁止转载。本文首发于BFS & DFS in maze。

---

参考资料

1. from Stanford CS106

2. 搜索思想 ——DFS & BFS（ 基础基础篇） - Linkcheng