数据结构 刘大有 第六章 递归1013(精品·公开课件).pptVIP

* 《数据结构》国家精品课程 * 6.4 递归法求解问题 6.4.1 委员会问题 组合数学用于解决给定事件会以多少种方式发生的问题。 以经典的委员会问题为例，给出非负整数N和K，求从N个人中选出K个成员组成一个委员会的方法总数，即C(N, K)。 以N＝6，K＝2为例对一般问题求解。 可以穷举出共有15种不同的选择方案。假设成员名分别为A、B、C、D、E和F。 当问题规模很大时，用分治策略将问题分解为较简单的子问题。简化问题的第一步是将A从小组中拿出，这样只剩下B、C、D、E和F。 子问题1： 列出小组中剩下的5个人组成2人委员会的所有可能的组合情况。共有10种不同的子委员会，需要注意的是：每个新的委员会都不包含缺席者A。 子问题2： 列出小组中剩下的5个人组成1人委员会的所有可能情况。显然，共有5种情况，即：(B)，(C)，(D)，(E)和(F)。每个委员会要组成2人小组还缺1人。将成员A加入其中，它们即可变成两人委员会。这些两人委员会为：(A，B)，(A，C)，(A，D)，(A，E)和(A，F)。 可以断定子问题1和子问题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))? 递归的应用－－回溯(backtracking) 寻找特定问题解的一种比较可靠的方法是首先列出所有候选解，然后依次检查每一个候选解，在检查完所有或部分候选解后，即可找到所需要的解。 理论上，当候选解的数量有限并且通过检查所有或部分候选解能够得到所需要的解的时候，上述方法是可行的。 对候选解进行系统检查的方法有多种，其中回溯和分枝限界法是比较常用的两种。 6.4.2 回 溯 回溯法试图通过建立部分的解决方法来得到整个问题的解决方案。该算法可将一个局部的解决方法扩展到整个问题。 如果从局部的解决方法肯定不能得到整个问题的解决方案，也就是说局部的解将导致走进死胡同，这时就要通过移除最近加入的部分将算法回退，并且尝试其他的方法。 回溯的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。 回溯法解决的问题：货船装箱、背包、最大完备子图、旅行商和电路板排列 迷宫老鼠问题 2,1 2,2 2,3 1,1 1,2 1,3 3,1 3,2 3,3 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) 迷宫问题 小型迷宫 路口 动作 结果 1(入口) 正向走 进到 2 2 左拐弯 进到 3 3 右拐弯 进到 4 4(堵死) 回溯 退到 3 3(堵死) 回溯 退到 2 2 正向走 进到 5 5(堵死) 回溯 退到 2 2 右拐弯 进到 6 6 左拐弯 进到 7 (出口) 7 6 4 3 5 2 1 例：n-皇后问题 在国际象棋中，最强大的棋子是皇后，因为她能攻击她所在行、所在列内或沿对角方向的任何一个棋子。n-皇后问题要求在棋盘上放置n个皇后，使得没有哪个皇后能攻击其他的皇后。 在回溯中，由于每个皇后都必须放置在不同的行中，所以n-皇后问题的解决方案可以表示为一个n元组(x1, … , xn)，这里的xi 是把第i个皇后放在第i行的列数且1 ≤xi ≤n. 由于任何两个皇后都不能出现在同一列中，因此n元组(x1, … , xn)中没有两个元素是相同的。 那么，应该如何判断两个皇后是否在同一斜角线上呢？ 如果设想棋盘的方格像二维数组A(1: n, 1: n)的下标那样标记，对于在同一条斜角线上的由左上方到右下方的每一个元素都有相同的“行?列”值，同样，在同一