[算法]搜索初步: 从迷宫最短路问题来理解DFS和BFS

[Locietta]

搜索初步: DFS和BFS

第一篇算法，从最基础的搜索开始。

所谓搜索算法，也就是从某个状态出发，按照一定顺序遍历所有能到达的状态来解决问题的办法。一般来说，按照搜索顺序的不同，主要分为深度优先搜索(DFS) 和 广度优先搜索(BFS) 两种手段。

这里我们用一个经典的搜索问题：迷宫最短路问题 来看看这两种搜索方式具体是什么，又有什么异同。

题目描述：

给定一个由n*n的二维数组表示的迷宫，其中只包含0和1，0表示可以走的路，1表示不可通过的墙壁。
最初，有一个人位于左上角(0, 0)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，此人从左上角移动至右下角(n-1,n-1)处，至少需要移动多少次？

输入格式：

第一行包含一个整数n，代表迷宫的大小为n*n

接下来的n行，每行包含n个整数（0或1）表示完整的迷宫

输出格式：

若有可行的通道则输出一个整数，代表求出的通道的最短步长；若没有通道则输出"No solution"

输入与输出样例：

输入1：

5
0 0 1 1 0
0 1 0 0 1
0 0 0 1 0
1 0 0 0 1
0 0 1 0 0

输出1：

8

输入2：

5
0 1 0 1 0
0 0 1 0 1
1 0 0 0 1
1 0 1 0 1
0 1 0 1 0

输出2：

No solution

输入3：

9
0 0 1 0 1 0 0 0 1
1 0 0 0 1 0 1 0 1
0 0 1 0 1 0 1 0 1
1 0 1 0 0 0 1 0 1
1 0 1 1 1 1 0 0 1
1 0 1 0 1 0 0 1 1
0 0 0 1 0 0 0 0 1
0 1 0 0 1 1 0 1 0
1 1 0 1 0 0 0 0 0

输出3：

24

深度优先DFS

什么是DFS？

所谓的深度优先指的是从某个状态开始，不断地转移到下一个状态，直到不能继续转移为止，这时候返回前一步，转移到其他的状态，直到到达解状态。

emmm有亿点抽象，那...具体在这个迷宫问题上来看呢？

在迷宫问题上翻译一下深度优先的定义的话：就是说从某个格子出发，不断地往四周的格子走，如果考虑不走回头路的话，那么总会出现不能继续走的情况。这时候，退回到上一步，在上一步走其他的路，如果上一步没有其他的路可走了就再退回到上一步......不断重复这个过程，直到走到终点为止。

这就很直观了，就像一个人通过试错法来走迷宫的过程：先一路走到死路，然后回到前一步选另一条路，不断地试错，这样就遍历了所有能走的路。事实上也就是一种回溯法。

画成搜索树的话就是这样👇

这个搜索过程对应LIFO的栈结构：不断push新的状态入栈，不能继续时，pop出最后push的状态，push另一个状态。而众所周知，所有的栈操作和递归函数是等价的，所以DFS通常用递归来实现。

DFS的代码实现

先来看看DFS解迷宫问题的C++代码（顺便也练习了一下面向对象和STL）：

#include <iostream>
#include <stack>
#include <cstdio>
#include <string>

using namespace std;

class Walker : public stack<pair<int, int>> {
private:
    const int n_;
    int map[50][50] = {};
    const pair<int, int> start_, end_;

    inline void next(const pair<int, int> &pos) {
        const auto &cur = this->top();
        map[cur.first][cur.second] = -1;
        this->push(pos);
        dfs();
        this->pop();
        map[cur.first][cur.second] = 0;
    }

public:
    int length = INT_MAX, count = 0;
    Walker(const int &n, pair<int, int> &&start, pair<int, int> &&end)
        : n_(n), start_(start), end_(end) { // 读取地图
        for (int i = 0; i < n_; ++i) {
            for (int j = 0; j < n_; ++j) {
                cin >> map[i][j];
            }
        }
        this->push(start);
    }
    bool reach() const { return this->top() == end_; }

    void dfs();
};

int main() {
    int n;
    while (cin >> n) {
        Walker w(n, pair(0, 0), pair(n - 1, n - 1));
        w.dfs();
        w.count ? printf("%d\n", w.length) : puts("No solution");
        // w.count ? printf("%d %d\n", w.length, w.count) : puts("No solution");
    }
}

