递归、回溯与剪枝 王子琪、谭裕韦、刘丽颖
递归、回溯与剪枝 王子琪、谭裕韦、刘丽颖
递归与回溯 我们有时会碰到一些题目,它们既不能通 过建立数学模型解决,又没有现成算法可 以套用,或者必须遍历所有状况才可以得 出正确结果。这时,我们就必须采用搜索 算法来解决问题。 搜索算法按搜索的方式分有两类,一类是 深度优先搜索,一类是广度优先搜索。而 对于深度优先搜索来说,我们需要使用到 的一个技术就是递归与回溯
递归与回溯 ▪ 我们有时会碰到一些题目，它们既不能通 过建立数学模型解决，又没有现成算法可 以套用，或者必须遍历所有状况才可以得 出正确结果。 这时，我们就必须采用搜索 算法来解决问题。 ▪ 搜索算法按搜索的方式分有两类，一类是 深度优先搜索，一类是广度优先搜索。而 对于深度优先搜索来说，我们需要使用到 的一个技术就是递归与回溯
“和最小”题目描述 设有一个长度为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之间 添加一个 加号