深度搜索 算法（c++深搜与宽搜的解题思路）
导读：写在开头：本文章提供深搜与宽搜的解题思路，无具体题目对应的代码，如想了解，请到个人主页查找，感谢观看。 深度优先搜索（DFS）：...
写在开头：本文章提供深搜与宽搜的解题思路 ，无具体题目对应的代码 ，如想了解 ，请到个人主页查找 ，感谢观看 。
深度优先搜索（DFS）：
递归 ，即函数调用自身 ，以逐步减小问题 的规模 。但在一些问题中 ，并不是所有的 递归路径都是有效的 。 如图所示迷宫 ，很可能会进入橙色所标识 的“死胡同 ” ，只能回到之前的路径 ，直到 找到绿色的解为止 。
这种方法被称为回溯法 。 回溯法往往会尝试一条尽可能深而完整的搜索路线 ，直至完全无 法继续递归时才回溯 ，因而需要用深度优先搜索(DFS) 实现 。
所以学会深度优先搜索前一定要深刻理解递归 ，先来看一段代码：
结果为：
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 }
总结：
回溯法/深度优先搜索(上图 a) ：
快速构造解 ，使用递归 。不撞南墙心不死 。 但进入死路就回头了 。
洪泛法/广度优先搜索(上图 b):
寻找最优解 ，使用队列 从起点开始 ，逐层往外扩展 。
优化技巧（剪枝）：将不可能的解提前剪掉 。
声明：本站所有文章 ，如无特殊说明或标注 ，均为本站原创发布 。任何个人或组织 ，在未征得本站同意时 ，禁止复制 、盗用 、采集 、发布本站内容到任何网站 、书籍等各类媒体平台 。如若本站内容侵犯了原著者的合法权益 ，可联系我们进行处理 。
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！