数据结构第4讲递归广义表.pptVIP

1. 分治法 (又称分割求解法) 三、递归函数设计方法 2. 后置递归法 3. 回溯法 3. 回溯法 是一种“穷举”方法。其基本思想为: 假设问题的解为 n 元组 (x1, x2, …, xn)， 其中 xi 取值于集合 Si。 2. n 元组的子组 (x1, x2, …, xi) (in) 称为 部分解，应满足一定的约束条件。 3. 对于已求得的部分解 (x1, x2, …, xi) ， 若在添加 xi+1?Si+1 之后仍然满足约束条件， 则得到一个新的部分解 (x1, x2, …, xi+1) , 之后继续添加 xi+2?Si+2 并检查之; 若对于所有取值于集合Si+1的xi+1 都不能得到新的满足约束条件的部分 解(x1,x2, ? ? ?，xi+1 )， 则从当前子组中删去xi, 回溯到前一个部分解(x1,x2, ? ? ?,xi-1 )， 重新添加那些值集Si中尚未考察过的xi，并检查之。 5. 如此反复进行，直至求得满足约束条件的问题的解，或者证明问题无解。 回溯法的关键是: 穷举策略 约束条件 终止条件 皇后问题 设四皇后问题的解为 (x1, x2, x3, x4), 其中: xi (i=1,2,3,4) ? Si={1, 2, 3, 4} 约束条件为: 其中任意两个xi 和xj不能位于棋盘的同行、同列及同对角线。 1 2 3 4 X1 X2 X3 X4 x1= 1 x2= 3 x1= 2 x2= 4 x3= 1 x4= 3 皇后问题回溯算法关键: 穷举策略: 依次取 xi = 1,2,3,4; 约束条件: xi和xj不位于棋盘的同行、 同列及同对角线上； 终止条件: 找到满足条件的x1,x2 x3,x3； 回溯条件: 在当前初始条件下穷举无解； 无解: 回溯到了起始状态； void Trial(int i, int n) { // 进入本函数时，在n×n棋盘前i-1行已放置了互不攻 // 击的i-1个棋子。现从第 i 行起继续为后续棋子选择 // 满足约束条件的位置。当求得(in)的一个合法布局 // 时，输出之。i 的初始值为1。 if(i=0) 无解； if (in) 输出棋盘的当前布局; //终止 else for (j=1; j=n; ++j) { //试探策略 在第 i 行第 j 列放置一个棋子; if (当前布局合法) Trial(i+1, n); //约束-递归 移去第 i 行第 j 列的棋子; } i--; //回溯 } // Trial T(2,4) T(2,4) … … T(1,4) T(1,4) T(3,4) T(1,2) T(1,4) T(1,3) T(3,4) T(3,4) T(3,4) T(3,4) T(3,4) T(3,4) T(2,4) T(2,4) … T(2,4) T(2,4) T(2,4) T(2,4) … T(4,4) T(4,4) T(4,4) T(4,4) T(4,4) B(4,4) x2 x1 x3 x4 … 四皇后递归树 j=1 j=2 j=3 j=4 j=1 j=4 j=1 j=4 j=1 j=3 j=4 j=1 j=1 j=2 先写出问题求解的递归定义,包括两项内容: 基本项: 描述一个或几个递归过程的终结状态； 归纳项: 描述如何从当前状态到终结状态的转换； 四、递归注意事项 2 写递归函数时注意: 严格定义函数的功能和接口; 将每一个递归看成一个简单的操作; 切忌想得太深太远！ 递归树的深度即为递归函数的递归深度 递归树上的结点数目恰为函数中的主要操作重复进行的次数； 若递归树蜕化为单支树或者递归树中含有很多相同的结点，则表明该递归函数不适用。 3. 分析递归算法的工具是递归树，从递归树上可以得到递归函数的各种相关信息。 例如: n=3的梵塔算法中主要操作move的执行次数可以利用下列递归树进行分析: move(3, a, b, c) move(2, a, c, b) move(2, b, a, c) move(1, a, b, c) move(1, c, a, b)