数据结构与算法第十章algorithmdesigntechniques武汉理工大学全解

1、信息工程学院信息工程学院School of Information Engineering2Ch10 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 ConquerDivide and Conquer ）10.6 贪心法（ Gre

2、edy AlgorithmGreedy Algorithm ）10.7 回溯法（ Backtracking AlgorithmBacktracking Algorithm ）10.8 动态规划法（ Dynamic ProgrammingDynamic Programming ）10.9 分支界限法（ Branch and Bound AlgorithmBranch and Bound Algorithm ）Summary 310.1 穷举法（Exhaustive Algorithm） 穷举法穷举法( (枚举法枚举法/ /试探法试探法) )基本思想是：基本思想是： 分别列举出各种可能解，测试（试

3、探）其是否满足条件分别列举出各种可能解，测试（试探）其是否满足条件（是否是欲求的解），若是，则输出之。（是否是欲求的解），若是，则输出之。 特点是算法简单，但是运算量大。当问题的规模变大，执行的的速度变慢。410.1 穷举法（穷举法（Exhaustive Algorithm） 例例1解不定方程。不定方程（组）是指独立方程个数少于变量个数而导致方程有多解。 如，2x+3y=20是一个不定方程（设x, y为正整数）。解这个方程，就是求出所有的解。 不定方程一般都有限定条件，我们这里考虑正整数解的情况。解这个方程，一个简单的做法是，让x和y分别遍取0到20内的正整数，并代入方程计算，若值为20，则表

4、示找到一组解。具体的程序片断如下。 for (i=0; i=20; i+) for (j=0; j=20; j+) if (2*i + 3*j = 20 ) coutni,j; 510.2 递推法与迭代法 （Recurrence and Iterative Algorithm） 递推递推法与法与迭代迭代法是两种风格类似的方法，它们都法是两种风格类似的方法，它们都是是基于分步递增基于分步递增方式进行求解。方式进行求解。6（1）递推法）递推法（Recurrence Algorithm） 递推法递推法是针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解（部分结果），每个子解都是由前

5、面若干子解生成。把这种由前面的子解得出后面的子解的规则称为递推关系。例如例如，对于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)7递推法实现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-xprecision); /当最近两个近似解的差

6、的绝对值小于给定精度时结束 return x; 1210.3.1 10.3.1 什么是递归什么是递归（1 1）递归的定义）递归的定义在定义一个过程或函数时出现调用本过程或本函数的成在定义一个过程或函数时出现调用本过程或本函数的成分分, ,称之为称之为递归递归。 若调用自身若调用自身, ,称之为称之为直接递归直接递归。 若过程或函数若过程或函数p p调用过程或函数调用过程或函数q,q,而而q q又调用又调用p,p,称之为称之为间接递归间接递归。 如果一个递归过程或递归函数中递归调用语句是最后如果一个递归过程或递归函数中递归调用语句是最后一条执行语句一条执行语句, ,则称这种递归调用为则称这种递归

7、调用为尾递归尾递归。10.3 10.3 递归递归（Recursive Algorithm）13例例10.3.1 以下是求以下是求n!(n为正整数为正整数)的递归函数。的递归函数。 int fun(int n) if (n=1) /*语句语句1*/ return 1;/*语句语句2*/ else /*语句语句3*/ return fun(n-1)*n;/*语句语句4*/ 在该函数在该函数fun(n)求解过程中求解过程中,直接调用直接调用fun(n-1)(语句语句4)自身自身,所以它是一个所以它是一个直接递归函数直接递归函数。 递归调用是最后一条语句递归调用是最后一条语句,所以它又属于所以它又属于

8、尾递归尾递归。14（2 2） 何时使用递归何时使用递归 在以下三种情况下在以下三种情况下,常常要用到递归的方法。常常要用到递归的方法。 （a） 定义是递归的定义是递归的 有许多数学公式、数列等的定义是递归的。有许多数学公式、数列等的定义是递归的。 例如例如,求求n!和和Fibonacci数列等。数列等。 这些问题的求解过程可以将其递归定义直接转化这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。为对应的递归算法。 15（b）数据结构是递归的）数据结构是递归的 有些数据结构是递归的。有些数据结构是递归的。 例如例如,第第2章中介绍过的单链表就是一种递归数据结章中介绍过的单链表就是一种递

