搜索初步: 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:
输入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:
输入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:
深度优先DFS
什么是DFS?
所谓的深度优先指的是从某个状态开始,不断地转移到下一个状态,直到不能继续转移为止,这时候返回前一步,转移到其他的状态,直到到达解状态。
emmm有亿点抽象,那...具体在这个迷宫问题上来看呢?
在迷宫问题上翻译一下深度优先的定义的话:就是说从某个格子出发,不断地往四周的格子走,如果考虑不走回头路的话,那么总会出现不能继续走的情况。这时候,退回到上一步,在上一步走其他的路,如果上一步没有其他的路可走了就再退回到上一步......不断重复这个过程,直到走到终点为止。
这就很直观了,就像一个人通过试错法来走迷宫的过程:先一路走到死路,然后回到前一步选另一条路,不断地试错,这样就遍历了所有能走的路。事实上也就是一种回溯法。
画成搜索树的话就是这样👇
![](https://user-images.githubusercontent.com/53137814/92997517-7f458600-f546-11ea-9df7-6c143afe5857.png)
这个搜索过程对应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分支都该是一个完整的状态转移→递归调用→状态还原过程
看,是不是很容易~
![飘了](https://user-images.githubusercontent.com/53137814/92998417-47414180-f54c-11ea-94fe-9352fef40f0b.png)
广度优先BFS
什么是BFS?
BFS和DFS很类似,区别只在于搜索的顺序不同:BFS总是先搜索距离初始状态近的状态。
也就是说,它是按照 开始状态→1次转移可以到达的所有状态→2次转移可以到达的所有状态→…… 这样的顺序进行搜索。
在迷宫的例子里,就是说我们按照走1步能到达的位置,走2步能到达的位置...这样的顺序逐一搜索,直到不再有能到达的位置。
想象我们拿着地图,画出一系列的“等高线”,先标距离为1的,再标距离为2的,直到地图上的每一个位置都被标上了要到达所需的步数。
画成搜索树的话就是这样👇
![](https://user-images.githubusercontent.com/53137814/92998839-f4b55480-f54e-11ea-8264-8e525c8521b3.png)
这个搜索过程对应 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的位置,这一操作增加了复杂度。