数据结构与算法第十章Algorithmdesigntechniques

1、Ch10 算法设计技术(Algorithm Design Techniques)10.1 穷举法（Exhaustive Algorithm）10.2 递推法与迭代法（ Recurrence and Iterative Algorithm ）10.3 递归（ Recursive Algorithm ）10.4 逐步求精（ Stepwise Refinement ）10.5 分治法（ Divide and Conquer ）10.6 贪心法（ Greedy Algorithm ）10.7 回溯法（ Backtracking Algorithm ）10.8 动态规划法（ Dynamic Progra

2、mming ）10.9 分支界限法（ Branch and Bound Algorithm ）Summary 10.1 穷举法（Exhaustive Algorithm） 穷举法(枚举法/试探法)基本思想是： 分别列举出各种可能解，测试（试探）其是否满足条件（是否是欲求的解），若是，则输出之。 特点是算法简单，但是运算量大。当问题的规模变大，执行的的速度变慢。10.1 穷举法（Exhaustive Algorithm） 例1解不定方程。不定方程（组）是指独立方程个数少于变量个数而导致方程有多解。 如，2x+3y=20是一个不定方程（设x, y为正整数）。解这个方程，就是求出所有的解。 不定方程

3、一般都有限定条件，我们这里考虑正整数解的情况。解这个方程，一个简单的做法是，让x和y分别遍取0到20内的正整数，并代入方程计算，若值为20，则表示找到一组解。具体的程序片断如下。 for (i=0; i=20; i+) for (j=0; j=20; j+) if (2*i + 3*j = 20 ) coutni,j; 10.2 递推法与迭代法 （Recurrence and Iterative Algorithm） 递推法与迭代法是两种风格类似的方法，它们都是基于分步递增方式进行求解。（1）递推法（Recurrence Algorithm） 递推法是针对这样一类问题：问题的解决可以分为若干步

4、骤，每个步骤都产生一个子解（部分结果），每个子解都是由前面若干子解生成。把这种由前面的子解得出后面的子解的规则称为递推关系。例如，对于Fibonacci数列：1 1 2 3 5 8 13 21 34 设f(n)表示数列中第n项，则有：f(1) = 1f(2) = 1f(k) = f(k-1) + f(k-2)递推法实现Fibonacci数列int Fibonacci(int n) int f1, f2, f3; int k; f1 = 1 ; f2 = 1 ; if ( n=1 ) return 1; if ( n=2 ) return 1; for (k=3; kprecision | x0

5、-xprecision); /当最近两个近似解的差的绝对值小于给定精度时结束 return x; 10.3.1 什么是递归（1）递归的定义在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。 若调用自身,称之为直接递归。 若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。10.3 递归（Recursive Algorithm）例10.3.1 以下是求n!(n为正整数)的递归函数。 int fun(int n) if (n=1) /*语句1*/ return 1;/*语句2*/ els

6、e /*语句3*/ return fun(n-1)*n;/*语句4*/ 在该函数fun(n)求解过程中,直接调用fun(n-1)(语句4)自身,所以它是一个直接递归函数。 递归调用是最后一条语句,所以它又属于尾递归。（2） 何时使用递归 在以下三种情况下,常常要用到递归的方法。 （a） 定义是递归的 有许多数学公式、数列等的定义是递归的。 例如,求n!和Fibonacci数列等。 这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。 （b）数据结构是递归的 有些数据结构是递归的。 例如,第2章中介绍过的单链表就是一种递归数据结构,其结点类型定义如下： typedef struct LN

