526互联

DFS 与 BFS

发布时间 2023-10-08 18:10:48作者: xiehanrui0817

简介

  • 状态：解决问题所关注的属性的集合。
  • 转移：状态之间的变化过程。
  • 搜索：处理状态转移、寻找新状态、枚举（遍历）所有状态的一种算法思想。
  • 搜索树：状态和有效转移形成的树形结构，每个状态只会被扩展一次。

深度优先搜索

  • 全称为 Depth-First Search，简称 DFS、深搜。
  • 这个算法一般采用递归的形式，本质上是一种枚举遍历所以状态的算法，算法思想就是 “不撞南墙不回头”。底层实现为一个栈。
  • 一般最常用的 DFS 有 \(5\) 种：全排列搜索、组合搜索、子集搜索、全排列搜素、网格图搜索。
  • 回溯：从新状态退回旧状态。相当于，递归调用是把旧状态处理进度压入栈顶，递归结束后弹出栈顶回到旧状态。
  • DFS 只要把状态转移想清楚就基本能写出来。

全排列

  • 枚举（生成） \(1 \sim n\) 的全排列。
  • 状态：\((t, v[])\)，表示现在选第 \(t\) 个数，\(n\) 个数选择的状态为 \(v\)。
  • 转移：\((t, v[]) \rightarrow (t + 1, v'[])(对于某个下标 i(1 \leqslant i \leqslant n), v_i = 0, v'_i = 1，其余 v_j = v'_j)\)。
  • 初始状态：\((1, v = \{0, 0, 0, \cdots 0\})\)，目标状态：\((n + 1, v = \{1, 1, 1, \cdots 1\})\)。
  • 时间复杂度：\(O(n\cdot n!)\)，一般可以通过 \(n \leqslant 10\) 的算法。
int n, a[MAXN], v[MAXN];

void dfs(int t) {
  if (t == n + 1) { // 生成了全排列
    for (int i = 1; i <= n; i++) {
      cout << a[i] << ' ';
    }
    cout << '\n';
    return ;
  }
  for (int i = 1; i <= n; i++) {  // 转移：往序列添加一个没有出现过的数字
    if (!v[i]) {
      a[t] = i;  // 记录序列
      v[i] = 1;  // 标记出现
      dfs(t + 1);
      v[i] = 0;  // 回溯，重新标记为未出现
    }
  }
}

组合

  • 枚举（生成）从 \(1 \sim n\) 中挑选 \(m\) 个数的组合。
  • 状态：\((t, last)\) 表示现在选到第 \(t\) 个数，上一个数选的是 \(last\)。
  • 转移：选一个 \(> last\) 的数，即选一个 \(i\)，使得 \(last < i \leqslant n\)，然后添加到序列末尾。
  • 初始状态：\((0, 0)\)，目标状态：\((n + 1, last)\)。
  • 时间复杂度：\(O(m \cdot C_{n}^m)\)。
int n, m, a[MAXN];

void dfs(int t, int last) {
  if (t == m + 1) { // 生成了组合
    for (int i = 1; i <= m; i++) {
      cout << a[i] << ' ';
    }
    cout << '\n';	
    return ;
  }
  for (int i = last + 1; last <= n; i++) { // 在序列末尾添加一个数字
    a[x] = i, dfs(t + 1, i);
  }
}

子集

  • 生成集合 \({1,2,…,n}\) 的所有的子集。

  • 状态：当前的考虑第 \(t\) 个元素和已选的子集。

  • 转移是考虑当前元素是否添加到子集中。

  • 初始状态：\((1, \varnothing)\)，\(\varnothing\) 表示空集。目标状态：\((n + 1, s)\)，\(s\) 为某个子集。

  • 时间复杂度：每个数有两种选择，\(O(2^n)\)。

int n, m, a[MAXN];

void dfs(int t) {
  if (t == n + 1) {
    for (int i = 1; i <= m; i++) {
      cout << a[i] << ' ';
    }
    cout << '\n';
    return ;
  }
  a[++m] = t, dfs(t + 1); // 选第 t 个数
  m--, dfs(t + 1); // 不选
}

子序列

  • 子序列：可以不连续的序列（要求有序）。以求出所最长上升子序列长度为例。
  • 状态：\((last, len)\) 表示子序列末尾为 \(last\)，长度为 \(len\)。
  • 转移：往子序列末尾加入一个下标和数值都更大的数。
  • 初始状态：\((0, 0)\)，目标状态：不知。
  • 时间复杂度：最坏 \(O(2^n)\)。
int n, ans, a[MAXN];

void dfs(int last, int len) {
  ans = max(ans, len);   // 更新答案
  for (int i = last + 1; i <= n; i++) { // 转移
    if (a[i] > a[last]) [
      dfs(i, len + 1);
    }
  }
}

网格图

  • 计算起点 \((sx, sy)\) 到终点 \((ex, ey)\) 的路径数量（不能经过重复格子和有障碍的格子）。
  • 状态：\((x, y)\) 表示当前走到了 \((x, y)\)。
  • 转移 : \((x, y) \rightarrow (x + 1, y + 1), (x + 1, y - 1), (x - 1, y + 1), (x - 1, y - 1)\)。
  • 初始状态：\((sx, sy)\)，目标状态：\((ex, ey)\)。
  • 时间复杂度：\(O(4^{nm})\)，由于并不是每次都有 \(4\) 次转移，因此达不到该复杂度。
const int dx[4] = {1, 0, -1, 0}; // 方向数组
const int dy[4] = {0, 1, 0, -1};

int n, m, sx, sy, ex, ey, ans;
bool a[MAXN[MAXN], v[MAXN][MAXN];

void dfs(int x, int y) {
  if (x < 1 || y < 1 || x > n || y > m || a[x][y] || v[x][y]) { // 非法状态
    return ;
  }
  if (x == ex && y == ey) { // 到达终点
    ans++;
    return ;
  }
  v[x][y] = 1; // 标记
  for (int i = 0; i < 4; i++) { // 转移
    dfs(x + dx[i], y + dy[i]);
  }
  v[x][y] = 0;
}

广（宽）度优先搜索

题单

  • 全称为 Breadth-First Search，简称 BFS，广搜。
  • 这个算法一般用队列实现，算法思想不是想 DFS 一样一条道走到黑，不撞南墙不回头，而是比较有技巧性的逐层进行扩散。在境界上就比 DFS 高一些些，DFS 就是无脑枚举，BFS 还是有一些技巧性在里面。
  • 具体来说我们会用一个队列来存储状态，在队列里永远只有两层状态，第 \(i\) 层会扩散至第 \(i + 1\) 层，只有第 \(i\) 层全部扩散完毕后，才会去扩散第 \(i + 1\) 层的状态。
  • 不过广搜也会有一个条件：第一次到达某个状态就是最优的，即状态转移图的边权非负。这就是广搜在时间复杂度上的优势：每个状态只会被访问一次。
  • 和深搜一样，广搜只需要确定好状态、转移就基本结束了。而且 BFS 还是一种常用的最短路算法，不过图的边权必须相等且非负。

过程

  • 将初始状态压入队列。

  • 每次取出队头元素进行扩散，如果扩散出来的状态合法且第一次访问，压入队列并记录答案。

下面用 洛谷 P1443 来再熟悉一下 BFS 的过程。

题意

  • 有一个 \(n \times m\) 的棋盘，在某个点 \((sx,sy)\) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步（不能到达输出 \(-1\)）。
  • \(1 \leqslant n, m \leqslant 400\)。

思路

  • 首先这个题肯定是可以暴力 DFS 的，只不过时间复杂度炸掉了。
  • 这时我们就可以考虑 BFS，我们的状态显然是 \((x, y, w)\) 表示现在在 \((x, y)\) 走了 \(w\) 步，转移就是从 \((x, y, w) \rightarrow (x', y', w + 1)\)，其中马可以从 \((x, y)\) 通过一步到达 \((x', y')\)。初始状态：\((sx, sy, 0)\)。
  • 我们用 \(d_{x, y}\) 表示 \(x, y\) 的答案，最开始初始化为 \(-1\)，如果当前的 \(d_{x, y} \ne -1\)，说明 \(x, y\) 已经被访问过了，因为我们是一层一层的扩散，并且边权为 \(1\)，所以最开始访问时，就已经得到了最优答案了，就不必压入队列了。否则 \(d_{x, y} = w\)，将状态压入队尾，后续进行扩散。

时间复杂度

\(n \times m\) 个状态，每个状态 \(8\) 次转移，共 \(O(nm)\)。

Code

点击查看代码 
#include<iostream>
#include<algorithm>

using namespace std;

const int MAXN = 405;
const int dx[8] = {-1, 1, 2, 2, 1, -1, -2, -2}; // 方向数组，转移
const int dy[8] = {2, 2, 1, -1, -2, -2, -1, 1};

struct Node{
  int x, y;
}que[MAXN * MAXN];

int n, m, h = 1, t, x, y, d[MAXN][MAXN];

void Record(int x, int y, int step){ // 处理状态
  if (x < 1 || y < 1 || x > n || y > m || d[x][y]) {  // 非法或非最优
    return ;
  }
  d[x][y] = step, que[++t] = {x, y}; // 更新答案，将状态压入队列
}

void Bfs(){
  for(Record(x, y, 1); h <= t; ){ // 终止条件：队列为空，没有状态需要扩散
    Node u = que[h++];
    for(int i = 0; i < 8; i++){ // 转移
      Record(u.x + dx[i], u.y + dy[i], d[u.x][u.y] + 1);
    }
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> x >> y;
  Bfs();
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      cout << d[i][j] - 1 << ' ';
    }
    cout << '\n';
  }
  return 0;
}