《计算机算法设计与分析-Chapter7动态规划》由会员分享，可在线阅读，更多相关《计算机算法设计与分析-Chapter7动态规划（50页珍藏版）》请在金锄头文库上搜索。
1、计算机算法设计与分析,Chapter7.动态规划（DynamicProgramming）,7.1动态规划的基本原理7.2最优二分搜索树(OptimalBinarySearchTree)7.3近似串匹配(ApproximateStringMatching)问题,3,7.1动态规划的基本原理,7.1.1Fibonacci数的计算Fibonacci数又称为Fibonacci数列，定义为：F0=0,F1=1,Fn=Fn-1+Fn-2(n2)计算Fibonacci数列可由递归函数fibo完成。递归函数fibo由此可知，函数fibo的计算量随n的增加而急剧增加，n=6时需25次调用，n=10时需177次调
2、用，n=15时需1974次调用。进一步的研究表明，调用次数An=2Fn+1-1，其中，。可以估计，其计算量是n的指数函数。,从Fig.7.1中可以看出，大量的调用过程是重复的，此算法可以改进。函数fibo的改进函数fib这个程序的时间代价为O(n)阶。,7.1.2矩阵连乘的顺序问题1.一个实例四个矩阵A1、A2、A3、A4相乘，设其阶数分别为A1：301，A2：140，A3：4010，A4：1025。因为矩阵相乘满足结合律，所以可有下面五种（实际为六种）不同的运算次序，而且不同的运算次序所需的元素间乘法的次数不同，如下面所列：(A1A2)A3)A430140+304010+301025=207
3、00(A1A2)(A3A4)30140+401025+304025=41200(A1(A2A3)A414010+30110+301025=8200A1(A2A3)A4)14010+11025+30125=1400A1(A2(A3A4)401025+14025+30125=11750,五种运算次序的计算结果相同，但所花费的时间代价相差极大。如果某一应用问题需要经常进行矩阵连乘运算，应首先确定最优的矩阵连乘的次序。2.最优矩阵连乘次序（OptimalMatrixMultiplicationOrder）问题给定n个矩阵A1,A2,.,An的维数为d0,d1,d2,.,dn，即：Ai的维数为di-1d
4、i(1in)。求一种连乘次序，使得计算时所需的元素乘法的总数最少。3.算法的思路如同上面实例中所做的那样，把所有可能的运算次序所需的计算量全计算出来，选择最小者，这种方法称为穷举法。不过，当n值较大时，这种方法的计算量过高。n个矩阵相乘应有（n-1）！种不同的运算次序，计算每种运算次序所需的时间代价需要2(n-1)次乘法和n-2次加法运算。当n=11时需要7257.6万次乘法。,由于不能事先决定最初在何处进行划分，所以分治策略难以解决这个问题。但这个问题满足最优子结构性质：即，当选择了进行最外层相乘的位置之后，其左右两边的矩阵相乘序列都必须是时间代价最小的，可以考虑采用贪心策略。一种使用贪心策
5、略的解决方法是：每次优先选择其相乘代价最小的两个矩阵。例如在本实例中，A1A2A3A4有三个可能的相邻矩阵乘积，其中A2A3的代价400为最小。那么首先完成A2A3，在余下的两个可能的相邻矩阵乘积中：30110和11025相比较，后者较小。于是得到的解为A1(A2A3)A4)，与穷举法的最优结果一致。不过该贪心策略不能保证得到最优解。例如反例：矩阵A、B、C，维数分别为：401，120，2050，(AB)C40120+402050=40800A(BC)12050+40150=3000,另外一种采用贪心策略的方法是，对于n个矩阵A1.An的维数序列d0.dn，每次从d1.dn-1中取最大值di，
6、首先进行Ai与Ai+1的乘法使最大的维数仅参加一次乘法运算，这样做有可能有利于减少矩阵连乘的计算量。使用这一策略，对上面的两个简单实例进行计算，其结果都是正确的。但是这个贪心算法仍然不能总是找出最优解。可以从Fibonacci数的计算得到启发，采用动态规划的方法设计算法。最简单的递归算法描述如下：递归算法MinCost,此算法的递归过程中，存在与fibo函数相似的地方，即会有大量的重复调用，其调用关系如Fig7.2所示，其中n=4。,递归函数MinCost的调用过程在n=4时共27次，n=5时为81次，n=6时为249次，当n增大时，计算量急剧增加。如果采用自底向上的计算方式，函数MinCos
7、t(1,n)的计算代价将大大减少。其计算过程为：MinCost(1,1)=MinCost(2,2)=MinCost(3,3)=MinCost(4,4)=0MinCost(1,2)=MinCost(1,1)+MinCost(2,2)+d0d1d2=30140=1200类似地，Mincost(2,3)=d1d2d3=14010=400；Mincost(3,4)=d2d3d4=401025=10000；在第二步计算MinCost(1,3)和MinCost(2,4)，最后计算MinCost(1,4)。由此可以看出，n=4时函数MinCost(1,4)的计算量是4+3+2+1=10次，n=5时为15次，
8、n=6时为21次。,4.矩阵连乘的DP算法设矩阵个数为n，维数为dimn+1（n+1个值），同时用数组MultiOrdern保存程序运行时得到的最优乘法顺序，可得：算法7.1最优矩阵连乘算法MatrixOrder函数MatrixOrder返回最优连乘次序所需的最小时间代价，同时将最优次序保存在数组MultiOrder中，从此数组中得到最优乘法次序的算法为：ExtractOrder用上述算法计算本节给出的实例，其结果为：最小代价为cost0n=1400，最优乘法次序MultiOrder1.3=2,3,1，即A1(A2A3)A4)。,7.1.3动态规划（DP）算法的基本条件1.最优子结构性质最优化
9、原理。其特征是：当要求一个问题的最优解时，构成整体解的子问题的解也必须是最优的。例如，为了使计算n个矩阵连乘A1A2.An的代价最小，无论最后一次乘法的位置k在何处（1kn），其左右两部分A1.Ak，Ak+1.An的乘积也必须是代价最小的。这也可用最短路径问题来说明：若V1V2.Vn是一条从V1到Vn的最短路径，那么这条路径的任何一段，比如从Vi到Vj（1ijn）也必须是一条最短路径。2.子结构重迭性质简单的递归程序解法都是一种自顶向下进行递归分解的过程，其中包含了大量的重复调用，在这种情况下采用动态规划方法特别有效。因此，问题中这种子结构重迭性质是采用动态规划方法的另一个条件。动态规划算法的
10、一个特征是自底向上，它可以大幅度减少计算代价。,解决这类具有子结构重迭性质的问题还有另外一种被称为备忘录（memorization）方法的自顶向下的递归方式。其思想是：由程序设置“备忘录”，每计算出一个新的子结构的解时，都保存起来。当遇到一次递归时，判断是否已经计算，如果已经计算，只需取出先前保存的结果即可。这种方式与动态规划算法相比，要增加保存与检索中间结果的代价。算法7.2求Fibonacci数的备忘录算法MemoFib,7.2最优二分搜索树（OptimalBinarySearchTree）,7.2.1OBST问题二分字典树是构造数据存储与检索系统的一种方便形式，例如一个翻译系统需要一个字
11、典数据库。可以按照单词的字典顺序构造一个二分搜索树，能获得较高的搜索效率。假定字典中只包含15个单词：and，cabbage，come，has，king，of，pig，ring，said，talk，the，thing，time，walrus，wing。按照字典顺序插入显然形成一个退化的二分树即线性链表，其平均搜索代价是(1+15)/2=8次单词比较。,采用Fig7.3中的二分搜索树，最多仅需4次比较，平均需要(1+22+34+48)/15=3.17次比较，因此完全二分搜索树具有最小的平均搜索代价。,在实用系统中，还要考虑到不同的单词在实际使用过程中被搜索的概率不同，例如，and、the等经常被
12、搜索，而pig、cabbage等则很少被搜索。因此若把and、the放在树的最底层必然增大词典的平均搜索代价，这时的平均搜索代价应为：即，二分搜索树T的平均搜索代价应为从根到各个单词节点在T中的路长Ci与其查找概率Pi乘积之和。当各个单词的查找概率不同时，完全二分搜索树就不一定最优了。例如，假定词典仅由4个单词cat、come、of、the组成，它们的查找概率分别为：cat:0.12，come:0.08，of:0.35，the:0.45,由这四个单词可以组成许多种不同的二分字典树，Fig7.4中给出了其中的三个。按照上面给出的计算方法，三棵树（a,b,c）的平均搜索代价分别为：cat:0.12
13、，come:0.08，of:0.35，the:0.45(a)0.08+2(0.12+0.35)+30.45=2.37次比较；/2,3为路径深度(a)0.35+2(0.08+0.45)+30.12=1.77次比较；(a)0.35+2(0.12+0.45)+30.08=1.73次比较。,平均搜索代价的差别说明，不同的二分搜索树在一定的查找概率条件下，性能是不同的。因此，在单词集合及其查找概率给定的条件下，构造一个平均搜索代价最小的二分搜索树的意义是很明显的。在实际问题中，还要考虑不成功的搜索，即查找给定单词集合之外的单词。这时可以把二分搜索树加以扩充，例如Fig7.4中的(c)，可以为这棵4个节点
14、的树增加5个外部节点，形成一棵新树，如Fig7.5所示。,其中4个内部节点表示单词集的4个单词，5个外部节点则表示检索其它单词时不成功的搜索路径。例如：搜索单词as，将到达最左边的外部节点，其代价为两次比较。,最优二分搜索树（OBST）问题可以描述为：已知：n个单词的查找概率p1,p2,.,pn和对应于n+1个外部节点的不成功查找概率q0,q1,q2,.,qn，。求：构造一种二分搜索树T，使平均搜索代价A(T)最小。解这个问题最简单的方法是把由n个单词（节点）组成的所有二分搜索树的平均搜索代价全算出来，取其最小者。不过，4个单词的二分搜索树有14种，7个单词的二分搜索树有429种就可知道，n较
15、大时，这种方法是根本行不通的。7.2.2动态规划算法的思路设n个单词为a1,a2,.,an，则由它们构成二分搜索树T1,n可以表示为Fig7.6的形式。其中ak(1kn)为T1,n的根，其左子树T1,k-1由a1.ak-1组成，右子树Tk+1,n由ak+1.an组成。,用代价函数Cost(low,high)表示由alow.ahigh及相应的外部节点blow-1,blow,.,bhigh组成的二分搜索树的最小代价。特别地，当high=low-1时表示空树，Cost(i,i-1)=0。Cost(low,high,r)表示指定以ar为根时，组成的二分搜索树的最小搜索代价。,如果T1,n是最优的，那么
16、T1,k-1，Tk+1,n两个子树也必然是最优的，因此，该问题具有最优子结构性质；另一方面，单词序列中任意几个相邻单词组成的子树将同时出现在多个包含它们的更大的树中，因此，子结构重迭性质也是很明显的。,T1,k-1是由a1至ak-1元素构成子树中最优者,权函数W(low,high)表示相应二分搜索树的所有节点的搜索概率之和，称为该树的权：特别地：W(i,i)=pi+qi-1+qi；W(i,i-1)=qi-1。（1in）。以上各式有如下的递推关系：Cost(low,high,r)=pr+W(low,r-1)+Cost(low,r-1)+W(r+1,high)+Cost(r+1,high)=W(low,high)+Cost(low,r-1)+Cost(r+1,high)Cost(low,high)=MinCost(low,high,r)|lowrhigh依照自底向上的顺序，很容易计算出Cost(1,n)以及最优树的各级子树的根。(注意路径的长度如何计算的,如,根结点r,在计算中最终结果为pr*1,而其他结点