7、ode ElemType data; struct LNode *next; LinkList; 该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。 对于递归数据结构,采用递归的方法编写算法既方便又有效。 例如,求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法如下： int Sum(LinkList *head) if (head=NULL) return 0; else return(head-data+Sum(head-next); （c） 问题的求解方法是递归的 有些问题的解法是递归的, 典

8、型的有Hanoi问题求解,该问题描述是：设有3个分别命名为X,Y和Z的塔座,在塔座X上有n个直径各不相同,从小到大依次编号为1,2,n的盘片,现要求将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放,盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X,Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法,并将其转换为非递归算法。 设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上,递归分解的过程是：Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)；move(n,x,z):将第n个圆盘从x移到z；Hanoi(n-1,y,x,z

9、)（3） 递归模型 递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 式（1）给出了递归的终止条件, 式（2）给出了fun(n)的值与fun(n-1)的值之间的关系 式（1）称为递归出口 式（2）称为递归体 一般地,一个递归模型是由递归出口和递归体两部分组成,前者确定递归到何时结束,后者确定递归求解时的递推关系。递归出口的一般格式如下： f(s1)=m1 这里的s1与m1均为常量,有些递归问题可能有几个递归出口。递归体的一般格式如下： f(sn+1)=g(f(si),f(

10、si+1),f(sn),cj,cj+1,cm) (6.2) 其中,n,i,j,m均为正整数。这里的sn+1是一个递归“大问题”,si,si+1,sn为递归“小问题”,cj,cj+1,cm是若干个可以直接(用非递归方法)解决的问题,g是一个非递归函数,可以直接求值。 实际上,递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决(此时分解到递归出口)。 递归分解不是随意的分解,递归分解要保证“大问题”与“小问题”相似,即求解过程与环境都相似。 为了讨论方便,简化上述递归模型为

11、： f(s1)=m1 f(sn)=g(f(sn-1),c)求f(sn)的分解过程如下： f(sn) f(sn-1) f(s2) f(s1) 一旦遇到递归出口,分解过程结束,开始求值过程,所以分解过程是“量变”过程,即原来的“大问题”在慢慢变小,但尚未解决,遇到递归出口后,便发生了“质变”,即原递归问题便转化成直接问题。上面的求值过程如下： f(s1)=m1 f(s2)=g(f(s1),c1) f(s3)=g(f(s2),c2) f(sn)=g(f(sn-1),cn-1) 这样f(sn)便计算出来了。 因此,递归的执行过程由分解和求值两部分构成。 求解fun(5)的过程如下：10.3.2 递归算

12、法的设计 递归的求解的过程均有这样的特征：先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法,于是可以再将它们划分成若干个子问题,分别求解,如此反复进行,直到不能再划分成子问题,或已经可以求解为止。这种自上而下将问题分解、求解,再自上而下引用、合并,求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。 递归算法设计先要给出递归模型,再转换成对应的C/C+语言函数。 递归设计的步骤如下： (1)对原问题f(s)进行分析,假设出合理的“较小问题”f(s)(与数学归纳法中假设n=k-1时等式成立相似)； (2)假设f(s)