void Walker::dfs() {
    if (this->reach()) {
        count++;
        if (int temp = this->size() - 1; temp < length) length = temp;
        return;
    }
    auto pos = this->top();
    int i = pos.first, j = pos.second;
    if (i && !map[i - 1][j]) next(pair(i - 1, j)); // left
    if (j && !map[i][j - 1]) next(pair(i, j - 1)); // up
    if (i < n_ - 1 && !map[i + 1][j]) next(pair(i + 1, j)); // right
    if (j < n_ - 1 && !map[i][j + 1]) next(pair(i, j + 1)); // down
}

Walker类完成了所有的操作，利用pair来保存状态（也就是走到的位置）。为了简明，它直接继承自STL的stack，其中构造函数完成读取的操作，dfs()实现DFS，next()是DFS状态转移的精髓。

所有的DFS都有类似next()的代码：状态转移→递归调用→状态还原。只要掌握了这个，所有的DFS就都会写了。

当然栈和面向对象语言都是不必要的（这里主要是我想练习一下刚学的C++（逃）），我们来看C语言的版本：

#include <stdio.h>
int map[50][50], n, count, length;
void dfs(const int step, int i, int j) {
    if (i == n - 1 && j == n - 1) {
        count++;
        if (step < length) length = step;
        return;
    }
    map[i][j] = 1;
    if (i && !map[i - 1][j]) dfs(step + 1, i - 1, j); // left
    if (j && !map[i][j - 1]) dfs(step + 1, i, j - 1); // up
    if (i < n - 1 && !map[i + 1][j]) dfs(step + 1, i + 1, j); // right 
    if (j < n - 1 && !map[i][j + 1]) dfs(step + 1, i, j + 1); // down
    map[i][j] = 0;
}
int main(void) {
    while (scanf("%d", &n) != EOF) {
        count = 0, length = __INT_MAX__;
        for (int i = 0; i < n; ++i) { // read
            for (int j = 0; j < n; ++j) {
                scanf("%d", &map[i][j]);
            }
        }
        dfs(0,0,0);
        count ? printf("%d\n", length) : puts("No solution");
    }
    return 0;
}

仅28行，单纯依靠dfs()递归来实现，注意下面的这段代码👇

    /* 状态转移 */
    map[i][j] = 1; 
    /* 递归调用 */
    if (i && !map[i - 1][j]) dfs(step + 1, i - 1, j);
    if (j && !map[i][j - 1]) dfs(step + 1, i, j - 1);
    if (i < n - 1 && !map[i + 1][j]) dfs(step + 1, i + 1, j);
    if (j < n - 1 && !map[i][j + 1]) dfs(step + 1, i, j + 1);
    /* 状态还原 */
    map[i][j] = 0;

是很经典的状态转移→递归调用→状态还原模式。

严格来讲，我这里由于采用了离开的时候才标记的策略，把状态修改给延后了。
如果按照到达时就标记的策略，应该把状态修改塞到每个if分支里。

也就是每个if分支都该是一个完整的状态转移→递归调用→状态还原过程

看，是不是很容易~

广度优先BFS

什么是BFS？

BFS和DFS很类似，区别只在于搜索的顺序不同：BFS总是先搜索距离初始状态近的状态。

也就是说，它是按照 开始状态→1次转移可以到达的所有状态→2次转移可以到达的所有状态→…… 这样的顺序进行搜索。

在迷宫的例子里，就是说我们按照走1步能到达的位置，走2步能到达的位置...这样的顺序逐一搜索，直到不再有能到达的位置。

想象我们拿着地图，画出一系列的“等高线”，先标距离为1的，再标距离为2的，直到地图上的每一个位置都被标上了要到达所需的步数。

画成搜索树的话就是这样👇

这个搜索过程对应 FIFO 的队列结构：enqueue加入一层的状态，再dequeue丢出最先加入的那一层状态。当然由于BFS依赖于“步数”的概念，所以有时也可以考虑直接利用循环来实现。

BFS的代码实现

BFS的C++代码（夹杂了各种私货，主要是为了练习新学的C++，不过应该还是清楚的（大概））

#include <iostream>
#include <deque>
#include <tuple>
#include <cstdio>
#include <string>

using namespace std;

