1、1数据结构国家精品课程2022-12-22l以以N6，K2为例对一般问题求解。为例对一般问题求解。l可以穷举出共有可以穷举出共有15种不同的选择方案。假设成种不同的选择方案。假设成员名分别为员名分别为A、B、C、D、E和和F。l当问题规模很大时，用分治策略将问题分解为当问题规模很大时，用分治策略将问题分解为较简单的子问题。简化问题的第一步是将较简单的子问题。简化问题的第一步是将A从从小组中拿出，这样只剩下小组中拿出，这样只剩下B、C、D、E和和F。2数据结构国家精品课程2022-12-22l子问题子问题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)和和
3、(A，F)。l可以断定子问题可以断定子问题1和子问题和子问题2所得到的两人委员会包含了从原所得到的两人委员会包含了从原始问题得到的所有可能的委员会。始问题得到的所有可能的委员会。3数据结构国家精品课程2022-12-22委员会问题的递归算法委员会问题的递归算法算法算法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-12-22递归的应用回溯递归的应用回溯(backtr
4、acking)寻找特定问题解的一种比较可靠的方法是首先列出所寻找特定问题解的一种比较可靠的方法是首先列出所有候选解，然后依次检查每一个候选解，在检查完所有候选解，然后依次检查每一个候选解，在检查完所有或部分候选解后，即可找到所需要的解。有或部分候选解后，即可找到所需要的解。理论上，理论上，当候选解的数量有限并且通过检查所有或部分候选解当候选解的数量有限并且通过检查所有或部分候选解能够得到所需要的解的时候，上述方法是可行的。能够得到所需要的解的时候，上述方法是可行的。对候选解进行系统检查的方法有多种，其中对候选解进行系统检查的方法有多种，其中回溯回溯和分和分枝限界法是比较常用的两种。枝限界法是比
5、较常用的两种。6.4.2 回回 溯溯5数据结构国家精品课程2022-12-22l回溯法试图通过建立部分的解决方法来得到整回溯法试图通过建立部分的解决方法来得到整个问题的解决方案。该算法可将一个局部的解个问题的解决方案。该算法可将一个局部的解决方法扩展到整个问题。决方法扩展到整个问题。l如果从局部的解决方法肯定不能得到整个问题如果从局部的解决方法肯定不能得到整个问题的解决方案，也就是说局部的解将导致走进死的解决方案，也就是说局部的解将导致走进死胡同，这时就要通过移除最近加入的部分将算胡同，这时就要通过移除最近加入的部分将算法回退，并且尝试其他的方法。法回退，并且尝试其他的方法。6数据结构国家精品
6、课程2022-12-22回溯的基本思想是：为了求得问题的解，先选择某一回溯的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。索，如此反复进行，直至得到解或证明无解。回溯法解决的问题：回溯法解决的问题：货船装箱、背包、最大完备子图货船装箱、背包、最大完备子图、旅行商和电路板排列、旅行商和电路板排列7数据结构国家精品课程2022-12-22迷宫老鼠问题迷宫老鼠问题2,12,22,31,
7、11,21,33,13,23,38数据结构国家精品课程2022-12-22 0 0 0 0 1 1 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数据结构国家精品课程2022-12-22迷宫问题小型迷宫小型迷宫 路口 动作 结果(入口)正向走 进到 左拐弯 进到 右拐弯 进到 (堵死)回溯 退到 (堵死)回溯 退到 正向走 进到 (堵死)回溯 退到 右拐弯 进到 左拐弯 进到 (出口)764352110数据结构国家精品课程2022-12-22例：例：n-皇后问题皇后问题l在国际象棋
8、中，最强大的棋子是皇后，因在国际象棋中，最强大的棋子是皇后，因为她能攻击她所在行、所在列内或沿对角为她能攻击她所在行、所在列内或沿对角方向的任何一个棋子。方向的任何一个棋子。n-皇后问题要求在皇后问题要求在棋盘上放置棋盘上放置n个皇后，使得没有哪个皇后能个皇后，使得没有哪个皇后能攻击其他的皇后。攻击其他的皇后。11数据结构国家精品课程2022-12-22l在回溯中，由于每个皇后都必须放置在不同的行在回溯中，由于每个皇后都必须放置在不同的行中，所以中，所以n-皇后问题的解决方案可以表示为一个皇后问题的解决方案可以表示为一个n元组元组(x1,xn)，这里的，这里的xi 是把第是把第i个皇后放在第个
9、皇后放在第i行的列数且行的列数且1 xi n.由于任何两个皇后都不能出由于任何两个皇后都不能出现在同一列中，因此现在同一列中，因此n元组元组(x1,xn)中没有两个中没有两个元素是相同的。元素是相同的。l那么，应该如何判断两个皇后是否在同一斜角线那么，应该如何判断两个皇后是否在同一斜角线上呢？上呢？12数据结构国家精品课程2022-12-22 如果设想棋盘的方格像二维数组如果设想棋盘的方格像二维数组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、结构国家精品课程2022-12-22ln-皇后问题的解为一个皇后问题的解为一个n元组，使用一个大小为元组，使用一个大小为n的的数组数组queenInRow来存储。其中来存储。其中queenInRow k表表示 第示 第 k 行 的 第行 的 第 k 个 皇 后 所 在 列 的 位 置。例 如个 皇 后 所 在 列 的 位 置。例 如queenInRow 1=7表示第一个皇后被放在第表示第一个皇后被放在第1行、行、第第7列。列。l假设已经将第假设已经将第k-1个皇后放入第个皇后放入第k-1行中，接下来尝行中，接下来尝试将第试将第k个皇后放入第个皇后放入第k行的某一列。编写算法行的某一列。编写算法
12、PLACE(k,i.result)，当第，当第k个皇后能放置于第个皇后能放置于第k行行第第i列则返回列则返回true；否则返回；否则返回false。14数据结构国家精品课程2022-12-22算法算法PLACE要测试两种情况，即要测试两种情况，即queenInRow k是否不同于前面是否不同于前面queenInRow 1，queenInRowk 1的值以及在同一的值以及在同一条斜角线上是否有别的皇后。条斜角线上是否有别的皇后。15数据结构国家精品课程2022-12-22算法算法PLACE(k,i.result)/*如果一个皇后能放在第如果一个皇后能放在第k行第行第i列则返回列则返回true；否
13、则返回否则返回false，结果保存在，结果保存在result中中*/PLACE1 初始化初始化 j1.PLACE2 判定能否放置判定能否放置 16数据结构国家精品课程2022-12-22WHILE 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)是当前列是当前列/对所有的行执行循环语句对所有的行执行循环语句/移到下一列移到下一列当该位置不当该位置不能放皇后时能放皇后时转到下一列转到下一列/找到一个位置找到一个位置/否则转到下一行否则转到下一行/没有合适的位置没有合适的位置,回溯回溯