13、是可解的,在此基础上确定f(s)的解,即给出f(s)与f(s)之间的关系(与数学归纳法中求证n=k时等式成立的过程相似)； (3)确定一个特定情况(如f(1)或f(0)的解,由此作为递归出口(与数学归纳法中求证n=1时等式成立相似)。 例如,采用递归算法求实数数组A0.n-1中的最小值。 假设f(A,i)函数求数组元素A0Ai中的最小值。 当i=0时,有f(A,i)=A0； 假设f(A,i-1)已求出,则f(A,i)=MIN(f(A,i-1),Ai),其中MIN()为求两个值较小值函数。 因此得到如下递归模型： A0 当i=0时 f(A,i)= MIN(f(A,i-1),Ai) 其他情况由此得

14、到如下递归求解算法： float f(float A,int i) float m; if (i=0) return A0; else m=f(A,i-1); if (mAi) return Ai; else return m; 例采用递归算法求解皇后问题：在nn的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。 （见教材）10.3.3 递归算法到非递归算法的转换 递归算法有两个基本特性： 一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的方法是十分有效的； 二是递归算法的时间效率通常比较差。 因此,对求解某些问题

15、时,我们希望用递归算法分析问题,用非递归算法具体求解问题。 这就需要把递归算法转换为非递归算法。把递归算法转化为非递归算法有如下三种基本方法： (1)对于尾递归和单向递归的算法,可用循环结构的算法替代。 (2)自己用栈模拟系统的运行时栈,通过分析只保存必须保存的信息,从而用非递归算法替代递归算法。 (3)利用栈保存参数,由于栈的后进先出特性吻合递归算法的执行过程,因而可以用非递归算法替代递归算法。 （见教材） 10.4 逐步求精（Stepwise Refinement）简单地讲，逐步求精方法，是一种逐步“划分”的方法，即将问题的解决，先用几个大/粗的模块的组合表示。对这些模块，先不考虑它们的内

16、部实现，只规定其功能。然后再按类似方法继续划分这些模块，直到它们都变为程序设计语句。在这种划分中，应遵循下列规则：保证模块的粒度应逐步变小。粒度越大/粗，“说明性”越强，越远离程序设计语言，但越容易给出（设计）；保证当前正确。对每次划分，若假定各模块都可正确实现，则它们的当前组合（即划分方式）是整个问题的正确实现；对逐步求精的描述，一般采用“伪码”。所谓伪码，是指不完全的程序代码，它一般以程序设计语言(典型的是C/Pascal之类的结构化程序设计语言)的流程控制语句（如while, for, if等）为主体，夹杂自然语言的描述。 例 求矩阵的鞍点考虑求矩阵鞍点的问题。所谓矩阵鞍点，是指满足这样

17、条件的矩阵元素：它是所在行上的最小元素，同时是所在列上的最大元素。可以证明，一个矩阵可以有多个鞍点，但它们的值均相等。显然，求鞍点的一个直接的方法是，检查矩阵中每个元素是否为鞍点，用伪码描述为（设矩阵名为a，有n行m列，元素下标从0起）：for (i=0; in; i+) for (j=0; jm; j+) 判断aij是否为鞍点； if (aij 是鞍点) 输出aij; 例 求矩阵的鞍点(续1)这里，关键问题是判断aij是否为鞍点，所以关键是细化模块“判断aij是否为鞍点”。解决该问题，先检查aij是否为i行上的最小者，若是，则继续检查其是否为j列上最大者，若是，则为鞍点。其他情况都不是鞍点。

18、该过程的伪码描述为：isSaddle = 0; 检查aij是否为i行上最小者；if (是) 检查aij是否为j列上最大者； if (是) isSaddle = 1;例 求矩阵的鞍点（续2）这段程序结束后，isSaddle为非0时表示aij为鞍点，否则不是鞍点。在这里，有两个模块需要细化：a) 检查aij是否为i行上最小者，这可以先找出i行上最小者的下标，然后与aij比较即可：kk=0;for (k=1; km; k+) if (aik aikk ) kk=k;if (aikk=aij) aij为i行上最小者；例 求矩阵的鞍点（续3）b) 检查aij是否为j列上最大者： kk=0; for (k

19、=1; k akkj ) kk=k; if (akkj=aij) aij为j列上最大者； 10.5 分治法（Divide and Conquer） 分治是指“分而治之”（Divide and conquer），是把一个规模为n的问题分成两个或多个较小的与原问题类型相同的子问题，通过对子问题的求解，并把子问题的解合并起来从而构造出整个问题的解，即对问题分而治之。 如果子问题的规模仍然相当大，还不足以很容易地求得它的解，这时可以对此子问题重复地应用分治策略。10.5 分治法（Divide and Conquer） 分治法求解过程，分为3个阶段：划分。规模为n的原问题划分为k（k=1）规模较小子问题

20、。求解子问题。各子问题与原问题解法相同，可用递归方法求解各个子问题。子问题足够小时，直接求解。合并。把各个子问题的解合并起来。分治法的算法框架return_type d_and_c( objArray * p , int i , int j ) int temp ; if ( simple (p,i,j) ) return solve (p,i,j) ; /*基值处理 */ temp = divide (p,i,j) ; /*分解问题 */ return ( combine ( d_and_c(p,i,temp-1),d_and_c(p,temp,j) ) ); /*递归调用与合并处理 */1

21、0.5 分治法（Divide and Conquer）10.5 分治法（Divide and Conquer）二分法检索就是我们所学过的应用分治策略的典型的例子。快速排序算法，归并排序算法、汉诺塔问题等都可以用分治策略求解。 快速排序算法每趟把一个元素放入排完序后它所应在的位置，这个位置把原表分成了两个宏观有序的子表；归并排序算法是把规模为的问题分成规模为n/2的两个子问题；而汉诺塔问题分原问题为两个规模为n-1的子问题。 例子10.5 分治法（Divide and Conquer）讨论分治策略把问题分成若干个子问题，分成的子问题的数目一般不大。如果每次分成的各子问题的规模相等或近乎相等的话，

22、则分治策略的效率较高，否则效率就比较低。例如：直接插入排序可以看作是把原问题分解成两个子问题，一个是规模为的问题，另一个是规模为n-1的问题，算法的时间代价是O(n)级的。而归并排序把原问题分成了两个大小为n/2的问题，算法的时间代价是O(nlog2n)级的。10.6 贪心法（Greedy Algorithm）贪心法(greedy)基本思想根据题意，选取一种度量标准，然后将n个输入数据排成这种标准所要求的顺序，按这种顺序一次输入一个数据。每一次都要保证能获得局部最优解。若下一个数据与局部最优解连在一起不再是可行解，就不把该数据添加到局部解中，直到把所有数据枚举完，或者不能再添加为止。这种能够得

