搜索学习笔记

〇、什么是搜索？

认识搜索

搜索，是基本算法中的一个非常重要的算法！搜索，可以理解为枚举法的应用。

搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。 —— OI-WIKI
关于搜索

搜索是一些高级算法的基础，它有很多种优化方式，如减小状态空间、更改搜索顺序、剪枝等。

搜索也有几个类别，如DFS（深度优先搜索）、BFS（广度优先搜索）...

一、深度优先搜索

定义

深度优先搜索（DFS，Depth First Search），顾名思义，就是按照深度优先这一潜规则来进行搜索的算法。

当有这样一颗树时，DFS的搜索顺序即为此树前序遍历（先序遍历）：ABDGECFH。我们称这样的结构为搜索树！

实现

DFS在搜索算法中，常常指利用递归函数方便地实现暴力枚举的算法。 —— OI-WIKI

没错，DFS的实现就是用递归实现！

代码的框架基本为如下：

返回值类型 dfs(参数列表) {
	if (函数出口) {
		//TO-DO...
		return;
	}
	if (剪枝)	return;
	//可以有多个剪枝
    //TO-DO...
	for (/*...*/) {//一般都要用循环
		if () {
			dfs();//递归调用
			//回溯 看情况
		}
	}
}

当然，框架因题目而异。

回溯法

(1). 定义

刚才DFS的代码框架中有一个回溯。

那什么是回溯法呢？

回溯法是一种经常被用在DFS的技巧。

其本质是：走不通就回头。 —— OI-WIKI

传说中有一个十分cute的算法，ta不撞南墙不回头，ta总是在俄罗斯套娃似的调用自己。 —— C20253036zhangyuming

(2). 回溯的过程
- Step 1. 构造空间树；
- Step 2. 进行遍历；
- Step 3. 如遇到边界条件，即不再向下搜索，转而搜索另一子树；
- Step 4. 达到目标条件，输出结果。

例题

题目描述：

Freda和Rainbow运送只小猫坐索道下山。索道上的缆车最大承重量为，而只小猫的重量分别是。当然，每辆缆车上的小猫的重量之和不能超过。每租用一辆缆车，Freda和Rainbow就要付美元，所以他们想知道，最少需要付多少美元才能把这只小猫都运送下山？（原题为小猫爬山）
解题思路：用DFS，思路我不会写，看《算法竞赛进阶指南》吧！

详细代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n, w, a[MAXN], b[MAXN], ans = INT_MAX;
void dfs(int x, int y) {
	int nx = x + 1, ny = y + 1;
	if (x == n + 1) { //出口
		ans = min(ans, y);
		return;
	}
	if (y >= ans) { //剪枝
		return;
	}
	for (int i = 1; i <= y; i++) { //分配到已租用缆车
		if (b[i] + a[x] <= w) { //可以装下
			b[i] += a[x];
			dfs(nx, y); //递归调用
			b[i] -= a[x]; //回溯
		}
	}
	b[ny] += a[x];
	dfs(nx, ny);
	b[ny] -= a[x];
}
signed main() {
	cin >> n >> w;
	for (int i = 1; i <= n; i++) { //输入
		cin >> a[i];
	}
	stable_sort(a + 1, a + n + 1, greater<int>()); //优化搜索顺序
	dfs(1, 0);
	cout << ans;
	return 0;
}

可以看到这里有一个小小的剪枝和一个优化搜索顺序，下面我们就来深入了解一下剪枝。

二、剪枝优化

定义

什么是剪枝呢？因为DFS的时间复杂度特别高，所以我们要去掉一些冗余的搜索！

还是这颗搜索树，当你要找E这个节点时，你遍历到D了，你发现条件对不上了，就果断return，回到上一个节点，去遍历右子树。

这个就是剪枝！
分类

刚才举的例子是剪枝的一种，名为可行性剪枝。剪枝主要分为五种：
- 优化搜索顺序：在不同的问题中，搜索树的各个层次、各个分支之间的顺序不是固定的，不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。
  
  前面的例题_"小猫爬山"_就是将小猫按照重量降序排列，优化时间。
- 排除等效冗余：在搜索过程中，若能判断从搜索树当前节点上沿某几条不同分支到达的子树是相同的，那么只需对其中一条分支执行搜索。
- 可行性剪枝：其是指在搜索过程中，及时对当前状态进行检查，若发现当前解已经不可用了，就执行回溯。可行性剪枝有时也叫上下界剪枝，某些题目条件的范围限制是一个区间，通过区间限制来搜索就算是上下界剪枝。
- 最优性剪枝：在最优化问题的搜索过程中，若当前花费的代价已超过当前搜索到的最优解，那么无论采取多么优秀的策略到达递归边界，都不可能更新答案，此时可以停止对当前分支的搜索进行回溯。
  
  前面的例题_"小猫爬山"_的剪枝就是最优性剪枝。
- 记忆化：在搜索过程中记录每个状态的结果，在重复遍历某个状态的时候直接返回其结果。
思路

