深搜与宽搜的解题思路

时间:2023-01-27 17:06:42

 

深度优先搜索(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
 


 

下面是回溯的一般形式:

 
 
 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 }

 


总结:

深搜与宽搜的解题思路

 

 

回溯法/深度优先搜索(上图 a) :

  快速构造解,使用递归。不撞南墙心不死。 但进入死路就回头了。

洪泛法/广度优先搜索(上图 b):

   寻找最优解,使用队列 从起点开始,逐层往外扩展。

  优化技巧(剪枝):将不可能的解提前剪掉。