递归回溯与剪枝

递归回溯与剪枝第一页，共三十三页，编辑于2023年，星期五递归与回溯我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者必须遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。而对于深度优先搜索来说，我们需要使用到的一个技术就是递归与回溯。第二页，共三十三页，编辑于2023年，星期五回溯法（试探法），在问题的解空间中，将问题的所有候选解按某种顺序逐一枚举和检验，从而找到符合要求的解的集合或最优解。关键词：向前试探，回溯递归法为求解规模为N的问题，设法将它分解成一些规模较小的问题，然后从这些较小的问题方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，特别的，当N=1时，能够直接得到解。关键词：递进，回归问题分析（代码架构）回溯法递归法栈第三页，共三十三页，编辑于2023年，星期五常见的剪枝的方法限界剪枝法最优性剪枝可行性剪枝奇偶剪枝第四页，共三十三页，编辑于2023年，星期五“和最小”题目描述设有一个长度为N的数字串，要求使用K个加号将它分成K+1个部分，找出一种分法，使得这K+1个部分的和能够为最小。有一个数字串：312，当N=3，K=1时会有以下两种分法：1)3+12=152)31+2=33

这时，符合题目要求的结果是：3+12=15第五页，共三十三页，编辑于2023年，星期五递归回溯法算法框架[一]procedureSearch(k:integer);beginfori:=1to算符种数Doif满足条件thenbegin

保存结果

if到目的地then输出解

elseSearch(k+1);

恢复：保存结果之前的状态{回溯一步}end;end;第六页，共三十三页，编辑于2023年，星期五递归回溯法算法框架[二]procedureSearch(k:integer);beginif到目的地then输出解

elsefori:=1to算符种数Doif满足条件thenbegin

保存结果

Search(k+1,参数表); end;end;第七页，共三十三页，编辑于2023年，星期五搜索策略题目要求的就是在每个数字之间：或者填加号，或者什么都不填。根据这个要求，我们可以从头开始扫描整个数字串，逐个考察是否要填加号，然后检查下一个数字间的位置，直到最后一个数字。下面是一个例子和它的状态树第八页，共三十三页，编辑于2023年，星期五数字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之间添加一个加号第九页，共三十三页，编辑于2023年，星期五迷宫问题给出一个迷宫的地图，有一些格子中有障碍，问从起点到终点的最短路径，并输出所有的最短路径。回溯法解题思路1、

这个方向有路可走，我没走过，

往这个方向前进2、

是死胡同,往回走,回到上一个路口3、

重复第一步，直到找着出口第十页，共三十三页，编辑于2023年，星期五但是回溯法的缺点暴露无遗：搜索耗时极巨，无法忍受。那么我们可否提前判断我们前进的方向是否可能得到最优解呢？如果可以的话，搜索效率岂不是能够提高了吗答案就是：剪枝！第十一页，共三十三页，编辑于2023年，星期五关于剪枝剪枝的概念，其实就跟走迷宫避开死胡同差不多.。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义,就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。搜索算法，绝大部分需要用到剪枝。

然而，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。

在设计判断剪枝条件的时候，就需要有一定的方法。

第十二页，共三十三页，编辑于2023年，星期五最优性剪枝又称为上下界剪枝一种重要的搜索剪枝策略记录当前得到的最优值如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯第十三页，共三十三页，编辑于2023年，星期五回到加号题儿子结点的数一定比父亲大即搜索树深度越深得到的解越大满足最优性剪枝的条件我们可以记录当前得到的解的最小值如果当前得到的和值已经超过保存的最小解，即不必再继续深入搜索，回溯。第十四页，共三十三页，编辑于2023年，星期五再看搜索树我们可以看到红色结点的子节点不可能有最优解

77+6

767+6+27+6276+2

7627+62+97+62976+2+976+29

7629762+97+6+2+97+6+29第十五页，共三十三页，编辑于2023年，星期五最优性剪枝结果结点数大大减少。

77+6767+6+27+627+6+2+97+6+29第十六页，共三十三页，编辑于2023年，星期五可行性剪枝除最优性剪枝外，另一种重要的搜索剪枝策略判断继续搜索能否得出答案，如果不能直接回溯第十七页，共三十三页，编辑于2023年，星期五再看搜索树对于图中蓝色结点。后面能够插入’+’的位置已经少于未用完’+’的数量，肯定不可能有解。对于这种结点，其子节点不可能有解，可以回溯。这个节点的加号不可能有解,可以进行可行性剪枝

77+6

767+6+27+6276+2

7627+62+97+62976+2+976+29

