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

递归回溯与剪枝


递归、回溯与剪枝

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

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

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

“和最小”题目描述
? 设有一个长度为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、递归回溯:由于回溯法是对解空间的...
回溯递归练习题
回朔与递归 1.液晶数字排列:下面是用液晶七笔数字表示的十个数,我们把横、竖的一个短划都称为一笔。现 请你把这十个数重新排列,使从第二个数以后的每一...
第五课 递归与回溯法
关于回溯法搜索的递归程序... 1页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
合并递归回溯
合并递归回溯_学科竞赛_初中教育_教育专区。1、设有两个有序表 L1 和 L2(从小...C++ 递归和回溯 22页 2下载券 递归回溯与剪枝 22页 免费 递归与回溯算法 70...
递归法和回溯法
递归和回溯递归和回溯法隐藏>> 递归和回溯法 有人说,回溯实际上是递归的展开,但实际上。两者的指导思想并不一致。 打个比方吧,递归法好比是一个军队...
递推-递归-分治-回溯
递推—递归—分治—回溯 递推算法在程序编辑过程中,我们可能会遇到这样一类问题,出题者告诉你数列的前几个数,或 通过计算机获取了数列的前几个数,要求编程者求出...
回溯初学
这两类函数统称为剪枝函数。 问题的解空间通常是在搜索问题的解的过程中动态...回溯可以分为:递归回溯、迭代回溯 搜索:全面访问所有可能的情况,分为两种:不...
搜索与回溯算法介绍
(3)以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无 效搜索; ...【递归回溯递归回溯】 由于回溯法是对解空间的深度优先搜索, 因此在一般情况...
算法提高回溯
说明:上面给出的是回溯法的通用递归框架,用红色标记出来的部分是根据不同问题的 不同情况可以做变动的地方,比如“剪枝”、“限界”提高算法效率等技巧都是通过变换...
算法回溯递归动态贪心分支综合代码
算法回溯递归动态贪心分支综合代码_计算机软件及应用_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 算法回溯递归动态贪心分支综合代码_计算机软件及应用_IT...
更多相关标签: