文档章节

2018.4.24 回溯法

o
 osc_x4h57ch8
发布于 2018/04/24 14:41
字数 889
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

为了描述问题的某一状态,必须用到该状态的上一状态,而描述上一状态,又必须用到上一状态的上一状态……这种用自已来定义自己的方法,称为递归。

从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到” 尽头 “的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断” 回溯 “寻找解的方法, 称为回溯。

 

回溯法是以深度优先方式系统搜索问题解的算法,适用于解决组合数较大的问题。

回溯就是让计算机自动的去搜索,碰到符合的情况就结束或者保存起来,在一条路径上走到尽头也不能找出解,就回到原来的岔路口,选择一条以前没有走过的路继续探测,直到找到解或者走完所有路径为止。

回溯就是一种试探,类似于穷举,但回溯有“剪枝”功能。

回溯法一般有两种实现方式,分别是递归回溯和迭代回溯。

回溯一般使用递归来实现,那个这个递归调用该如何来写呢?进行回溯搜索都会有一系列的步骤,每一步都会进行一些查找。而每一步的情况除了输入会不一样之外,其他的情况都是一致的。这就刚好满足了递归调用的需求。通过把递归结束的条件设置到搜索的最后一步,就可以借用递归的特性来回溯了。

回溯常用模板:

1.非递归模板:

1: int a[n],i;
   2: 初始化数组a[];
   3: i = 1;
   4: while (i>0(有路可走)   and  (未达到目标))  // 还未回溯到头
   5: {
   6:     if(i > n)                                              // 搜索到叶结点
   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: }

2.递归模板:

1: int a[n];
   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:                   ...                         // 其他操作
  14:                   try(i+1);
  15:                   回溯前的清理工作(如a[i]置空值等);
  16:              }
  17:         }
  18:      }
  19: }

3.迭代回溯伪代码:

void IterativeBacktrack(void){
     int t = 1;
     while(t > 0){
         if(f(n,t) < g(n,t)){
             for(int i = f(n,t); i <= g(n,t); ++i){//这个for 是遍历各个值的意思,实际中写成for循环会有逻辑错误
                 x[t] = h(i);
                 if(constraint(t) && bound(t)){
                     if(solution(t)) Output(x);//solution 判断是否已经得到问题的解
                     else t++;
                 }
                 else t--;
             }
         }
     }
 }

4.递归回溯伪代码:

void Backtrack(int t){
    if(t > n) 
        Output(x);//Output 记录或者输出可行解
    else{
        //f(n,t)和g(n,t)表示在当前结点未搜索过的子树的起始编号和终止编号
        for( int i = f(n,t); i <= g(n,t); ++i){
            x[t] = h(i);
            //constraint和bound分别是约束函数和界限函数
            if(constraint(t) && Bound(t)) 
                Backtrack(t+1);
        }
    }
}

 

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

dict.items()和dict.iteritems()有什么区别?

问题: Are there any applicable differences between dict.items() and dict.iteritems() ? dict.items()和dict.iteritems()之间是否有适用的区别? From the Python docs: 从Python文档中......

法国红酒甜
25分钟前
20
0
R中“ =”和“ <-”赋值运算符有什么区别?

问题: What are the differences between the assignment operators = and <- in R? R中赋值运算符=和<-之间有什么区别? I know that operators are slightly different, as this example ......

fyin1314
55分钟前
14
0
之间的区别 和

问题: I'm learning Spring 3 and I don't seem to grasp the functionality behind <context:annotation-config> and <context:component-scan> . 我正在学习Spring 3,并且似乎不太了解<......

javail
今天
15
0
业内首款,百度工业视觉智能平台全新亮相

本文作者:y****n 业内首款全国产化工业视觉智能平台——百度工业视觉智能平台亮相中国机器视觉展(Vision China),该平台所具有的核心AI能力完全自主可控,在质检、巡检等场景中具有高效、...

百度开发者中心
昨天
7
0
我们如何制作xkcd样式图? - How can we make xkcd style graphs?

问题: Apparently, folk have figured out how to make xkcd style graphs in Mathematica and in LaTeX . 显然,民间已经想出了如何在Mathematica和LaTeX中制作xkcd风格的图形。 Can we d......

富含淀粉
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部