回溯 DFS 深度优先搜索[待更新]

时间:2021-09-25 03:41:50
 
首先申明,本文根据微博博友 @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: ... // 其他操作