递归回溯与剪枝ppt课件.ppt
《递归回溯与剪枝ppt课件.ppt》由会员分享,可在线阅读,更多相关《递归回溯与剪枝ppt课件.ppt(22页珍藏版)》请在三一办公上搜索。
1、递归、回溯与剪枝,递归与回溯,我们有时会碰到一些题目,它们既不能通过建立数学模型解决,又没有现成算法可以套用,或者必须遍历所有状况才可以得出正确结果。 这时,我们就必须采用搜索算法来解决问题。搜索算法按搜索的方式分有两类,一类是深度优先搜索,一类是广度优先搜索。而对于深度优先搜索来说,我们需要使用到的一个技术就是递归与回溯。,“和最小”题目描述,设有一个长度为N的数字串,要求使用K个加号将它分成K+1个部分,找出一种分法,使得这K+1个部分的和能够为最小。有一个数字串:312, 当N=3,K=1时会有以下两种分法:1) 3+12=152) 31+2=33 这时,符合题目要求的结果是:3+12=
2、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,参数表); 恢复:保存结果之前的状
3、态回溯一步 end;end;,搜索策略,题目要求的就是在每个数字之间:或者填加号,或者什么都不填。根据这个要求,我们可以从头开始扫描整个数字串,逐个考察是否要填加号,然后检查下一个数字间的位置,直到最后一个数字。下面是一个例子和它的状态树,数字7629需要插入2个加号这是一棵完整的搜索树。结点内表示当前处理的状态,每向后处理一个空位即深入一层。我们可以看到,在最后的所有叶子结点中,有三个黄色的结点是满足条件的。,7和6之间不添加加号,7和6之间添加一个加号,迷宫问题,给出一个迷宫的地图,有一些格子中有障碍,问从起点到终点的最短路径,并输出所有的最短路径。回溯法解题思路1、这个方向有路可走,我没
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归 回溯 剪枝 ppt 课件
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-1364541.html