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

递归回溯与剪枝


递归、回溯与剪枝

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

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

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

“和最小”题目描述
? 设有一个长度为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、设有两个有序表 L1 和 L2(从小...C++ 递归和回溯 22页 2下载券 递归回溯与剪枝 22页 免费 递归与回溯算法 70...
递归法和回溯法
递归和回溯递归和回溯法隐藏>> 递归和回溯法 有人说,回溯实际上是递归的展开,但实际上。两者的指导思想并不一致。 打个比方吧,递归法好比是一个军队...
回溯法求装载问题_物联1301班_刘悦_201308080112
回溯法求装载问题_物联1301班_刘悦_201308080112_工学_高等教育_教育专区。算法...进入左子树/右子树之后调用本身进行递归剪枝策略: 将剩余的集装箱都装上...
n皇后问题是递归和回溯法的一个典型应用
[ col ] = false; } 关于 guarded 还有一点说明: 由于回溯法中的剪枝函数 ...int Site[QUEENS]; //!递归求解的函数。 void Queen(int n); //!输出一...
回溯算例
这类 问题一般只能借助搜索与回溯算法求解。 回溯法的基本思想是 回溯算法求解 ...并且在搜索过程中用剪枝函数避免无效搜索; 3、递归回溯:由于回溯法是对解空间的...
回溯法实验(最大团问题)
程序中采用了一个比较简单的剪枝策略, 即如果剩余未考虑的顶点数加上 团中顶点数不大于当前解的顶点数, 可停止继续深度搜索, 否则继续深度递归 当搜索到一个叶...
回溯法 java
或建议本次实验虽为回溯法,但却有动态规划的思想。回溯法也有子问题,可 以用递归实现。回溯法与动态规划的不同在于回溯法拥有剪枝函数,可以缩 短很大的计算量,...
回溯法与分支限界法的分析与比较
的解空间结构; (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免...在一般情况下用递归方法实现回溯法的基本框架如下: void backtrack (int t) {...
算法分析复习题目及答案[1]
下面哪种函数是回溯法中为避免无效搜索采取的策略( A.递归函数 B.剪枝函数 C。随机数函数 21、下面关于 NP 问题说法正确的是(B ) A NP 问题都是不可能解决...
搜索与回溯算法介绍
(3)以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无 效搜索; ...【递归回溯递归回溯】 由于回溯法是对解空间的深度优先搜索, 因此在一般情况...
更多相关标签: