DFS & BFS

发表于 分类于 ， 阅读次数：
搜索是一种递归地解决问题的方式。它往往通过看似“暴力”的穷举策略，来试探问题的答案所在。选择正确高效的搜索策略在搜索中非常重要。

本文作为一篇很久以后才写下的博客，只简单地写一下关于DFS & BFS的经验。

首先需要明白什么是搜索、为什么搜索。本质上来说，搜索是一种递归的处理问题的方式，是一种使用递归来代替循环的方式。就比如说，对于求出前5个数的全排列，如果不使用递归，我们就需要写出5个for循环，然后每层循环上加上适当的判定条件；这无 疑让代码变得冗长。但如果在系统栈上利用递归求解，我们就只需要将判定条件书写一次，然后逐层递归判定即可。

那么搜索能解决什么样的问题？近乎所有。但是，出于数据规模以及运行时间考虑，搜索通常不是一种优秀的解法——其他更针对性的算法往往才是问题的正解。但是，我们仍然不能忽略搜索算法的普适性及可尝试性。甚至，如果你剪枝剪的够刁钻，非正解也能够解决题目。

DFS：

DFS，深度优先搜索，顾名思义，就是一种“一条路走到黑”的、一条路一条路搜索的搜索方式，很类似于栈的工作原理（实际上也可以用栈来写DFS）。 由于DFS需要遍历到所有结点且会有重复的情况，所以速度通常较慢，需要搭配高超的剪枝技术。一个潦草的DFS模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
void dfs()
{
	if(剪枝条件达成)	continue; 
	if(边界条件成立)	记录答案 
	for(下层结点)
	{
		if(超过边界)	continue
		记录状态（记忆化）
		搜索下一层
		回溯状态	
	}
}

对于记忆化，更推荐记录结点的具体结果，而不是只记录是否走过。这样才能尽可能压缩复杂度。
当然，实际应用情况并不会那么简单。DFS更多地还是需要想清楚自己要干嘛，如何用递归高效地实现，以及如何剪枝优化以更快地实现，而不是为了模板性的搜索而搜索。

BFS：

BFS，广度优先搜索，就是一种优先广度、一层一层扩展的搜索方式，类似于队列的工作原理（实际也是用栈来实现的）。BFS的好处便是其一层层扩展的特征，使其在一些情况下不必扩展到所有结点就能得到结果，如最短路问题、连通块问题等。但其缺陷也十分明显——由于其一层一层扩展且不pop的特质，很容易导致队列容量爆炸导致MLE。所以在使用BFS时，一定要注意控制数据层的规模，或者通过记忆化等方式进行优化。
一个潦草的BFS模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bfs()
{
	while(!q.empty())
	{
		取出队首结点
		弹出队首结点
		队首结点记忆化状态更改 
		if(结点符合边界条件)	记录答案 & break 
		for(下层结点) 
		if(超过边界)	continue
		将下层结点放入队列 
		下层节点状态记忆化或更新最优解 
	}
}

相较于DFS，BFS的流程更加模式化，但依旧需要以搜索的思想来解决问题，而不是以搜索的模板来解决问题。

搜索的优化策略

1、记忆化搜索。对搜索树上点所处的状态进行记录，或者转向动态规划。
2、剪枝。对一些已经不满足条件的分支直接删除。
3、更改搜索顺序与起止点。灵活地选择正搜或者倒搜，以及更改或增加搜索的起始点，以便搜索更好地扩展（例如双向DFS/BFS）。
4、深度限制。通过人为干预搜索深度（设置深度上界），来避免陷入过深的搜索。