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

迷宫

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

A perfect maze
-------
-@@@@@-
-----@-
-@@@-@-
-@---@-

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

针对这个输入,会提供一个 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 方法检查栈顶元素是否是终点)。

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

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

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

BFS 模型概念图

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 - 迷宫

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

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

DFS - 迷宫 - 左

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

DFS - 迷宫 - 左回溯

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

DFS - 迷宫 - 回溯

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

![DFS - 迷宫 - 下

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

DFS - 迷宫 - 下左

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

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不需要存储所有走过的路线,它只需要找到一条正确的路线即可


  1. from Stanford CS106 ↩︎

  2. 搜索思想 ——DFS & BFS( 基础基础篇) - Linkcheng ↩︎