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

递归回溯与剪枝


递归、回溯与剪枝

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

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

使用到

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

“和最小”题目描述
? 设有一个长度为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

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

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

回溯。

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

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

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

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

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

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

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

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

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

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

没有其他更好的算法。


相关文章:
回溯递归练习题
回朔与递归 1.液晶数字排列:下面是用液晶七笔数字表示的十个数,我们把横、竖的一个短划都称为一笔。现 请你把这十个数重新排列,使从第二个数以后的每一...
递归与回溯练习题
递归回溯与剪枝 22页 免费 递归回溯搜索 81页 2财富值 递推-递归-分治-回溯...acm暑期练习7-递归练习等 6页 5财富值如要投诉违规内容,请到百度文库投诉中心;...
算法分析复习题(含答案)
(A)备忘录法 (B)动态规划法 (C)贪心法 (D)回溯法 21、下面哪种函数是回溯法中为避免无效搜索采取的策略( B )(A)递归函数 (B)剪枝函数 (C)随机数函数...
第三讲 递归与回溯法
第三讲 递归与回溯法_IT/计算机_专业资料。递归与回溯法 第三讲 递归与回溯法一、递归的概念 什么是递归?先看大家都熟悉的一个民间故事:从前有座山,山上有座...
合并递归回溯
合并递归回溯_学科竞赛_初中教育_教育专区。1、设有两个有序表 L1 和 L2(从小...C++ 递归和回溯 22页 2下载券 递归回溯与剪枝 22页 免费 递归与回溯算法 70...
0027算法笔记——【回溯法】回溯法与装载问题
常用剪枝函数:用约束函数在扩展结点处剪去不满足约束的子树;用限界函数剪去得不到最优解的子树。 递归回溯: 回溯法对解空间作深度优先搜索,因此,在一般情况下...
算法分析复习题目及答案[1]
下面哪种函数是回溯法中为避免无效搜索采取的策略( A.递归函数 B.剪枝函数 C。随机数函数 21、下面关于 NP 问题说法正确的是(B ) A NP 问题都是不可能解决...
算法分析复习题目及答案
下面哪种函数是回溯法中为避免无效搜索采取的策略( A.递归函数 B.剪枝函数 C。随机数函数 21、下面关于 NP 问题说法正确的是(B ) A NP 问题都是不可能解决...
回溯法解决迷宫问题
回溯法即以这种工作方式递归地在解空间中搜索, 直至找到所要求的解或解空间中...不过回溯算法使用剪枝函数,剪去一些不可能 到达 最终状态(即答案状态)的节点,...
算法分析复习题目及答案
下面哪种函数是回溯法中为避免无效搜索采取的策略( A.递归函数 B.剪枝函数 C。随机数函数 21、下面关于 NP 问题说法正确的是(B ) A NP 问题都是不可能解决...
更多相关标签:
回溯剪枝 | 回溯法 剪枝函数 | 带剪枝的回溯法 | 回溯剪枝法 | 背包问题回溯法剪枝 | 回溯与递归 | 递归回溯 | 递归回溯算法 |