算法设计之递归算法.doc

算法设计之递归算法 概念 (1)函数自已调用自己（直接递归） (2)函数a调用函数b,而函数b又调用a。（间接递归） 简述 　一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。因此，在考虑使用递归算法时，应满足两点： 1）该问题能够被递归形式描述； 2）存在递归结束的边界条件 示例 阶乘 阶乘函数是按照递推关系式来定义的: f(0) = 1 f(n) = n * f(n-1) (n0)int f(int n) { if (n==0) return(1); else return(n * f(n-1)); } 优缺点 优点：源程序非常简洁（递归的能力在于用有限的语句来定义对象的无限集合）， 有一些算法本质上只有递归算法。 缺点：消耗较多的内存和运行时间，效率不高。容易引起堆栈溢出。 递归算法的题外话 递归哲学 递归思考法 回溯法（讲稿） 概述 回溯法是一种满足一定约束条件的穷举式搜索法 搜索方法与树的深度优先搜索方式相似 如果问题的解能表示成一个n元组（X1,X2,…,Xn），其中Xi 属于集合Si，则可用回溯法。适用与解的组合数相当大但仍然有限的一类问题 约束条件分为两类： 显约束：每个Xi 的取值范围都给定的约束称为显约束。 隐约束：满足判定函数P的关于I的解空间上的多元式称为隐约束 算法说明 八后问题：在国际象棋棋盘上放八个皇后，要求任何一个往后都吃不到别人，也不受别人攻击。皇后的走法：可以横走、直走和斜走（斜率为±1）任意多格。（棋盘为八行八列） 为简单起见，只讨论四后问题：四行四列棋盘 给行、列、皇后编号，放在第I行的皇后编号为I, Xi 值表示皇后I处的列数。这样，四后问题的全部解向量可以写为：（X1,X2, X3，X4） 显约束可以写为Si ={1，2，3，4}，1≤i≤4. 隐约束是：Xi ≠Xj (1≤i≤4., 1≤j≤4, i≠j).即没有两个皇后在同一列 (i-j)/ (Xi -Xj ) ≠±1.即没有两个皇后在同一斜线上。 求解过程：求解过程可以表示为一棵树，如图4-33(P93) 开始时，根结点(结点1)是唯一的轰动结点，把它变成扩展结点且定义路径为空（）。按从左到右的顺序生成根的子树，即生成结点2，路径变为(1),即X1 =1.相当与把皇后1放在第一行第一列。结点2成为当前的扩展结点。当生成结点3时，路径（1,2）不满足约束条件，此路径不作考虑。回溯到结点2，生产结点4，得到路径(1,3),满足约束，但它的子树不满足约束条件。回溯到结点2，生成结点5，。。。。。。，最终一个解（2，4，1，3），见图4-34(P94) 算法 proceduce BACKTRACK(n) 1.k←1 2.while k0 do if 对于还没有试探过的值x(k),有x(k)属于T（x(1)、…、x(k-1)且Bk (x(1)、…、x(k)的值为真 then begin if(x(1)、…、x(k))是一个解 then write(x(1)、…、x(k)); k←k+1 end else k←k-1 end 算法分析 所需时间取决四个因数： 产生X(k)的时间 满足显约束的x(k)的个数 计算约束函数Bi 的时间 满足约束函数Bi 的x(k)的个数 用回溯法解决一个大的实际问题，其成功的关键之一就是选择有效的约束函数。最价情况：是沿左枝搜索便得到一个解，不用回溯。产生的结点的个数为O(n)，最坏情况是要产生所有的结点，即到右枝才能得到解。如果解空间的结点数为2n ,时间耗费为O(P(n) 2n ) 4．7探索法（讲稿） 计算机研 适合的环境：对于一些复杂的、无法估算是否存在解的问题。 定义：如果一个算法对给定的问题能够通过不同的途径进行探索而得到一个较好的解，而实现这种算法比最佳算法要快，要容易，那么这种算法称为“探索法”。 设计方法：一种常用的方法就是列出精确解的所有要求，分成两类： 必须满足的要求 允许折衷的要求 那么探索算法的设计目的就是保证满足第一类要求，尽量满足第二类要求。 探索法最经典的例子就是 “装箱问题” 了。 问题：有容积为T0的箱子Bi个，另有大小为ti的目标，i = ，要求把所有的目标放入数目尽可能少的箱子里去，目标不能分割，每个箱子装的目标体积之和不能超过T0。 这里给出解此类问题的4种算法： FF算法：（First Fit 首次适合） L是给定的目标序列，把L中的第一个放入B1，然后拿第二个，看是否还能放入B1，能则放入，不能则放入B2，依次。就是说尽量放入下标最小的Bi。 F