9、归数据结构构,其结点类型定义如下：其结点类型定义如下： typedef struct LNode ElemType data; struct LNode *next; LinkList; 该定义中该定义中,结构体结构体LNode的定义中用到了它自身的定义中用到了它自身,即即指针域指针域next是一种指向自身类型的指针是一种指向自身类型的指针,所以它是一种所以它是一种递归数据结构。递归数据结构。 16 对于递归数据结构对于递归数据结构,采用递归的方法编写算法既方采用递归的方法编写算法既方便又有效。便又有效。 例如例如,求一个不带头结点的单链表求一个不带头结点的单链表head的所有的所有data域

10、域(假设为假设为int型型)之和的递归算法如下：之和的递归算法如下： int Sum(LinkList *head) if (head=NULL) return 0; else return(head-data+Sum(head-next); 17（c） 问题的求解方法是递归的问题的求解方法是递归的 有些问题的解法是递归的有些问题的解法是递归的, 典型的有典型的有Hanoi问题求解问题求解,该问题描述是：设有该问题描述是：设有3个个分别命名为分别命名为X,Y和和Z的塔座的塔座,在塔座在塔座X上有上有n个直径各不个直径各不相同相同,从小到大依次编号为从小到大依次编号为1,2,n的盘片的盘片,现要

11、求将现要求将X塔座上的塔座上的n个盘片移到塔座个盘片移到塔座Z上并仍按同样顺序叠放上并仍按同样顺序叠放,盘片移动时必须遵守以下规则：每次只能移动一个盘盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在片；盘片可以插在X,Y和和Z中任一塔座；任何时候都中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归不能将一个较大的盘片放在较小的盘片上。设计递归求解算法求解算法,并将其转换为非递归算法。并将其转换为非递归算法。 设设Hanoi(n,x,y,z)表示将表示将n个盘片从个盘片从x通过通过y移动到移动到z上上,递归分解的过程是：递归分解的过程是：18Hanoi(n,x,y

12、,z)Hanoi(n-1,x,z,y)；move(n,x,z):将第将第n个圆盘从个圆盘从x移到移到z；Hanoi(n-1,y,x,z)19（3 3） 递归模型递归模型 递归模型是递归算法的抽象递归模型是递归算法的抽象,它反映一个递归问题它反映一个递归问题的递归结构的递归结构,例如例如,前面的递归算法对应的递归模型如下：前面的递归算法对应的递归模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 式（式（1）给出了递归的终止条件）给出了递归的终止条件, 式（式（2）给出了）给出了fun(n)的值与的值与fun(n-1)的值之间的关系的值之间的关系 式（式（1）

13、称为）称为递归出口递归出口 式（式（2）称为）称为递归体递归体20 一般地一般地,一个递归模型是由递归出口和递归体两部分一个递归模型是由递归出口和递归体两部分组成组成,前者确定递归到何时结束前者确定递归到何时结束,后者确定递归求解时的后者确定递归求解时的递推关系。递推关系。递归出口的一般格式如下：递归出口的一般格式如下： f(s1)=m1 这里的这里的s1与与m1均为常量均为常量,有些递归问题可能有几个递有些递归问题可能有几个递归出口。归出口。递归体的一般格式如下：递归体的一般格式如下： f(sn+1)=g(f(si),f(si+1),f(sn),cj,cj+1,cm) (6.2) 其中其中,

14、n,i,j,m均为正整数。这里的均为正整数。这里的sn+1是一个递归是一个递归“大大问题问题”,si,si+1,sn为递归为递归“小问题小问题”,cj,cj+1,cm是若干是若干个可以直接个可以直接(用非递归方法用非递归方法)解决的问题解决的问题,g是一个非递归是一个非递归函数函数,可以直接求值。可以直接求值。21 实际上实际上,递归思路是把一个不能或不好直接求解的递归思路是把一个不能或不好直接求解的“大问题大问题”转化成一个或几个转化成一个或几个“小问题小问题”来解决来解决,再把再把这些这些“小问题小问题”进一步分解成更小的进一步分解成更小的“小问题小问题”来解来解决决,如此分解如此分解,直

15、至每个直至每个“小问题小问题”都可以直接解决都可以直接解决(此此时分解到递归出口时分解到递归出口)。 递归分解不是随意的分解递归分解不是随意的分解,递归分解要保证递归分解要保证“大问题大问题”与与“小问题小问题”相似相似,即求解过程与环境都相似。即求解过程与环境都相似。 22为了讨论方便为了讨论方便,简化上述递归模型为：简化上述递归模型为： f(s1)=m1 f(sn)=g(f(sn-1),c)求求f(sn)的分解过程如下：的分解过程如下： f(sn) f(sn-1) f(s2) f(s1)23 一旦遇到递归出口一旦遇到递归出口,分解过程结束分解过程结束,开始求值过程开始求值过程,所所以分解过

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

17、un(3) d3:fun(2) d4:fun(1) 返回 1 fun(2)=2 fun(3)=6 fun(4)=24 fun(5)=120 求解求解fun(5)的过程如下：的过程如下：2610.3.2 10.3.2 递归算法的设计递归算法的设计 递归的求解的过程均有这样的特征：先将整个问题递归的求解的过程均有这样的特征：先将整个问题划分为若干个子问题划分为若干个子问题,通过分别求解子问题通过分别求解子问题,最后获得最后获得整个问题的解。而这些子问题具有与原问题相同的求整个问题的解。而这些子问题具有与原问题相同的求解方法解方法,于是可以再将它们划分成若干个子问题于是可以再将它们划分成若干个子问题

18、,分别分别求解求解,如此反复进行如此反复进行,直到不能再划分成子问题直到不能再划分成子问题,或已经或已经可以求解为止。这种自上而下将问题分解、求解可以求解为止。这种自上而下将问题分解、求解,再自再自上而下引用、合并上而下引用、合并,求出最后解答的过程称为递归求解求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。过程。这是一种分而治之的算法设计方法。 递归算法设计先要给出递归模型递归算法设计先要给出递归模型,再转换成对应的再转换成对应的C/C+语言函数。语言函数。27 递归设计的步骤如下：递归设计的步骤如下： (1)对原问题对原问题f(s)进行分析进行分析,假设出合理的假设出合

19、理的“较小问较小问题题”f(s)(与数学归纳法中假设与数学归纳法中假设n=k-1时等式成立相似时等式成立相似)； (2)假设假设f(s)是可解的是可解的,在此基础上确定在此基础上确定f(s)的解的解,即给出即给出f(s)与与f(s)之间的关系之间的关系(与数学归纳法中求证与数学归纳法中求证n=k时等式成时等式成立的过程相似立的过程相似)； (3)确定一个特定情况确定一个特定情况(如如f(1)或或f(0)的解的解,由此作为递由此作为递归出口归出口(与数学归纳法中求证与数学归纳法中求证n=1时等式成立相似时等式成立相似)。28 例如例如,采用递归算法求实数数组采用递归算法求实数数组A0.n-1中的

20、最小值。中的最小值。 假设假设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) 其他情况其他情况29由此得到如下递归求解算法：由此得到如下递归求解算法： float f(float A,int i) float m; if (i=0) return A0; el

21、se m=f(A,i-1); if (mAi) return Ai; else return m; 30例采用递归算法求解皇后问题：在例采用递归算法求解皇后问题：在nn的方的方格棋盘上，放置格棋盘上，放置n个皇后，要求每个皇后不同行、个皇后，要求每个皇后不同行、不同列、不同左右对角线。不同列、不同左右对角线。 （见教材）（见教材）3110.3.3 10.3.3 递归算法到非递归算法的转换递归算法到非递归算法的转换 递归算法有两个基本特性：递归算法有两个基本特性： 一是递归算法是一种分而治之的、把复杂问题分解为一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法简单问题的求解问题

22、方法,对求解某些复杂问题对求解某些复杂问题,递归算递归算法分析问题的方法是十分有效的；法分析问题的方法是十分有效的； 二是递归算法的时间效率通常比较差。二是递归算法的时间效率通常比较差。 因此因此,对求解某些问题时对求解某些问题时,我们希望用递归算法分析问我们希望用递归算法分析问题题,用非递归算法具体求解问题。用非递归算法具体求解问题。 这就需要把递归算法转换为这就需要把递归算法转换为非递归算法非递归算法。32把递归算法转化为非递归算法有如下三种基本方法：把递归算法转化为非递归算法有如下三种基本方法： (1)对于尾递归和单向递归的算法对于尾递归和单向递归的算法,可用循环结构的算可用循环结构的算

23、法替代。法替代。 (2)自己用栈模拟系统的运行时栈自己用栈模拟系统的运行时栈,通过分析只保存必通过分析只保存必须保存的信息须保存的信息,从而用非递归算法替代递归算法。从而用非递归算法替代递归算法。 (3)利用栈保存参数利用栈保存参数,由于栈的后进先出特性吻合递归由于栈的后进先出特性吻合递归算法的执行过程算法的执行过程,因而可以用非递归算法替代递归算法。因而可以用非递归算法替代递归算法。 （见教材）（见教材） 3310.4 逐步求精（Stepwise Refinement）简单地讲，逐步求精方法，是一种逐步“划分”的方法，即将问题的解决，先用几个大/粗的模块的组合表示。对这些模块，先不考虑它们的

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

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

26、查其是否为j列上最大者，若是，则为鞍点。其他情况都不是鞍点。该过程的伪码描述为：isSaddle = 0; 检查aij是否为i行上最小者；if (是) 检查aij是否为j列上最大者； if (是) isSaddle = 1;36例 求矩阵的鞍点（续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行上最小者；37例 求矩阵的鞍点（

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

28、.5 分治法分治法（Divide and ConquerDivide and Conquer） 分治法求解过程，分为3个阶段： 划分。规模为n的原问题划分为k（k=1）规模较小子问题。 求解子问题。各子问题与原问题解法相同，可用递归方法求解各个子问题。子问题足够小时，直接求解。 合并。把各个子问题的解合并起来。40 分治法的算法框架分治法的算法框架return_type d_and_c( objArray return_type d_and_c( objArray * * p , int i , int j ) p , int i , int j ) int temp ; int temp ;

29、 if ( simple (p,i,j) ) return solve (p,i,j) ; if ( simple (p,i,j) ) return solve (p,i,j) ; / /* *基值处理基值处理 * */ / temp = divide (p,i,j) ; / temp = divide (p,i,j) ; /* *分解问题分解问题 * */ / return ( combine ( d_and_c(p,i,temp-1),d_and_c(p,temp,j) ) ); return ( combine ( d_and_c(p,i,temp-1),d_and_c(p,temp,j

30、) ) ); / /* *递归调用与合并处理递归调用与合并处理 * */ / 10.5 10.5 分治法分治法（Divide and ConquerDivide and Conquer）4110.5 10.5 分治法分治法（Divide and ConquerDivide and Conquer） 二分法检索就是我们所学过的应用分治策略的典型的例子。 快速排序算法，归并排序算法、汉诺塔问题等都可以用分治策略求解。 快速排序算法每趟把一个元素放入排完序后它所应在的位置，这个位置把原表分成了两个宏观有序的子表； 归并排序算法是把规模为的问题分成规模为n/2的两个子问题； 而汉诺塔问题分原问题为两个

31、规模为n-1的子问题。 例子4210.5 10.5 分治法分治法（Divide and ConquerDivide and Conquer）讨论 分治策略把问题分成若干个子问题，分成的子问题的数目一般不大。 如果每次分成的各子问题的规模相等或近乎相等的话，则分治策略的效率较高，否则效率就比较低。 例如：直接插入排序可以看作是把原问题分解成两个子问题，一个是规模为的问题，另一个是规模为n-1的问题，算法的时间代价是O(n)级的。 而归并排序把原问题分成了两个大小为n/2的问题，算法的时间代价是O(nlog2n)级的。4310.6 10.6 贪心法贪心法（Greedy AlgorithmGreed

32、y Algorithm）贪心法贪心法(greedy)基本思想 根据题意，选取一种度量标准，然后将n个输入数据排成这种标准所要求的顺序，按这种顺序一次输入一个数据。每一次都要保证能获得局部最优解。若下一个数据与局部最优解连在一起不再是可行解，就不把该数据添加到局部解中，直到把所有数据枚举完，或者不能再添加为止。 这种能够得到某种度量意义下的最优解的分级处理方法贪心法。4410.6 10.6 贪心法贪心法（Greedy AlgorithmGreedy Algorithm） Dijkstra的最短路径算法 求从源点到其它各结点的最短路径 它总是从那些最短路径还不知道的结点中挑选一个到源点最近的结点。

33、 另一采用贪心策略的算法是Kruskal的求最小生成树算法。 Huffman树的算法采用贪心法。45背包问题背包问题 给定n个物体和一个背包，已知物体i的重量为wi0，价值为pi，背包能容纳物体的重量为M。要求确定一组分数xi(xi0,1)，能够把物体i的xi部分放入背包，使得 最大，即将尽量多的价值装入背包。 这是一个求最优解的问题。在仅仅限制装入背包的物品重量的前提下，为了使得装入背包的物品得到尽量大的价值，应该优先放入按单位重量价值最大的物品。可以用贪心法求解。贪心法是一个很直接的算法设计技术，可以很容易地用算法实现。10.6 10.6 贪心法贪心法（Greedy AlgorithmGr

34、eedy Algorithm）niiixp14610.6 10.6 贪心法贪心法（Greedy AlgorithmGreedy Algorithm）因为：p/w25/181.38，p/w24/151.6，p3/w315/101.5，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)4710.6 10.6 贪心法贪心法（Greedy AlgorithmGreedy Algorithm） 解背包问

