当前位置:首页 >> 学科竞赛 >>

递归回溯与剪枝


递归、回溯与剪枝

递归与回溯
? 我们有时会碰到一些题目,它们既不能通

过建立数学模型解决,又没有现成算法可 以套用,或者必须遍历所有状况才可以得 出正确结果。 这时,我们就必须采用搜索 算法来解决问题。
? 搜索算法按搜索的方式分有两类,一类是 深度优先搜索,一类是广度优先搜索。而 对于深度优先搜索来说,我们需要使用到

的一个技术就是递归与回溯。

“和最小”题目描述
? 设有一个长度为N的数字串,要求使用K个

?

?
? ?

加号将它分成K+1个部分,找出一种分法, 使得这K+1个部分的和能够为最小。 有一个数字串:312, 当N=3,K=1时会有 以下两种分法: 1) 3+12=15 2) 31+2=33 这时,符合题目要求的结果是:3+12=15

递归回溯法算法框架[一] procedure Search(k:integer); Var i begin for i:=1 to 算符种数 Do if 满足条件 then begin 保存结果 if 到目的地 then 输出解 else Search(k+1); 恢复:保存结果之前的状态{回溯一步} end; end;

递归回溯法算法框架[二] procedure Search(k:integer); Var i begin if 到目的地 then 输出解 else for i:=1 to 算符种数 Do if 满足条件 then begin 保存结果 Search(k+1,参数表);
恢复:保存结果之前的状态{回溯一步}

end; end;

搜索策略
? 题目要求的就是在每个数字之间:

或者填加号,或者什么都不填。根 据这个要求,我们可以从头开始扫 描整个数字串,逐个考察是否要填 加号,然后检查下一个数字间的位 置,直到最后一个数字。 ? 下面是一个例子和它的状态树

7和6之间 添加一个 加号

7和6之间 不添加加 号 7

7+6 7+6+2 7+62 76+2

76 762 762+9

7+6+2+9

7+6+29

7+62+9

7+629

76+2+9

76+29

7629

? 数字7629需要插入2个加号
? 这是一棵完整的搜索树。 ? 结点内表示当前处理的状态,每向后处理一个空位即

深入一层。
? 我们可以看到,在最后的所有叶子结点中,有三个黄

色的结点是满足条件的。

迷宫问题
? 给出一个迷宫的地图,有一些格子中有障

碍,问从起点到终点的最短路径,并输出 所有的最短路径。 ? 回溯法解题思路 ? 1、 这个方向有路可走,我没走过, 往 这个方向前进 ? 2、 是死胡同,往回走,回到上一个路口 ? 3、 重复第一步,直到找着出口

但是
? 回溯法的缺点暴露无遗:
? 搜索耗时极巨,无法忍受。

? 那么
? 我们可否提前判断我们前进的方向是

否可能得到最优解呢?如果可以的话 ,搜索效率岂不是能够提高了吗 ? 答案就是: ? 剪枝!

关于剪枝
? 剪枝的概念,其实就跟走迷宫避开死胡同差不 多.。若我们把搜索的过程看成是对一棵树的遍 历,那么剪枝顾名思义,就是将树中的一些“死 胡同”,不能到达我们需要的解的枝条“剪” 掉,以减少搜索的时间。

? 搜索算法,绝大部分需要用到剪枝。 然而,不 是所有的枝条都可以剪掉,这就需要通过设计 出合理的判断方法,以决定某一分支的取舍。 在设计判断剪枝条件的时候,就需要有一定的 方法。

最优性剪枝
? 又称为上下界剪枝 ? 一种重要的搜索剪枝策略 ? 记录当前得到的最优值 ? 如果当前结点已经无法产生比当前

最优解更优的解时,可以提前回溯

回到加号题
儿子结点的数一定比父亲大 即搜索树深度越深得到的解越大 满足最优性剪枝的条件 我们可以记录当前得到的解的最小值 ? 如果当前得到的和值已经超过保存的 最小解,即不必再继续深入搜索,回 溯。
? ? ? ?

再看搜索树
7 7+6 7+6+2 7+62 76+2 762+9 76 762

7+6+2+9

7+6+29

7+62+9

7+629

76+2+9

76+29

7629

? 我们可以看到红色结点的子节点不可能有

最优解

最优性剪枝结果
7

7+6

76

7+6+2

7+62

