数据结构-刘大有-第六章-递归1013.ppt

《数据结构-刘大有-第六章-递归1013.ppt》由会员分享，可在线阅读，更多相关《数据结构-刘大有-第六章-递归1013.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1数据结构国家精品课程2023/3/9l以以N6，K2为例对一般问题求解。为例对一般问题求解。l可可以以穷穷举举出出共共有有15种种不不同同的的选选择择方方案案。假假设设成成员名分别为员名分别为A、B、C、D、E和和F。l当当问问题题规规模模很很大大时时，用用分分治治策策略略将将问问题题分分解解为为较较简简单单的的子子问问题题。简简化化问问题题的的第第一一步步是是将将A从从小组中拿出，这样只剩下小组中拿出，这样只剩下B、C、D、E和和F。2数据结构国家精品课程2023/3/9l子问题子问题1：列列出出小小组组中中剩剩下下的的5个个人人组组成成2人人委委员员会会的的所所有有可可能能的的组组合合情

2、情况况。共共有有10种种不不同同的的子子委委员员会会，需需要要注注意意的的是是：每每个个新新的的委委员会都不包含缺席者员会都不包含缺席者A。l子问题子问题2：列列出出小小组组中中剩剩下下的的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数据结构国家精品课程2023/3/9委员会问题的递归算法委员会问题的递归算法算法算法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数据结构国家精品课程2023/3/9递归的应用回溯递归的应用回溯(backtracking)寻寻找找特特定定问问题题解解的的

4、一一种种比比较较可可靠靠的的方方法法是是首首先先列列出出所所有有候候选选解解，然然后后依依次次检检查查每每一一个个候候选选解解，在在检检查查完完所所有有或或部部分分候候选选解解后后，即即可可找找到到所所需需要要的的解解。理理论论上上，当当候候选选解解的的数数量量有有限限并并且且通通过过检检查查所所有有或或部部分分候候选选解解能够得到所需要的解的时候，上述方法是可行的。能够得到所需要的解的时候，上述方法是可行的。对对候候选选解解进进行行系系统统检检查查的的方方法法有有多多种种，其其中中回回溯溯和和分分枝限界法是比较常用的两种。枝限界法是比较常用的两种。6.4.2 回回 溯溯5数据结构国家精品课程

5、2023/3/9l回回溯溯法法试试图图通通过过建建立立部部分分的的解解决决方方法法来来得得到到整整个个问问题题的的解解决决方方案案。该该算算法法可可将将一一个个局局部部的的解解决方法扩展到整个问题。决方法扩展到整个问题。l如如果果从从局局部部的的解解决决方方法法肯肯定定不不能能得得到到整整个个问问题题的的解解决决方方案案，也也就就是是说说局局部部的的解解将将导导致致走走进进死死胡胡同同，这这时时就就要要通通过过移移除除最最近近加加入入的的部部分分将将算算法回退，并且尝试其他的方法。法回退，并且尝试其他的方法。6数据结构国家精品课程2023/3/9回回溯溯的的基基本本思思想想是是：为为了了求求得

6、得问问题题的的解解，先先选选择择某某一一种种可可能能情情况况向向前前探探索索，在在探探索索过过程程中中，一一旦旦发发现现原原来来的的选选择择是是错错误误的的，就就退退回回一一步步重重新新选选择择，继继续续向向前前探探索，如此反复进行，直至得到解或证明无解。索，如此反复进行，直至得到解或证明无解。回回溯溯法法解解决决的的问问题题：货货船船装装箱箱、背背包包、最最大大完完备备子子图图、旅行商和电路板排列旅行商和电路板排列7数据结构国家精品课程2023/3/9迷宫老鼠问题迷宫老鼠问题2,12,22,31,11,21,33,13,23,38数据结构国家精品课程2023/3/9 0 0 0 0 1 1

7、0 0 0 1 1 1 0 1 1 0 0 0(1,1)(1,2)(1,3)失败失败，回溯回溯到到(1,2)(1,1)(2,1)(3,1)(3,2)(3,3)9数据结构国家精品课程2023/3/9迷宫问题小型迷宫小型迷宫 路口 动作 结果 1 1(入口)正向走 进到 2 2 2 2 左拐弯 进到 3 3 3 3 右拐弯 进到 4 4 4 4(堵死)回溯 退到 3 3 3 3(堵死)回溯 退到 2 2 2 2 正向走 进到 5 5 5 5(堵死)回溯 退到 2 2 2 2 右拐弯 进到 6 6 6 6 左拐弯 进到 7 7 (出口)764352110数据结构国家精品课程2023/3/9例：例：n

