《动态规划近似串匹配》由会员分享，可在线阅读，更多相关《动态规划近似串匹配（51页珍藏版）》请在金锄头文库上搜索。
1、计算机算法 设计与分析导论南开大学 计算机科学与技术系刘璟1Chapter 7.Chapter 7. 动态规划动态规划 （Dynamic ProgrammingDynamic Programming）v 7.1 动态规划的基本原理v 7.2 最优二分搜索树(Optimal Binary Search Tree)v 7.3 近似串匹配(Approximate String Matching)问题27.1 动态规划的基本原理v7.1.1 Fibonacci数的计算 Fibonacci数又称为Fibonacci数列，定义为： F0=0, F1=1, Fn=Fn-1 + Fn-2 (n 2)计算Fib
2、onacci数列可由递归函数fibo完成。 递归函数fibo 由此可知，函数fibo的计算量随n的增加而急剧增加，n=6时 需25次调用，n=10时需177次调用，n=15时需1974次调用。进一步的研究表明，调用次数 An = 2Fn+1 - 1，其中， 。可以估计， ，其计算量是n的指数函数。3从Fig.7.1中可以看出，大量的调用过程是重复的，此算法可以 改进。 函数fibo的改进函数fib 这个程序的时间代价为O(n)阶。 4v7.1.2 矩阵连乘的顺序问题 1. 一个实实例 四个矩阵阵A1、A2、A3、A4相乘，设设其阶阶数分别为别为 A1：301，A2：140，A3：4010，A4
3、：1025。 因为为矩阵阵相乘满满足结结合律，所以可有下面五种（实际为实际为 六种 ）不同的运算次序，而且不同的运算次序所需的元素间间乘法 的次数不同，如下面所列： ( ( A1 A2 ) A3 ) A4 30140+304010+301025=20700 ( A1 A2 )( A3 A4 ) 30140+401025+304025=41200 ( A1( A2 A3 ) ) A4 14010+30110+301025=8200 A1( ( A2 A3 ) A4 ) 14010+11025+30125=1400 A1( A2( A3 A4 ) ) 401025+14025+30125=1175
4、05五种运算次序的计算结果相同，但所花费的时间代价相差极 大。如果某一应用问题需要经常进行矩阵连乘运算，应首先 确定最优的矩阵连乘的次序。2. 最优优矩阵连阵连 乘次序（Optimal Matrix Multiplication Order ）问题问题 给给定n个矩阵阵A1,A2,.,An的维维数为为d0,d1,d2,.,dn，即：Ai的维维 数为为di-1di(1in)。求一种连连乘次序，使得计计算时时所需的元 素乘法的总总数最少。 3. 算法的思路 如同上面实实例中所做的那样样，把所有可能的运算次序所需的 计计算量全计计算出来，选择选择 最小者，这这种方法称为穷举为穷举 法。不 过过，当n
5、值较值较 大时时，这这种方法的计计算量过过高。n个矩阵阵相乘 应应有（n-1）！种不同的运算次序，计计算每种运算次序所需的 时间时间 代价需要2(n-1)次乘法和n-2次加法运算。当n=11时时需要 7257.6万次乘法。6由于不能事先决定最初在何处进处进 行划分，所以分治策略难难以 解决这这个问题问题 。但这这个问题满问题满 足最优优子结结构性质质：即，当 选择选择 了进进行最外层层相乘的位置之后，其左右两边边的矩阵阵相乘 序列都必须须是时间时间 代价最小的，可以考虑虑采用贪贪心策略。 一种使用贪心策略的解决方法是：每次优先选择其相乘代价 最小的两个矩阵。例如在本实例中，A1A2A3A4有三
6、个可能 的相邻矩阵乘积，其中A2A3的代价400为最小。那么首先完 成A2A3，在余下的两个可能的相邻矩阵乘积中：30110和 11025相比较，后者较小。于是得到的解为A1( ( A2 A3 ) A4 ) ，与穷举法的最优结果一致。不过该贪心策略不能保证得到 最优解。例如反例：矩阵A、B、C，维数分别为：401，120，2050，(AB)C 40120+402050=40800A(BC) 12050+40150=30007另外一种采用贪贪心策略的方法是，对对于n个矩阵阵A1. An的维维 数序列d0.dn，每次从d1.dn-1中取最大值di，首先进行Ai与 Ai+1的乘法使最大的维数仅参加一
7、次乘法运算，这样做有可能 有利于减少矩阵连乘的计算量。使用这一策略，对上面的两 个简单实例进行计算，其结果都是正确的。但是这个贪心算 法仍然不能总是找出最优解。 可以从Fibonacci数的计算得到启发，采用动态规划的方法设 计算法。最简单的递归算法描述如下： 递归算法MinCost 8此算法的递归过递归过 程中，存在与fibo函数相似的地方，即会有 大量的重复调调用，其调调用关系如Fig7.2所示，其中n=4。 9递归函数MinCost的调用过程在n=4时共27次，n=5时为81次 ，n=6时为249次，当n增大时，计算量急剧增加。如果采用自 底向上的计算方式，函数MinCost(1,n)的
8、计算代价将大大减少 。其计算过程为： MinCost(1,1)=MinCost(2,2)=MinCost(3,3)=MinCost(4,4)=0 MinCost(1,2)=MinCost(1,1)+MinCost(2,2)+d0d1d2=30140=1 200类似地， 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时为1
9、5次，n=6时为21次。 104. 矩阵连乘的DP算法 设矩阵个数为n，维数为dimn+1（n+1个值），同时用数组 MultiOrdern保存程序运行时得到的最优乘法顺序，可得： 算法7.1 最优矩阵连乘算法 MatrixOrder 函数MatrixOrder返回最优连乘次序所需的最小时间代价，同 时将最优次序保存在数组MultiOrder中，从此数组中得到最 优乘法次序的算法为：ExtractOrder 用上述算法计计算本节给节给 出的实实例，其结结果为为：最小代价为cost0n=1400， 最优优乘法次序MultiOrder1.3=2,3,1，即A1(A2A3)A4)。 11v7.1.3
10、 动态规划（DP）算法的基本条件 1. 最优优子结结构性质质 最优化原理。其特征是：当要求一个问题问题 的最优优解时时，构成 整体解的子问题问题 的解也必须须是最优优的。例如，为为了使计计算n 个矩阵连阵连 乘A1A2.An的代价最小，无论最后一次乘法的位 置k在何处（1k=0;i-)for(j=i+1;j1)k=lastlowhigh;ExtractOrder(low,k,last,MultiOrder);ExtractOrder(k,high,last,MultiOrder);MultiOrdernext+1=k; 返回46算法7.2 求Fibonacci数的备忘录算法MemoFib in
11、t MemoFib(int n)int dictn=0,0,.,0;int f1,f2;if(nRlowhigh)BuildTree(Rlowhigh+1,high,root.right);return; 返回50算法7.4 近似串匹配算法ASM int ASM(char P, char T, int m, int n, int K)int i,j,k,Dmn;for(j=1;j=n;j+) D0j=0;for(i=0;i=m;i+) Di0=i;for(j=1;j=n;j+)for(i=1;i=m;i+)if(Pi=Tj)Dij=minDi-1j-1,Di-1j+1,Dij-1+1;elseDij=minDi-1j-1+1,Di-1j+1,Dij-1+1;if(Dmj=K) return j; 返回51