35、题的贪心算法的实现：其中参数数组其中参数数组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

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

37、贪心法（Greedy AlgorithmGreedy Algorithm）4910.7 10.7 回溯法回溯法（Backtracking AlgorithmBacktracking Algorithm） 有一类问题，要求找到一个满足某些条件的最优解。对于解决这样的问题，可以通过使用彻底的搜索方法来解决。然而，彻底的搜索，要进行大量的比较，大量的舍弃，要以大量的运算时间为代价，有时甚至大到连计算机也承受不了的程度。 因此，用“穷举”的方法来解决这些问题往往是不实际的。 回溯法（backtracking）为我们解决这类问题提供了一个好的方法。求助于回溯技巧，常常可以大大地减少实际的搜索数目。回溯法

38、基本思想：若在当前位置探测到一条通路则继续向前，若在当前位置探测不到一条通路则回溯至前一位置继续探测尚未探测的方向，直到找到一条通路或探测出无通路存在为止。50典型回溯算法举例典型回溯算法举例 （1）求解迷宫问题 （2）深度优先对图的遍历 回溯算法与栈回溯算法与栈 由于回溯方法的本质是用深度优先的方法在解的空间树中搜索。所以在算法中都需要建立一个栈，用来保存搜索的路径。一旦产生的部分解系列不合要求，就要从栈中找到回溯的前一个位置，继续试探。10.7 10.7 回溯法回溯法（Backtracking AlgorithmBacktracking Algorithm）5110.7 10.7 回溯法回