剪枝思路有很多种，大多需要对于具体问题来分析。
- 极端法：考虑极端情况，如果最极端（最理想）的情况都无法满足，那么肯定实际情况搜出来的结果不会更优了。
- 调整法：通过对子树的比较剪掉重复子树和明显不是最有「前途」的子树。
- 数学方法：比如在图论中借助连通分量，数论中借助模方程的分析，借助不等式的放缩来估计下界等等。
例题

上面那个不是咩？

三、广度优先搜索

定义

广度优先搜索（BFS，Breadth First Search，又被称为宽度优先搜索），是图上最基础、最重要的搜索算法之一。

所谓宽度优先，就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。

那BFS的搜索树又长什么个样子呢？

因为BFS的搜索规则为优先访问同一层的节点，所以BFS的遍历顺序为：ABCDEFGHIJKL。
区别

那么什么时候该用DFS，什么时候该用BFS呢？

当你想要从A→E时，按照DFS的套路，就应该这样搜索：
```
1. A → B
2. A → B → D
3. A → B → D → E total=3
4. A → C
5. A → C → E
step=5 total=2
```
诶，找到了，3步！

结果就Wrong Answer！

但是你按照BFS的规则：
```
1. A → B 
2. A → C
3. A → B → D
4. A → C → E total=2
step=4 total=2
```
是不是要省时省力很多？

没错，BFS本就是为最短路而生！

BFS算法找到的路径是从起点开始的最短合法路径。换言之，这条路径所包含的边数最小。在BFS结束时，每个节点都是通过从起点到该点的最短路径访问的。 —— OI-WIKI
过程

算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。

也可以看做是洪水从上往下倾泻：水往低处流，水会慢慢的蔓延。

那这就引出了泛洪算法（Flood Fill，又叫作洪水填充算法），这个以后再讲。

实现

框架用到了队列。

伪代码：（— OI-WIKI）

bfs(s) {
	q = new queue()
	q.push(s), visited[s] = true
	while (!q.empty()) {
		u = q.pop()
		for each edge(u, v) {
			if (!visited[v]) {
				q.push(v)
				visited[v] = true
			}
		}
	}
}

struct PR { //名称自己改
	int x, y, t;
};
返回值类型 bfs(参数列表) {
	PR op;
	queue<PR> q;
	while (!q.empty()) { //不为空
		op = q.front(), q.pop(); //取出队首元素 并弹出队首元素
		if (函数出口) { //输出答案
			return;
		}
		//TO-DO...
		//一般都要用循环
	}
}

例题

题目描述

少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。下图显示了一个迷阵的样例及李逍遥找到仙药的路线。（原题见仙岛求药）

解题思路：这道题算是很简单的啦！就是BFS爆搜！

详细代码：

#pragma GCC optimize(2,3,"Ofast")
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n, m, ans, dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, x, y, z, w; 
//dir是偏移量数组 用来求相邻上下左右连通块的坐标
bool a[MAXN][MAXN], b[MAXN][MAXN];
struct PR {
	int x, y, t; //x y 均为坐标 t 用来存答案
};
void bfs(int x, int y) {
	queue<PR> q; //队列
	PR op;
	q.push({x, y, 0});
	while (!q.empty()) {
		op = q.front(), q.pop(); //取出队首元素 并弹出队首元素
		if (op.x == z && op.y == w) { //找到仙药 输出答案
			cout << op.t << '\n';
			return;
		}
		for (int i = 0; i < 4; i++) {
			int nx = op.x + dir[i][0], ny = op.y + dir[i][1], nt = op.t + 1; //nt 为步数
			if (nx >= 1 && nx <= m && ny >= 1 && ny <= n && !a[nx][ny] && !b[nx][ny]) { //判断是否越界 是否被标记过 是否是可以走的路
				b[nx][ny] = 1; //打标记
				q.push({nx, ny, nt}); //存入队列
			}
		}
	}
	cout << "-1\n"; //不可能找到仙药
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	while (cin >> m >> n && m && n) {
		memset(a, 0, sizeof(a)); //多组测记得清零
		memset(b, 0, sizeof(b));
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				char op;
				cin >> op; //我是存在bool数组中的
				if (op == '@')	x = i, y = j, a[i][j] = 0; //记录起点
				if (op == '*')	z = i, w = j, a[i][j] = 0; //记录终点
				if (op == '.')	a[i][j] = 0;
				if (op == '#') a[i][j] = 1;
			}
		}
		bfs(x, y); //调用BFS函数
	}
	return 0;
}

四、结束语

这个Blog真是耗费我大量精力，还请多多发现纰漏，我会竭尽全力改进！

Thank you !

ykj60 吃饭的GGBond

2023-08-16 14:13:22

114514+

Even226 逗比

2023-08-11 7:06:00

6

root 站长

2023-08-10 21:18:42

666+

搜索学习笔记

搜索学习笔记

〇、 什么是搜索？

一、 深度优先搜索

二、 剪枝优化

三、 广度优先搜索

四、 结束语

共 3 条回复

〇、什么是搜索？

一、深度优先搜索

二、剪枝优化

三、广度优先搜索

四、结束语