首页 > 其他分享 >DFS 与 BFS

DFS 与 BFS

时间:2023-10-08 18:11:09浏览次数:27  
标签:状态 last int 复杂度 DFS BFS MAXN

简介

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

深度优先搜索

  • 全称为 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;
}

标签:状态,last,int,复杂度,DFS,BFS,MAXN
From: https://www.cnblogs.com/xhr0817-blog/p/17749823.html

相关文章

  • 【大数据】HDFS
    HDFS原理基本介绍1:HDFS全称:HadoopDistributedFileSystem2:Hadoop三大组件(HDFS、MapReduce、YARN)之一3:可在多台服务器上构建集群,提供分布式数据存储能力4:NameNode:主角色,管理HDFS集群和DataNode角色5:DataNode:从角色,负责数据的存储6:SecondaryNameNode:辅助角色,协......
  • FastDFS 简介
    FastDFS简介FastDFS是一款开源的分布式文件系统,功能主要包括:文件存储、文件同步、文件访问(文件上传、文件下载)等,解决了文件大容量存储和高性能访问的问题。FastDFS特别适合以文件为载体的在线服务,如图片、视频、文档等等服务。FastDFS作为一款轻量级分布式文件系统,版本V6.01代......
  • FastDFS--扩展篇(Php&&Apache2&&Nginx)
         FastDFS不是通用的文件系统,只能通过专用的API来访问,目前提供了CJAVAPHP的API,下面我们来安装php扩展。   让Fastdfs支持php,在FastDFS的源码包解压后里面有个php_client目录,进入此目录,参照README进行安装: phpize./configuremakemakeinstall    ......
  • CH32V203的USBFS在主机和设备下的低功耗唤醒注意事项
    1.如果使用WFE睡眠,醒来后无需重新打开外设时钟;2.如果使用STOP模式睡眠,醒来后需要重新打开外设时钟。 USBFS_RCC_Init();3.STANDBY需要进入之前设置成IO(PB6.PB7)为外部事件,醒来之后设备复位(待机模式唤醒后复位),重新枚举USB。具体配置如下:voidSleep_WakeUp_Deal(){EXTI_Init......
  • Hadoop是什么? Hadoop是一个由Apache开发的开源分布式计算框架,它能够处理大规模数据并
    Hadoop是什么?Hadoop是一个由Apache开发的开源分布式计算框架,它能够处理大规模数据并行处理任务,支持大规模数据存储和处理。Hadoop的核心组件包括分布式文件系统HDFS和分布式计算框架MapReduce,它们使得Hadoop可以在廉价的硬件上并行地处理大量数据。Hadoop还包括很多相关的项目和子......
  • bfs (9/26)
    bfs可用于权值相同为1的时候求最短路问题#include<iostream>#include<algorithm>#include<cstring>#include<queue>usingnamespacestd;constintN=110;typedefpair<int,int>PII;queue<PII>q;inta[N][N],f[N][N];intn,m;intbfs()......
  • Hadoop是什么? Hadoop是一个由Apache开发的开源分布式计算框架,它能够处理大规模数据并
    Hadoop是什么?Hadoop是一个由Apache开发的开源分布式计算框架,它能够处理大规模数据并行处理任务,支持大规模数据存储和处理。Hadoop的核心组件包括分布式文件系统HDFS和分布式计算框架MapReduce,它们使得Hadoop可以在廉价的硬件上并行地处理大量数据。Hadoop还包括很多相关的项目和子......
  • 在操作过程中遇到Attempting to operate on hdfs namenode as root报错
    在操作过程中遇到Attemptingtooperateonhdfsnamenodeasroot报错HDFS格式化后启动dfs出现以下错误:[root@hadoop101sbin]#start-dfs.shStartingnamenodeson[hadoop101]ERROR:AttemptingtooperateonhdfsnamenodeasrootERROR:butthereisnoHDFS_NAMENO......
  • Hadoop是什么? Hadoop是一个由Apache开发的开源分布式计算框架,它能够处理大规模数据并
    Hadoop是什么?Hadoop是一个由Apache开发的开源分布式计算框架,它能够处理大规模数据并行处理任务,支持大规模数据存储和处理。Hadoop的核心组件包括分布式文件系统HDFS和分布式计算框架MapReduce,它们使得Hadoop可以在廉价的硬件上并行地处理大量数据。Hadoop还包括很多相关的项目和子......
  • 关于hdfs删除数据之后9870报错进入safe mode
    1.运行fsck命令:首先,运行Hadoop的fsck命令来检查文件系统的完整性并标记出已删除的文件。在终端或命令提示符中执行以下命令:hdfsfsck/-files-blocks-locations-delete上述命令会运行fsck并删除标记为已删除的文件。这将清除文件系统中的已删除文件的痕迹,并解决报错......