39、溯法（Backtracking AlgorithmBacktracking Algorithm）一般回溯方法的程序结构：void backtrack (void) 准备初值； do while (范围未超界并且工作未完成) 分析条件；/* 保证满足条件才往下去 */if (成功) 路径进栈； 由第一选择开始进入下一层；/* 纵向走 */ else 本层更换选择； /* 横向走 */ if ( 工作未完成 ) 弹出堆栈； 原来的上一层更换为下一选择；/* 回溯到上层横向*/ while ( 全部工作未完成 ) ；输出结果；5210.8 10.8 动态规划法动态规划法（Dynamic Progra

40、mmingDynamic Programming） 1951年，美国数学家R.Bellman等人根据一类多阶段问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段问题，然后逐个加以解决。 同时提出解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法动态规划法。 能采用动态规划法求解问题需要满足以下条件： 问题的状态必须满足最优化原理。 问题中的状态必须满足无后效性（下一时刻的状态只与当前状态有关，而与当前状态之前的状态无关）。5310.8 10.8 动态规划法动态规划法（Dynamic ProgrammingDynamic Programming） 与贪心法比较 动态规

41、划法是将一系列的子问题的解确定后填入表中，从而导出原问题的解； 而贪心算法是进行了一系列的挑选，确定一个较好的解。 相同点：二者都作出一系列的确定； 区别（1）动态规划法先求子问题的解，然后通过求解子问题构造原问题的解；而贪心法是直接地解原问题。54 与贪心法比较 区别（2）动态规划法一般产生多个子问题的解，每个子问题的解都是局部最优的，局部最优解构造的整体解不一定是最优的。动态规划法通过对若干局部最优解的比较，去掉了次优解。从而产生了更高一层次的局部最优解，保持了每个新产生的解都是该层次的局部最优解。相当于对较低层次的局部最优解进行贪心的选择而得到高一级的局部最优解，因而最终产生一个最高层次的局部最优解，它就是原问题所求的整体的最优解。 而贪心法是每阶段只作一个挑选，各阶段的解一经选出就固定不变了，后阶段的局部最优是基于前阶段的挑选，所以往往只能求出次优解。10.8 10.8 动态规划法动态规划法（Dynamic ProgrammingDynamic Programming）55 与分治法比较 共同点：把一个大问题分解为若干较小的子问题，通过求解子问题而得到原问题的解。 不同点： 分治法每次分解的子问题数目比较少，子问题之间界限清楚，处理的过程通常是自顶向下进行； 动态规划法分解的子问题可能比较多