7629762+97+6+2+97+6+29第十八页，共三十三页，编辑于2023年，星期五迷宫问题最优性剪枝我们可以将每一次搜索出的路径长度与上界比较（初始上界＝∞），不断降低上界，一旦出现路径长超出上界而仍未到达目标点，则放弃该搜索进程。因为就算继续搜索下去，这一条路径也必然比其他路径长，不是最优解。第十九页，共三十三页，编辑于2023年，星期五总结深度优先搜索的程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；所以，如何用正确的方法对程序进行优化，就成为搜索算法编程中最关键的一环。那么，剪枝就是搜索优化中最基本的方法之一。第二十页，共三十三页，编辑于2023年，星期五总结两种常用的剪枝方法：最优性剪枝适用范围：子结点的代价全部高于或低于父结点又之称为多米诺性质。可行性剪枝根据题意作出判断是否继续搜索还有可能得到解第二十一页，共三十三页，编辑于2023年，星期五剪枝的原则1.正确性：必须保证不丢失正确的结果。2.准确性：能够尽可能多的减去不能通向正解的枝条3.高效性：在很多时候，为了加强优化的效果，我们会增加一些判断，这样对程序效率也带来了副作用，所以要考虑剪枝的高效性，否则得不偿失。第二十二页，共三十三页，编辑于2023年，星期五总结在搜索算法中，几乎都需要采用程序优化,以减少时间复杂度。而这里所说的两种剪枝方法，是最常见的优化方法之一。然而，尽管可以采用众多优化算法使得程序的效率有所提高，搜索算法本身的时间复杂度不能从本质上减少是不可改变的事实。不妨在使用搜索算法之前先仔细想想，有没有其他更好的算法。第二十三页，共三十三页，编辑于2023年，星期五坚持就有希望，努力就有回报！目标都能实现！梦想都能成真！第二十四页，共三十三页，编辑于2023年，星期五演讲稿的写法

七个阶段的准备

一、决定话题和目的二、分析听众和场合三、满足听众的本能欲求四、收集材料五、编制提纲六、练习词语七、练习篇章第二十五页，共三十三页，编辑于2023年，星期五一、演说者和听众分析

1、演说的成败，首先决定于演说者的良好心理素质和充分准备。必须克服羞怯、拘谨、冷谈、自卑，做到勇敢、轻松、亲切、自信。任何演讲都必须有满腔热情和必胜的信心。

2、在演讲前对听众的人数、年纪、性别、教育程度、有关话题的、关注焦点和愿望、固定的态度和信仰等要进行调查，做到有的放矢，才可能收到理想的效果。

3、在演说过程中，必须目视听众，必须察言观色，注意听众情绪反应做适当的点整。第二十六页，共三十三页，编辑于2023年，星期五二、确定目的和选择话题

1、目的要么让人快乐；要么给人知识；要么让人行动；社交是联络感情，鉴赏目的是让人快乐、让人感动。可概括三大主要目的:知行目的，人际目的，语篇目的。

2、话题要令人亲近、关注，因此要具有社会性，特别要关注社会的热点。要明确、集中、正确、易懂，要有一定得形象性。要具有针对性，针对某种意见做辩答，或解决某个要解决问题，或针对某些人思想情绪。第二十七页，共三十三页，编辑于2023年，星期五三、文字口语化，语言的节奏感演讲的声音稍纵即逝，因而演讲稿必须要写得入耳。

1、多用群众创造的形象生动的语言演讲要尽量把不易听懂的书面语言改为口语，如书面语“对垒”、“角逐”改为“比赛”、“竞争”等口语。

2、避免同音相混的语言如期中---期终；终年----中年；全部---全不等

3、多用象声语言如，载重超负荷-----装多了，车压得吱吱的响；不说“正、草、隶、篆他会写”应改为“什么正楷啦，草书啦，隶书啦，篆书啦他全部会写”第二十八页，共三十三页，编辑于2023年，星期五四、演讲稿的开头1、提问开头法有这样一个问题常在我的脑海里萦回：是什么力量使爱因斯坦名扬天下之后仍在攀登科学高峰呢？是什么力量使张海迪在死神缠绕之时仍锐志奋进呢？，这大概是当代青年，特别是我们大学生讨论最多的问题之一，也是我今天演讲的题目。第二十九页，共三十三页，编辑于2023年，星期五2、套近乎开头林肯的演说：听说在场的就有些人要下决心和我作对，我实在不明白为什么要这样做，我也和你们一样是一位爽直的平民，我为什么不能和你们一样有发表意见的权力呢？好朋友，我不是来干涉你们的，我是你们中间的一员。第三十页，共三十三页，编辑于2023年，星期五

3、引用入题法同学们，有一首诗这样写道：“多少人爱你青春欢畅的时候，爱慕你的美丽，也许假意或真心。只要我爱你朝圣者的灵魂，爱你衰老的脸上脸上的痛苦的皱纹。”诗中倾诉的是深沉真挚的爱，正如别林基斯所说：“爱是理解的别名。”知之愈深，才能爱之愈切，今天，带着这种爱，我要讲一讲我的祖国，讲一讲生我的这片土地。第三十一页，共三十三页，编辑于2023年，星期五

4、开门见山我主张将我们全党的学习方法和学习制度改造一下。（改造我们的学习）

5、悬念开头法刚才，我会见了一个欧洲代表团，他们问我对一部分先富起来的政策持什么看法。我对特们说，这个问题我已经不感兴趣了！因为，这已经成为现实了！他们接着问我，那你对什么感兴趣？我对他们说，我对一部分县富