8、-皇后问题皇后问题l在在国国际际象象棋棋中中，最最强强大大的的棋棋子子是是皇皇后后，因因为为她她能能攻攻击击她她所所在在行行、所所在在列列内内或或沿沿对对角角方方向向的的任任何何一一个个棋棋子子。n-皇皇后后问问题题要要求求在在棋棋盘盘上上放放置置n个个皇皇后后，使使得得没没有有哪哪个个皇皇后后能能攻攻击其他的皇后。击其他的皇后。11数据结构国家精品课程2023/3/9l在在回回溯溯中中，由由于于每每个个皇皇后后都都必必须须放放置置在在不不同同的的行行中中，所所以以n-皇皇后后问问题题的的解解决决方方案案可可以以表表示示为为一一个个n元元组组(x1,xn)，这这里里的的xi 是是把把第第i个个

9、皇皇后后放放在在第第i行行的的列列数数且且1 xi n.由由于于任任何何两两个个皇皇后后都都不不能能出出现现在在同同一一列列中中，因因此此n元元组组(x1,xn)中中没没有有两两个个元素是相同的。元素是相同的。l那那么么，应应该该如如何何判判断断两两个个皇皇后后是是否否在在同同一一斜斜角角线线上呢？上呢？12数据结构国家精品课程2023/3/9 如如果果设设想想棋棋盘盘的的方方格格像像二二维维数数组组A(1:n,1:n)的的下下标标那那样样标标记记，对对于于在在同同一一条条斜斜角角线线上上的的由由左左上上方方到到右右下下方方的的每每一一个个元元素素都都有有相相同同的的“行行 列列”值值，同同样

10、样，在在同同一一条条上上的的由由右右上上方方到到左左下下方方的的每每一一个个元元素素则则有有相相同同的的“行行+列列”值值。假假设设有有两两个个皇皇后后被被放放置置在在(i,j)和和(k,l)位置上，那么根据以上所述，仅当位置上，那么根据以上所述，仅当 i j k l 或或 i+j k+l时时，它它们们才才在在同同一一条条斜斜角角线线上上。将将这这两两个个等等式式分分别别变换成变换成 j l i k 或或 j l k i因因此此，当当且且仅仅当当|j l|i k|时时，两两个个皇皇后后在在同同一条斜角线上，这里的一条斜角线上，这里的|j l|为为j l的绝对值。的绝对值。13数据结构国家精品课

11、程2023/3/9ln-皇皇后后问问题题的的解解为为一一个个n元元组组，使使用用一一个个大大小小为为n的的数数组组queenInRow来来存存储储。其其中中queenInRow k表表示示 第第 k行行 的的 第第 k个个 皇皇 后后 所所 在在 列列 的的 位位 置置。例例 如如queenInRow 1=7表表示示第第一一个个皇皇后后被被放放在在第第1行行、第第7列。列。l假假设设已已经经将将第第k-1个个皇皇后后放放入入第第k-1行行中中，接接下下来来尝尝试试将将第第k个个皇皇后后放放入入第第k行行的的某某一一列列。编编写写算算法法PLACE(k,i.result)，当当第第k个个皇皇后后

12、能能放放置置于于第第k行行第第i列则返回列则返回true；否则返回；否则返回false。14数据结构国家精品课程2023/3/9算法算法PLACE要测试两种情况，即要测试两种情况，即queenInRow k是否不同于前面是否不同于前面queenInRow 1，queenInRowk 1的值以及在同一的值以及在同一条斜角线上是否有别的皇后。条斜角线上是否有别的皇后。15数据结构国家精品课程2023/3/9算法算法PLACE(k,i.result)/*如果一个皇后能放在第如果一个皇后能放在第k行第行第i列则返回列则返回true；否则返回否则返回false，结果保存在，结果保存在result中中*/

13、PLACE1 初始化初始化 j1.PLACE2 判定能否放置判定能否放置 16数据结构国家精品课程2023/3/9WHILE j 0)do X(k)X(k)+1;while(X(k)n and Not PLACE(k)do X(k)X(k)+1;repeat if (X(k)n)then if (k=n)then print(X);else kk+1;X(k)0;endif else kk-1;endifrepeatend NQUEENS/若是一个完整的解则打印数组若是一个完整的解则打印数组X/k是当前行是当前行;X(k)是当前列是当前列/对所有的行执行循环语句对所有的行执行循环语句/移到下一列移到下一列当该位置不当该位置不能放皇后时能放皇后时转到下一列转到下一列/找到一个位置找到一个位置/否则转到下一行否则转到下一行/没有合适的位置没有合适的位置,回溯回溯