首页 > 代码库 > 回溯 DFS 深度优先搜索[待更新]
回溯 DFS 深度优先搜索[待更新]
首先申明，本文根据微博博友 @JC向北 微博日志 整理得到，本文在这转载已经受作者授权！
1.概念
回溯算法 就是 如果这个节点不满足条件 (比如说已经被访问过了)，就回到上一个节点尝试别的路径
也就是说 走到死胡同里边就往回走，直到找到出口.
回溯 是一种 选优搜索 。许多复杂规模较大的问题都可以用 回溯 解决 ，因此回溯法有 “通用解题方法”的美称。
2.思想
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而 若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
3.具体做法
（1）确定解空间，里边至少包含一个（最优）解。
（2）确定结点的扩展搜索规则。
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
4.
（1）问题框架
设问题的解是一个n维向量(a1,a2,………,an),约束条件是ai(i=1,2,3,…..,n)之间满足某种条件，记为f(ai)。
（2）非递归回溯框架
1:int a[N],i; //i 当前位置
2: 初始化数组a[];
3: i=1;
4:while(i>0(有路可走) and (未达到目标)) {
5: //如果说还没找到出口，就一直找，找不到别回来见我
6: if(i>n) // 如果说1-i的节点都找到了，就出这个屋
7: {
8: 搜索到一个解，输出；
9: }
10: else // 处理第i个元素
11: {
12: a[i]拿第一个可能的值；
13: while(a[i]在不满足约束条件且在搜索空间内)
14: {
15: a[i]下一个可能的值；
16: }
17: if(a[i]在搜索空间内)
18: {
19: 标识占用的资源；
20: i=i+1; // 扩展下一个结点
21: }
22: else
23: {
24: 清理所占的状态空间； // 回溯
25: i= i –1;
26: }
27:}
1.如果说 一个屋子有多个目标点 ：
总目标 = 所有目标点都找到
2.因为a[i]往下拿 拿到的节点不会重复 所以不会回到老路上去，所以只可能有一种方式出循环--找不到
3.我在这 把 JC向北 的意思转述一下：
while(i>0(还有路可走)&&没找到总目标){
if(i>n){
//如果说 最后一条路 a[n]找到了
保存 //如果还想找接着写条件
}else{
a[i]取到(相对于 a[i-1]所到达的节点的)下一条路径的第一条
while(第一条路a[i]不满足条件&&没出空间){
a[i]取到下一条
}
//接下来就要判断这条路O不OK？（实际上只要判读a[i]取到的这条路O不OK）
if(a[i]在范围内){
OK ,i++; //去找走的通的a[i+1]
}else{
i--; //回溯 这个a[i]没在上一条路径的基础上找到可行的路径
//退回去让保存上一条路径的a[i-1]试取下一个点
}
}
}
解决 找一个门的问题套路
while(有路可走 &&没找到){
if(找到1条路){
保存
}else{
找第一条路
while(){
找下一跳路
}
if(最后一条路满足条件){
i++; //走下一保存资源
}else{
i--; //回到上一保存资源
}
}
}
(3)递归框架
回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下：
1:int a[i];
2:try(int i)
3:{
4: if(i>n)
5: 输出结果;
6: else
7: {
8: for(j= 下界; j<= 上界;j=j+1) // 枚举i所有可能的路径
9: {
10: if(fun(j)) // 满足限界函数和约束条件
11: {
12: a[i]= j;
13: ... // 其他操作
回溯 DFS 深度优先搜索[待更新]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。