资源描述：
《动态规划近似串匹配》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机算法 ——设计与分析导论南开大学计算机科学与技术系刘璟1Chapter7.动态规划（DynamicProgramming）7.1动态规划的基本原理7.2最优二分搜索树(OptimalBinarySearchTree)7.3近似串匹配(ApproximateStringMatching)问题27.1动态规划的基本原理7.1.1Fibonacci数的计算Fibonacci数又称为Fibonacci数列，定义为：F0=0,F1=1,Fn=Fn-1+Fn-2(n≥2)计算Fibonacci数列可由递归函数fibo完成。递归函数fibo由此可知，函数fibo的计
2、算量随n的增加而急剧增加，n=6时需25次调用，n=10时需177次调用，n=15时需1974次调用。进一步的研究表明，调用次数An=2Fn+1-1，其中，。可以估计，，其计算量是n的指数函数。3从Fig.7.1中可以看出，大量的调用过程是重复的，此算法可以改进。函数fibo的改进函数fib这个程序的时间代价为O(n)阶。47.1.2矩阵连乘的顺序问题1.一个实例四个矩阵A1、A2、A3、A4相乘，设其阶数分别为A1：30×1，A2：1×40，A3：40×10，A4：10×25。因为矩阵相乘满足结合律，所以可有下面五种（实际为六种）不同的运算次序，而且不同的
3、运算次序所需的元素间乘法的次数不同，如下面所列：((A1A2)A3)A430×1×40+30×40×10+30×10×25=20700(A1A2)(A3A4)30×1×40+40×10×25+30×40×25=41200(A1(A2A3))A41×40×10+30×1×10+30×10×25=8200A1((A2A3)A4)1×40×10+1×10×25+30×1×25=1400A1(A2(A3A4))40×10×25+1×40×25+30×1×25=117505五种运算次序的计算结果相同，但所花费的时间代价相差极大。如果某一应用问题需要经常进行矩阵连乘运算
4、，应首先确定最优的矩阵连乘的次序。2.最优矩阵连乘次序（OptimalMatrixMultiplicationOrder）问题给定n个矩阵A1,A2,...,An的维数为d0,d1,d2,...,dn，即：Ai的维数为di-1×di(1≤i≤n)。求一种连乘次序，使得计算时所需的元素乘法的总数最少。3.算法的思路如同上面实例中所做的那样，把所有可能的运算次序所需的计算量全计算出来，选择最小者，这种方法称为穷举法。不过，当n值较大时，这种方法的计算量过高。n个矩阵相乘应有（n-1）！种不同的运算次序，计算每种运算次序所需的时间代价需要2(n-1)次乘法和n-2
5、次加法运算。当n=11时需要7257.6万次乘法。6由于不能事先决定最初在何处进行划分，所以分治策略难以解决这个问题。但这个问题满足最优子结构性质：即，当选择了进行最外层相乘的位置之后，其左右两边的矩阵相乘序列都必须是时间代价最小的，可以考虑采用贪心策略。一种使用贪心策略的解决方法是：每次优先选择其相乘代价最小的两个矩阵。例如在本实例中，A1•A2•A3•A4有三个可能的相邻矩阵乘积，其中A2•A3的代价400为最小。那么首先完成A2•A3，在余下的两个可能的相邻矩阵乘积中：30×1×10和1×10×25相比较，后者较小。于是得到的解为A1((A2A3)A4
6、)，与穷举法的最优结果一致。不过该贪心策略不能保证得到最优解。例如反例：矩阵A、B、C，维数分别为：40×1，1×20，20×50，(A•B)•C40×1×20+40×20×50=40800A•(B•C)1×20×50+40×1×50=30007另外一种采用贪心策略的方法是，对于n个矩阵A1...An的维数序列d0...dn，每次从d1...dn-1中取最大值di，首先进行Ai与Ai+1的乘法使最大的维数仅参加一次乘法运算，这样做有可能有利于减少矩阵连乘的计算量。使用这一策略，对上面的两个简单实例进行计算，其结果都是正确的。但是这个贪心算法仍然不能总是找出最
7、优解。可以从Fibonacci数的计算得到启发，采用动态规划的方法设计算法。最简单的递归算法描述如下：递归算法MinCost8此算法的递归过程中，存在与fibo函数相似的地方，即会有大量的重复调用，其调用关系如Fig7.2所示，其中n=4。9递归函数MinCost的调用过程在n=4时共27次，n=5时为81次，n=6时为249次，当n增大时，计算量急剧增加。如果采用自底向上的计算方式，函数MinCost(1,n)的计算代价将大大减少。其计算过程为：MinCost(1,1)=MinCost(2,2)=MinCost(3,3)=MinCost(4,4)=0Min
8、Cost(1,2)=MinCost(1,1)+Min
