数据结构-刘大有-第六章-递归优秀PPT.ppt
《数据结构-刘大有-第六章-递归优秀PPT.ppt》由会员分享,可在线阅读,更多相关《数据结构-刘大有-第六章-递归优秀PPT.ppt(18页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1数据结构国家精品课程2022/11/2l以以N6,K2为例对一般问题求解。为例对一般问题求解。l可可以以穷穷举举出出共共有有15种种不不同同的的选选择择方方案案。假假设设成成员名分别为员名分别为A、B、C、D、E和和F。l当当问问题题规规模模很很大大时时,用用分分治治策策略略将将问问题题分分解解为为较较简简洁洁的的子子问问题题。简简化化问问题题的的第第一一步步是是将将A从从小组中拿出,这样只剩下小组中拿出,这样只剩下B、C、D、E和和F。2数据结构国家精品课程2022/11/2l子问题子问题1:l列列出出小小组组中中剩剩下下的的5个个人人组组成成2人人委委员员会会的的全全部部可可能能的的组组
2、合合状状况况。共共有有10种种不不同同的的子子委委员员会会,须须要要留留意意的的是是:每每个个新新的委员会都不包含缺席者的委员会都不包含缺席者A。l子问题子问题2:l列列出出小小组组中中剩剩下下的的5个个人人组组成成1人人委委员员会会的的全全部部可可能能状状况况。明明显显,共共有有5种种状状况况,即即:(B),(C),(D),(E)和和(F)。每每个个委委员员会会要要组组成成2人人小小组组还还缺缺1人人。将将成成员员A加加入入其其中中,它它们们即即可可变变成成两两人人委委员员会会。这这些些两两人人委委员员会会为为:(A,B),(A,C),(A,D),(A,E)和和(A,F)。l可可以以断断定定
3、子子问问题题1和和子子问问题题2所所得得到到的的两两人人委委员员会会包包含含了了从从原原始问题得到的全部可能的委员会。始问题得到的全部可能的委员会。3数据结构国家精品课程2022/11/2委员会问题的递归算法委员会问题的递归算法算法算法COMM(n,k)COMM1递归出口递归出口 IF k n THEN RETURN(0).ELSE IF(n=k OR k=0)THEN RETURN(1).COMM2递归调用递归调用RETURN(COMM(n-1,k)+COMM(n-1,k-1)4数据结构国家精品课程2022/11/2递归的应用回溯递归的应用回溯(backtracking)找寻特定问题解的一种
4、比较牢靠的方法是首先找寻特定问题解的一种比较牢靠的方法是首先列出全部候选解,然后依次检查每一个候选解,列出全部候选解,然后依次检查每一个候选解,在检查完全部或部分候选解后,即可找到所须在检查完全部或部分候选解后,即可找到所须要的解。要的解。理论上,当候选解的数量有限并且通理论上,当候选解的数量有限并且通过检查全部或部分候选解能够得到所须要的解过检查全部或部分候选解能够得到所须要的解的时候,上述方法是可行的。的时候,上述方法是可行的。对候选解进行对候选解进行系统检查的方法有多种,其中回溯和分枝限界系统检查的方法有多种,其中回溯和分枝限界法是比较常用的两种。法是比较常用的两种。6.4.2 回回 溯
5、溯5数据结构国家精品课程2022/11/2l回回溯溯法法试试图图通通过过建建立立部部分分的的解解决决方方法法来来得得到到整整个个问问题题的的解解决决方方案案。该该算算法法可可将将一一个个局局部部的的解解决方法扩展到整个问题。决方法扩展到整个问题。l假假如如从从局局部部的的解解决决方方法法确确定定不不能能得得到到整整个个问问题题的的解解决决方方案案,也也就就是是说说局局部部的的解解将将导导致致走走进进死死胡胡同同,这这时时就就要要通通过过移移除除最最近近加加入入的的部部分分将将算算法回退,并且尝试其他的方法。法回退,并且尝试其他的方法。6数据结构国家精品课程2022/11/2回回溯溯的的基基本本
6、思思想想是是:为为了了求求得得问问题题的的解解,先先选选择择某某一一种种可可能能状状况况向向前前探探究究,在在探探究究过过程程中中,一一旦旦发发觉觉原原来来的的选选择择是是错错误误的的,就就退退回回一一步步重重新新选选择择,接接着着向向前前探探究,如此反复进行,直至得到解或证明无解。究,如此反复进行,直至得到解或证明无解。回回溯溯法法解解决决的的问问题题:货货船船装装箱箱、背背包包、最最大大完完备备子子图图、旅行商和电路板排列旅行商和电路板排列7数据结构国家精品课程2022/11/2迷宫老鼠问题迷宫老鼠问题2,12,22,31,11,21,33,13,23,38数据结构国家精品课程2022/1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 大有 第六 递归 优秀 PPT
限制150内