7+6+2+9

7+6+29

? 结点数大大减少。

可行性剪枝
? 除最优性剪枝外,另一种重要的搜

索剪枝策略 ? 判断继续搜索能否得出答案,如果 不能直接回溯

再看搜索树
7

这个节点的 加号不可能 有解,可以进 行可行性剪 枝

7+6
7+6+2 7+62 76+2

76
762 762+9

7+6+2+9

7+6+29

7+62+9

7+629

76+2+9

76+29

7629

? 对于图中蓝色结点。后面能够插入’+’的位置

已经少于未用完’+’的数量,肯定不可能有解。
? 对于这种结点,其子节点不可能有解,可以

回溯。

迷宫问题
? 最优性剪枝 ? 我们可以将每一次搜索出的路径长度与上

界比较(初始上界=∞),不断降低上界, 一旦出现路径长超出上界而仍未到达目标 点,则放弃该搜索进程。 因为就算继续搜 索下去,这一条路径也必然比其他路径长 ,不是最优解。

总结
? 深度优先搜索的程序简洁易懂,空间需求

也比较低,但是这种方法的时间复杂度往 往是指数级的,倘若不加优化,其时间效 率简直无法忍受;所以,如何用正确的方 法对程序进行优化,就成为搜索算法编程 中最关键的一环。那么,剪枝就是搜索优 化中最基本的方法之一。

总结
? 两种常用的剪枝方法:
? 最优性剪枝

? 适用范围:子结点的代价全部高于或 低于父结点 ? 又之称为多米诺性质。 ? 可行性剪枝
? 根据题意作出判断是否继续搜索还有 可能得到解

剪枝的原则
? 正确性 ? 准确性 ? 高效性

总结
? 在搜索算法中,几乎都需要采用程序优化,

以减少时间复杂度。 而这里所说的两种剪 枝方法,是最常见的优化方法之一。
? 然而,尽管可以采用众多优化算法使得程

序的效率有所提高,搜索算法本身的时间 复杂度不能从本质上减少是不可改变的事 实。
? 不妨在使用搜索算法之前先仔细想想,有

没有其他更好的算法。


赞助商链接
相关文章:
递推-递归-分治-回溯
递推—递归—分治—回溯 递推算法在程序编辑过程中,我们可能会遇到这样一类问题,出题者告诉你数列的前几个数,或 通过计算机获取了数列的前几个数,要求编程者求出...
回溯
确定结点的扩展搜索规则 (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝...(2)非递归回溯框架 1: int a[n],i; 2: 初始化数组 a[]; 3: i = ...
回溯算法的一些例题
回溯算法的一些例题 - 回溯算法 搜索与回溯是计算机解题中常用的算法, 很多问题无法根据某种确定的计算法则来求解, 可 以利用搜索与回溯的技术求解。回溯是搜索算法...
递归法和回溯法
2页 免费 第5章 回溯法 76页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 递归和回溯递归和回溯法递归...
编译原理第五章 作业参考答案
对每个非终结符写出不带回溯递归子程序如下: char CH;//存放当前的输入符号 void P_S()//非终结符 S 的子程序 { if(CH==’a’) READ(CH);//产生...
搜索与回溯算法介绍
(3)以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无 效搜索; ...【递归回溯递归回溯】 由于回溯法是对解空间的深度优先搜索, 因此在一般情况...
回溯算法的一些例题
按此原则不断搜索回溯再搜索,直到找到新的出路或从原路 返回入口处无解为止。 递归回溯法算法框架[一] procedure Try(k:integer); begin for i:=1 to 算符...
搜索与回溯算法
[提高与思考 2]: 回溯还可以通过循环加递归的形式来实现,放置一个皇后的过程...对于 这种情况要很快地“剪掉”多余分枝得出结论,这就是搜索里所说的“剪枝” ...
一种回溯算法入门教学思路
递归前后同样需更新、 恢复 cc 的值,并在递归前进行该剪枝检查。 3 结语 本文提出的回溯法教学思路采用了相对明确、简单的解题步骤,有 一定局限性,因此只适用于...
回溯算法的应用
回溯法,其意义是在递归直到可解的最小问题后,逐步返回原问题的过程。而这里 所说的回溯算法实际是一个类似枚举的搜索尝试方法, 它的主题思想是在搜索尝试过程 中...
更多相关标签: