深搜与宽搜的解题思路

时间：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):

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

　　优化技巧（剪枝）：将不可能的解提前剪掉。

 

相关文章