递归回溯与剪枝ppt课件.ppt
经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用递归与回溯递归与回溯我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者必须遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。而对于深度优先搜索来说，我们需要使用到的一个技术就是递归与回溯。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用“和最小和最小”题目描述题目描述设有一个长度为N的数字串，要求使用K个加号将它分成K+1个部分，找出一种分法，使得这K+1个部分的和能够为最小。有一个数字串：312，当N=3，K=1时会有以下两种分法：1)3+12=152)31+2=33这时，符合题目要求的结果是：3+12=15经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用递归回溯法算法框架递归回溯法算法框架一一procedure Search(k:integer);Var ibegin for i:=1 to 算符种数算符种数 Do if 满足条件满足条件 then begin 保存结果保存结果 if 到目的地到目的地 then 输出解输出解 else Search(k+1);恢复：保存结果之前的状态恢复：保存结果之前的状态回溯一步回溯一步 end;end;经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用递归回溯法算法框架递归回溯法算法框架 二二 procedure Search(k:integer);Var ibegin if 到目的地到目的地 then 输出解输出解 else for i:=1 to 算符种数算符种数 Do if 满足条件满足条件 then begin 保存结果保存结果 Search(k+1,参数表参数表);恢复：保存结果之前的状态恢复：保存结果之前的状态回溯一步回溯一步 end;end;经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用搜索策略搜索策略题目要求的就是在每个数字之间：或者填加号，或者什么都不填。根据这个要求，我们可以从头开始扫描整个数字串，逐个考察是否要填加号，然后检查下一个数字间的位置，直到最后一个数字。下面是一个例子和它的状态树经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用数字7629需要插入2个加号这是一棵完整的搜索树。结点内表示当前处理的状态，每向后处理一个空位即深入一层。我们可以看到，在最后的所有叶子结点中，有三个黄色的结点是满足条件的。7+6+2+9 77+6 767+6+27+6276+2 7627+62+97+62976+2+976+29 7629762+97+6+297和和6之间之间不添加加不添加加号号7和和6之间之间添加一个添加一个加号加号经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用迷宫问题迷宫问题给出一个迷宫的地图，有一些格子中有障碍，问从起点到终点的最短路径，并输出所有的最短路径。回溯法解题思路1、这个方向有路可走，我没走过，往这个方向前进2、是死胡同,往回走,回到上一个路口3、重复第一步，直到找着出口经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用但是但是回溯法的缺点暴露无遗：搜索耗时极巨，无法忍受。那么我们可否提前判断我们前进的方向是否可能得到最优解呢？如果可以的话，搜索效率岂不是能够提高了吗答案就是：剪枝！经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用关于剪枝关于剪枝剪枝的概念，其实就跟走迷宫避开死胡同差不多.。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义,就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。搜索算法，绝大部分需要用到剪枝。然而，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。在设计判断剪枝条件的时候，就需要有一定的方法。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用最优性剪枝最优性剪枝又称为上下界剪枝一种重要的搜索剪枝策略记录当前得到的最优值如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用回到加号题回到加号题儿子结点的数一定比父亲大即搜索树深度越深得到的解越大满足最优性剪枝的条件我们可以记录当前得到的解的最小值如果当前得到的和值已经超过保存的最小解，即不必再继续深入搜索，回溯。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用再看搜索树再看搜索树我们可以看到红色结点的子节点不可能有最优解 77+6 767+6+27+6276+2 7627+62+97+62976+2+976+29 7629762+97+6+2+97+6+29经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用最优性剪枝结果最优性剪枝结果结点数大大减少。77+6 767+6+27+627+6+2+97+6+29经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用可行性剪枝可行性剪枝除最优性剪枝外，另一种重要的搜索剪枝策略判断继续搜索能否得出答案，如果不能直接回溯经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用再看搜索树再看搜索树对于图中蓝色结点。后面能够插入+的位置已经少于未用完+的数量，肯定不可能有解。对于这种结点，其子节点不可能有解，可以回溯。这个节点的这个节点的加号不可能加号不可能有解有解,可以进可以进行可行性剪行可行性剪枝枝 77+6 767+6+27+6276+2 7627+62+97+62976+2+976+29 7629762+97+6+2+97+6+29经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用迷宫问题迷宫问题最优性剪枝我们可以将每一次搜索出的路径长度与上界比较（初始上界），不断降低上界，一旦出现路径长超出上界而仍未到达目标点，则放弃该搜索进程。因为就算继续搜索下去，这一条路径也必然比其他路径长，不是最优解。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用总结总结深度优先搜索的程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；所以，如何用正确的方法对程序进行优化，就成为搜索算法编程中最关键的一环。那么，剪枝就是搜索优化中最基本的方法之一。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用总结总结两种常用的剪枝方法：最优性剪枝适用范围：子结点的代价全部高于或低于父结点又之称为多米诺性质。可行性剪枝根据题意作出判断是否继续搜索还有可能得到解经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用剪枝的原则剪枝的原则正确性准确性高效性经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用总结总结在搜索算法中，几乎都需要采用程序优化,以减少时间复杂度。而这里所说的两种剪枝方法，是最常见的优化方法之一。然而，尽管可以采用众多优化算法使得程序的效率有所提高，搜索算法本身的时间复杂度不能从本质上减少是不可改变的事实。不妨在使用搜索算法之前先仔细想想，有没有其他更好的算法。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用