23、到某种度量意义下的最优解的分级处理方法贪心法。10.6 贪心法（Greedy Algorithm）Dijkstra的最短路径算法 求从源点到其它各结点的最短路径 它总是从那些最短路径还不知道的结点中挑选一个到源点最近的结点。另一采用贪心策略的算法是Kruskal的求最小生成树算法。Huffman树的算法采用贪心法。背包问题 给定n个物体和一个背包，已知物体i的重量为wi0，价值为pi，背包能容纳物体的重量为M。要求确定一组分数xi(xi0,1)，能够把物体i的xi部分放入背包，使得 最大，即将尽量多的价值装入背包。 这是一个求最优解的问题。在仅仅限制装入背包的物品重量的前提下，为了使得装入背包

24、的物品得到尽量大的价值，应该优先放入按单位重量价值最大的物品。可以用贪心法求解。贪心法是一个很直接的算法设计技术，可以很容易地用算法实现。10.6 贪心法（Greedy Algorithm）10.6 贪心法（Greedy Algorithm）因为：p/w25/18，p/w24/15，p3/w315/10，p/wp/wp/w。所以首先把物品2全部放入背包，然后考虑物品3，最后如果还有余地考虑物品1。这样得到的结果为（x，x2，x3）（0，1，1/2），例如：3，20， (p1,p2,p3)=(25,24,15), (w1,w2,w3)=(18,15,10)10.6 贪心法（Greedy Algo

25、rithm）解背包问题的贪心算法的实现：其中参数数组p和w中,按pi/wi的降序分别存放物体的价格和重量；m是背包能放的物体总重量，n是物体件数。x存放解向量。float knapSack(float* p, float* w, float * x ,float m, int n) int i=0;float s=0; while(in & pim) m -= wi; s += pi; xi = 1; i+; if ( i0 ) s += pi*m/wi; xi = m/wi; i+; for ( ; in ; i+ ) xi=0; return (s); 进一步讨论 贪心算法各个阶段的局部最

26、优选择，一经确定就固定地作为解序列的一部分。N步的选择就可得到一个较好的次优解（有可能是最优解，但是最优解一般是需经全排列所有测试才能得到）。 贪心法在各个阶段，选择那些在某些意义下是局部最优的方案，期望各阶段的局部最优的选择带来整体也最优。但是，贪心法不是每次都能成功地产生出一个整体最优解。 对某些问题，只有通过系统的、彻底的搜索才能得到最优解，从而使我们求得最优解的代价甚高。但是只要求得一个与最优解相差不多的次优解就满足要求时，选用贪心法可以帮助我们很快地得到这样的解。 10.6 贪心法（Greedy Algorithm）10.7 回溯法（Backtracking Algorithm） 有

27、一类问题，要求找到一个满足某些条件的最优解。对于解决这样的问题，可以通过使用彻底的搜索方法来解决。然而，彻底的搜索，要进行大量的比较，大量的舍弃，要以大量的运算时间为代价，有时甚至大到连计算机也承受不了的程度。 因此，用“穷举”的方法来解决这些问题往往是不实际的。 回溯法（backtracking）为我们解决这类问题提供了一个好的方法。求助于回溯技巧，常常可以大大地减少实际的搜索数目。回溯法基本思想：若在当前位置探测到一条通路则继续向前，若在当前位置探测不到一条通路则回溯至前一位置继续探测尚未探测的方向，直到找到一条通路或探测出无通路存在为止。典型回溯算法举例 （1）求解迷宫问题 （2）深度优

28、先对图的遍历 回溯算法与栈 由于回溯方法的本质是用深度优先的方法在解的空间树中搜索。所以在算法中都需要建立一个栈，用来保存搜索的路径。一旦产生的部分解系列不合要求，就要从栈中找到回溯的前一个位置，继续试探。10.7 回溯法（Backtracking Algorithm）10.7 回溯法（Backtracking Algorithm）一般回溯方法的程序结构：void backtrack (void) 准备初值； do while (范围未超界并且工作未完成) 分析条件；/* 保证满足条件才往下去 */if (成功) 路径进栈； 由第一选择开始进入下一层；/* 纵向走 */ else 本层更换选择； /* 横向走 */ if (