class Walker : public deque<tuple<int, int, int>> {
private:
    const int n_;
    int map[50][50] = {};
    const pair<int, int> start_, end_;

public:
    int step = 0;
    Walker(const int &n, pair<int, int> &&start, pair<int, int> &&end)
        : n_(n), start_(start), end_(end) {
        for (int i = 0; i < n_; ++i) {
            for (int j = 0; j < n_; ++j) {
                cin >> map[i][j];
            }
        }
        this->push_back(tuple(start.first, start.second, 0));
    }

    void next();
    bool reach() const { return map[end_.first][end_.second] == -1; };
};

int main() {
    int n;
    while (cin >> n) {
        Walker w(n, pair(0, 0), pair(n - 1, n - 1));
        while (!w.reach()) {
            try {
                w.next();
            } catch (const char *err) {
                cout << err << endl;
                break;
            }
        }
        if (w.reach()) cout << w.step << endl;
    }
}

void Walker::next() {
    if (!size()) throw "No solution";

    for (auto &&position = front(); get<2>(position) == step;) {
        int i = get<0>(position), j = get<1>(position);
        if (i && !map[i - 1][j]) { // left
            push_back(tuple(i - 1, j, step + 1));
            map[i - 1][j] = -1; // this position has been visited
        }
        if (j && !map[i][j - 1]) { // up
            push_back(tuple(i, j - 1, step + 1));
            map[i][j - 1] = -1;
        }
        if (i < n_ - 1 && !map[i + 1][j]) { // right
            push_back(tuple(i + 1, j, step + 1));
            map[i + 1][j] = -1;
        }
        if (j < n_ - 1 && !map[i][j + 1]) { // down
            push_back(tuple(i, j + 1, step + 1));
            map[i][j + 1] = -1;
        }
        pop_front();
        if (size()) {
            position = front();
        } else {
            throw "No solution";
        }
    }
    step++;
}

因为BFS对应于队列操作，所以让Walker类继承自deque,同样重载构造函数用于读入数据，利用tuple<i,j,step>来保存状态。next()函数将下一步的所有可能加入队列，并将上一步的状态移除，并维护一个step变量用于指示现在是第几步。当发现能到达终点时，输出步数。

当然实际上我们仔细思考的话，“地图”和状态完全可以二合一，我们可以把状态信息（这里也就是步数）直接标在地图上，这样一来就可以不用队列来实现这个迷宫BFS.

按照这样的思路，我们可以写出相应的C代码：

#include <stdio.h>
int map[50][50];
int main(void) {
    int n, temp;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; ++i) { // read
            for (int j = 0; j < n; ++j) {
                scanf("%d", &temp);
                map[i][j] = -temp;
            }
        }
        int step = 0;
        if (!map[0][1]) map[0][1] = 1;
        if (!map[1][0]) map[1][0] = 1;
        for (step = 1; map[n - 1][n - 1] <= 0; ++step) {
            int flag = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (map[i][j] != step) continue;
                    if (i && !map[i - 1][j] && (flag = 1)) map[i - 1][j] = step + 1;
                    if (j && !map[i][j - 1] && (flag = 1)) map[i][j - 1] = step + 1;
                    if (i < n - 1 && !map[i + 1][j] && (flag = 1)) map[i + 1][j] = step + 1;
                    if (j < n - 1 && !map[i][j + 1] && (flag = 1)) map[i][j + 1] = step + 1;
                }
            }
            if (!flag) break;
        }
        (map[n - 1][n - 1]) ? printf("%d\n", map[n - 1][n - 1]) : puts("No solution");
    }
}

用了一些技巧把代码压到了30行，思路还是比较简单的。按照步数step循环，最终判断有没有到达过终点。简单的用循环实现了BFS。

不过要注意的是这里因为去除了队列的关系，我们没有保存上一步的所有状态，所以只能每次遍历整个地图寻找标号恰为step的位置，这一操作增加了复杂度。

[Locietta]

DFS和BFS的比较

DFS的范式：

void dfs(int deep) { // 搜索深度/状态变量作为参数
	if (符合某种要求||已经不能在搜了) { // 终止
		做一些操作；
		return;
	}
	if (符合某种条件且有地方可以继续搜索的) { //这里可能会有多种条件，可能要循环或者多写几个if什么的
		a[x][y]='x';// 状态转移
	    dfs(deep+1,sum+1);// 递归调用，搜索下一层
		a[x][y]='.';// 状态还原
	}
}

