递归、回溯与剪枝 王子琪、谭裕韦、刘丽颖
递归、回溯与剪枝 王子琪、谭裕韦、刘丽颖
递归与回溯 我们有时会碰到一些题目,它们既不能通 过建立数学模型解决,又没有现成算法可 以套用,或者必须遍历所有状况才可以得 出正确结果。这时,我们就必须采用搜索 算法来解决问题。 搜索算法按搜索的方式分有两类,一类是 深度优先搜索,一类是广度优先搜索。而 对于深度优先搜索来说,我们需要使用到 的一个技术就是递归与回溯
递归与回溯 ▪ 我们有时会碰到一些题目，它们既不能通 过建立数学模型解决，又没有现成算法可 以套用，或者必须遍历所有状况才可以得 出正确结果。 这时，我们就必须采用搜索 算法来解决问题。 ▪ 搜索算法按搜索的方式分有两类，一类是 深度优先搜索，一类是广度优先搜索。而 对于深度优先搜索来说，我们需要使用到 的一个技术就是递归与回溯
“和最小”题目描述 设有一个长度为N的数字串,要求使用K个 加号将它分成K+1个部分,找出一种分法, 使得这K+1个部分的和能够为最小。 n有一个数字串:312,当N=3,K=1时会有 以下两种分法: )3+12=15 2)31+2=33 这时,符合题目要求的结果是:3+12=15
“和最小”题目描述 ▪ 设有一个长度为N的数字串，要求使用K个 加号将它分成K+1个部分，找出一种分法， 使得这K+1个部分的和能够为最小。 ▪ 有一个数字串：312， 当N=3，K=1时会有 以下两种分法： ▪ 1) 3+12=15 ▪ 2) 31+2=33 ▪ 这时，符合题目要求的结果是：3+12=15
搜索策略 a题目要求的就是在每个数字之间 或者填加号,或者什么都不填。根 据这个要求,我们可以从头开始扫 描整个数字串,逐个考察是否要填 加号,然后检査下一个数字间的位 置,直到最后一个数字。 下面是一个例子和它的状态树
搜索策略 ▪ 题目要求的就是在每个数字之间： 或者填加号，或者什么都不填。根 据这个要求，我们可以从头开始扫 描整个数字串，逐个考察是否要填 加号，然后检查下一个数字间的位 置，直到最后一个数字。 ▪ 下面是一个例子和它的状态树
7和6之间 7和6之间 添加一个 不添加加 加号 7+6 76 7+6+2 7+62 76+2 762 7+6+2+9(7+6+29)(7+62+9X7+629)(76+2+9)(76+29)(762+97629 数字7629需要插入2个加号 这是一棵完整的搜索树 结点内表示当前处理的状态,每向后处理一个空位即 深入一层 我们可以看到,在最后的所有叶子结点中,有三个黄 色的结点是满足条件的
▪ 数字7629需要插入2个加号 ▪ 这是一棵完整的搜索树。 ▪ 结点内表示当前处理的状态，每向后处理一个空位即 深入一层。 ▪ 我们可以看到，在最后的所有叶子结点中，有三个黄 色的结点是满足条件的。 7+6+2+9 7 7+6 76 7+6+2 7+62 76+2 762 7+6+29 7+62+9 7+629 76+2+9 76+29 762+9 7629 7和6之间 不添加加 号 7和6之间 添加一个 加号
迷宫问题 n给出一个迷宫的地图,有一些格子中有障 碍,问从起点到终点的最短路径,并输出 所有的最短路径 ■回溯法解题思路 1、这个方向有路可走,我没走过,往 这个方向前进 2、是死胡同往回走回到上一个路口 3、重复第一步,直到找着出口
迷宫问题 ▪ 给出一个迷宫的地图，有一些格子中有障 碍，问从起点到终点的最短路径，并输出 所有的最短路径。 ▪ 回溯法解题思路 1、 这个方向有路可走，我没走过， 往 这个方向前进 2、 是死胡同,往回走,回到上一个路口 3、 重复第一步，直到找着出口
但是 ■回溯法的缺点暴露无遗: 搜索耗时极巨,无法忍受。 那么 我们可否提前判断我们前进的方向是 否可能得到最优解呢?如果可以的话 ,搜索效率岂不是能够提高了吗 答案就是: 剪枝!
但是 ▪ 回溯法的缺点暴露无遗： 搜索耗时极巨，无法忍受。 ▪ 那么 我们可否提前判断我们前进的方向是 否可能得到最优解呢？如果可以的话 ，搜索效率岂不是能够提高了吗 ▪ 答案就是： 剪枝！
关于剪枝 剪枝的概念,其实就跟走迷宫避开死胡同差不 多.。若我们把搜索的过程看成是对一棵树的遍 历,那么剪枝顾名思义,就是将树中的一些“死 胡同”,不能到达我们需要的解的枝条“剪” 掉,以减少搜索的时间 ■搜索算法,绝大部分需要用到剪枝。然而,不 是所有的枝条都可以剪掉,这就需要通过设计 出合理的判断方法,以决定某一分支的取舍。 在设计判断剪枝条件的时候,就需要有一定的 方法
关于剪枝 ▪ 剪枝的概念，其实就跟走迷宫避开死胡同差不 多.。若我们把搜索的过程看成是对一棵树的遍 历，那么剪枝顾名思义,就是将树中的一些“死 胡同”，不能到达我们需要的解的枝条“剪” 掉，以减少搜索的时间。 ▪ 搜索算法，绝大部分需要用到剪枝。 然而，不 是所有的枝条都可以剪掉，这就需要通过设计 出合理的判断方法，以决定某一分支的取舍。 在设计判断剪枝条件的时候，就需要有一定的 方法
最优性剪枝 又称为上下界剪枝 种重要的搜索剪枝策略 ■记录当前得到的最优值 n如果当前结点已经无法产生比当前 最优解更优的解时,可以提前回溯
最优性剪枝 ▪ 又称为上下界剪枝 ▪ 一种重要的搜索剪枝策略 ▪ 记录当前得到的最优值 ▪ 如果当前结点已经无法产生比当前 最优解更优的解时，可以提前回溯
回到加号题 儿子结点的数一定比父亲大 ■即搜索树深度越深得到的解越大 ■满足最优性剪枝的条件 ■我们可以记录当前得到的解的最小值 如果当前得到的和值已经超过保存的 最小解,即不必再继续深入搜索,回 溯
回到加号题 ▪ 儿子结点的数一定比父亲大 ▪ 即搜索树深度越深得到的解越大 ▪ 满足最优性剪枝的条件 ▪ 我们可以记录当前得到的解的最小值 ▪ 如果当前得到的和值已经超过保存的 最小解，即不必再继续深入搜索，回 溯
