深搜与宽搜的解题思路

写在开头：本文章提供深搜与宽搜的解题思路，无具体题目对应的代码，如想了解，请到个人主页查找，感谢观看。

深度优先搜索（DFS）：

递归，即函数调用自身，以逐步减小问题的规模。但在一些问题中，并不是所有的递归路径都是有效的。如图所示迷宫，很可能会进入橙色所标识的“死胡同”，只能回到之前的路径，直到找到绿色的解为止。

这种方法被称为回溯法。回溯法往往会尝试一条尽可能深而完整的搜索路线，直至完全无法继续递归时才回溯，因而需要用深度优先搜索(DFS) 实现。

所以学会深度优先搜索前一定要深刻理解递归，先来看一段代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 void dfs(int x){
 4     if(x==0) 
 5         return;
 6     cout<<x<<endl;
 7     dfs(x-1);
 8     cout<<"*"<<x<<endl;
 9 }
10 int main(){
11     dfs(5);
12     return 0;
13 }

结果为：

5
4
3
2
1
*1
*2
*3
*4
*5

因为函数的不断嵌套，cout<<"*"<<x<<endl; 始终不会运行，只有x-1=0时才会一层一层由小到大执行这一行。

下面是回溯的一般形式：

 1 回溯算法的一般形式如下:
 2 void dfs(int k) { // k代表递归层数,或者说要填第几个空
 3     if(所有空已经填完了){
 4         判断最优解/记录答案;
 5         return;    
 6     }
 7     for (枚举这个空能填的选项)
 8         if (这个选项是合法的){//查看这个情况有没有被占位 
 9             记录下这个空(保存现场);//有时还需占位，例如四阶数独中的行、列、块记录 
10             dfs(k+1);
11             取消这个空(恢复现场);//如果占位了还需要取消占位 
12         }
13 }

广度优先搜索(BFS)：

深搜会尽快完成一个可行的解，再回溯尝试其他的可能性。当解相对稀疏，或问题很大时，深搜可能陷入过深、过窄的“陷阱”，这个时候就需要用到宽搜。

广度优先搜索可以保证在求解最近、最短、最快等一类问题时，搜索到的首个解就是最优解。

考虑另一种思路，从起点出发，类似于泼水一般，让水流顺着多个方向同时蔓延。这种方法被称为洪泛法。洪泛法会扩展相同层更多的可能性以拓宽广度，往往会使用广度优先搜索(BFS) 实现。

先来了解一些关于队列的函数（结果附在每行结束）：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     queue<int> a;
 5     cout<<a.empty()<<endl;//1
 6     a.push(10);//{10}
 7     cout<<a.front()<<endl;//{10}
 8     cout<<a.empty()<<endl;//0
 9     a.pop();//{}
10     cout<<a.empty()<<endl;//1    
11         
12     a.push(12);
13     a.push(13);
14     a.push(14);//{12,13,14}
15     cout<<a.front()<<endl;//{12}
16     
17     return 0;
18 }

这样再理解广度优先搜索的算法就简单多了：

1 Q.push(初始状态); // 将初始状态入队
2 while (!Q.empty()) {
3 State u = Q.front(); // 取出队首
4 Q.pop();//出队
5 for (枚举所有可扩展状态) // 找到u的所有可达状态v
6 if (是合法的) // v需要满足某些条件，如未访问过、未在队内等
7 Q.push(v); // 入队(同时可能需要维护某些必要信息)
8 }