BFS的范式：

int visit[N][N] //用来记录走过的位置
int dir[4][2]={0,-1,0,1,-1,0,1,0};
using status = tuple<int,int,int>; //一般是点，还有步数，也可以存其他的
queue<status> v;
void bfs(status p) {
	status t,tt;
	v.push(p);
	while (!v.empty()) {
		t=v.front(); //取出最前面的
		v.pop(); //删除
		if(找到符合条件的) {
			做记录；
			while(!v.empty()) v.pop(); //如果后面还需要用，随手清空队列
			return;
		}
		visit[t.x][t.y]=1; //走过的进行标记，以免重复
		rep(i,0,4) { //做多次查找
			tt=t;
			tt.x+=dir[i][0];tt.y+=dir[i][1]; //这里的例子是向上下左右查找的
			if(如果这个位置符合条件) {
				tt.bits++; //步数加一
				v.push(tt); //把它推入队列，在后面的时候就可以用了
			}
		}
	}
}

1. BFS适合用来求解最短路径问题，例如求最少步数的解，最少交换次数的解，最快走出迷宫等等。因为BFS搜索过程中遇到的第一个解一定是离初状态最近的，所以一旦遇到一个解，一定就是最优解，此时搜索可以停止。而如果用DFS，搜索到的解不能保证是最优解，要想找到最优解只有搜索全部情况一一比对，需要消耗较多的时间。

2. DFS应用更广泛，如果要搜索全部的解并且给出具体路径，那么DFS更优。 因为DFS记录路径信息更加方便，BFS若是想记录路径信息的话只能将路径作为状态保存，这就会带来很大的空间开销（反正BFS记录路径我是没有想到什么好办法啦）。而且DFS在很多情况下更加易用，因为大部分时候我们只要求得一个解就行，并不一定要是最优解。而回溯思想的DFS和需要考虑这一步所有可能位置下一步可能演化的BFS相比，更符合大多数人的思维习惯，所以比较容易写。

3. BFS每个状态只经过一次，而DFS可能会反复途径某个状态 因此BFS的时间复杂度绝不会超过“地图”的大小，但DFS在不少情况下都是指数级的时间复杂度。而由于DFS反复途径同个状态的特性，我们要很小心的避免重复和循环搜索。在这个意义上，BFS比DFS更易维护，因为我们不必担心循环搜索的问题。

4. BFS消耗更多的空间资源 换句话说，就是BFS是用空间来换时间，BFS的最坏时间复杂度比DFS小，但是空间复杂度不可避免地要膨胀。

搜索方式	数据结构	经典适用问题	泛用性	常见问题	优化
DFS	栈	连通性/路径存在性	好	循环搜索导致死循环，忘记状态还原	剪枝(时间)/IDDFS
BFS	队列	最短路径	一般	不易出错,但空间开销大	剪枝(空间+时间)

[Locietta]

终于摸完了(￣▽￣)"

[FavonianKong]

严格来讲，我这里由于采用了离开的时候才标记的策略，把状态修改给延后了。
如果按照到达时就标记的策略，应该把状态修改塞到每个if分支里。

这里是不是这个意思：

#include <stdio.h>
int map[50][50], n, count, length;
void dfs(const int step, int i, int j) {
    if (i == n - 1 && j == n - 1) {
        count++;
        if (step < length) length = step;
        return;
    }
    // map[i][j] = 1; 
    // 这里是不是就不用了？否则好像会重复，因为在dfs进来之前就已经转移状态了？
    // 不知道理解的对不对，那这样的话main函数调用dfs(0,0,0)的时候是不是也要先把 map[0][0] 设置为1？
    if (i && !map[i - 1][j]) { // left
        map[i-1][j] = 1;
        dfs(step + 1, i - 1, j);
        map[i-1][j] = 0; 
    }
    // up
    // right 
    // down
    // map[i][j] = 0;
}
int main(void) {
    while (scanf("%d", &n) != EOF) {
        count = 0, length = __INT_MAX__;
        for (int i = 0; i < n; ++i) { // read
            for (int j = 0; j < n; ++j) {
                scanf("%d", &map[i][j]);
            }
        }
        map[0][0] = 1;   // 这里这么加一句理解对吗？
        dfs(0,0,0);
        count ? printf("%d\n", length) : puts("No solution");
    }
    return 0;
}