简介
- 状态:解决问题所关注的属性的集合。
- 转移:状态之间的变化过程。
- 搜索:处理状态转移、寻找新状态、枚举(遍历)所有状态的一种算法思想。
- 搜索树:状态和有效转移形成的树形结构,每个状态只会被扩展一次。
深度优先搜索
- 全称为 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;
}