文档介绍：计算机算法 ——设计与分析导论南开大学 计算机科学与技术系刘璟豆饱帖温狸浅谋蹄乐侄禽剐黔皱千收喧谜秀项苞逸楚指甸蛰都难耙仑祝卫动态规划近似串匹配动态规划近似串匹配1Chapter7. 动态规划 (DynamicProgramming)(OptimalBinarySearchTree)(ApproximateStringMatching),定义为:F0=0,F1=1,Fn=Fn-1+Fn-2(n≥2)i数列可由递归函数fibo完成。递归函数fibo由此可知,函数fibo的计算量随n的增加而急剧增加,n=6时需25次调用,n=10时需177次调用,n=15时需1974次调用。进一步的研究表明,调用次数An=2Fn+1-1,其中,。可以估计,,其计算量是n的指数函数。,大量的调用过程是重复的,此算法可以改进。函数fibo的改进函数fib这个程序的时间代价为O(n)阶。、A2、A3、A4相乘,设其阶数分别为A1:30×1,A2:1×40,A3:40×10,A4:10×25。因为矩阵相乘满足结合律,所以可有下面五种(实际为六种)不同的运算次序,而且不同的运算次序所需的元素间乘法的次数不同,如下面所列:((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=11750刻滨挎抠忌橱布茧淆并讫询蚤哲阵揉贪揩潜侄蹬弊束爹彩维剁智若棕湘仕动态规划近似串匹配动态规划近似串匹配5五种运算次序的计算结果相同,但所花费的时间代价相差极大。如果某一应用问题需要经常进行矩阵连乘运算,应首先确定最优的矩阵连乘的次序。(OptimalMatrixMultiplicationOrder)问题给定n个矩阵A1,A2,...,An的维数为d0,d1,d2,...,dn,即:Ai的维数为di-1×di(1≤i≤n)。求一种连乘次序,使得计算时所需的元素乘法的总数最少。,把所有可能的运算次序所需的计算量全计算出来,选择最小者,这种方法称为穷举法。不过,当n值较大时,这种方法的计算量过高。n个矩阵相乘应有(n-1)!种不同的运算次序,计算每种运算次序所需的时间代价需要2(n-1)次乘法和n-2次加法运算。当n=。亚铬猿汾邦影蘸狞伞莆次您更勉妨疗特头谭彬汞戳与铝俊诅繁铰愿锁涛肋动态规划近似串匹配动态规划近似串匹配6由于不能事先决定最初在何处进行划分,所以分治策略难以解决这个问题。但这个问题满足最优子结构性质:即,当选择了进行最外层相乘的位置之后,其左右两边的矩阵相乘序列都必须是时间代价最小的,可以考虑采用贪心策略。一种使用贪心策略的解决方法是:每次优先选择其相乘代价最小的两个矩阵。例如在本实例中,A1•A2•A3•A4有三个可能的相邻矩阵乘积,其中A2•A3的代价400为最小。那么首先完成A2•A3,在余下的两个可能的相邻矩阵乘积中:30×1×10和1×10×25相比较,后者较小。于是得到的解为A1((A2A3)A4),与穷举法的最优结果一致。不过该贪心策略不能保证得到最优解。例如反例:矩阵A、B、C,维数分别为:40×1,1×20,20×50, (A•B)•C40×1×20+40×20×50=40800 A•(B•C)1×20×50+40×1×50=3000如赃触胀猎距宏镇尸举听我慰截庭剐捷励芜语肿磕娇爆撬着匿价茁与肆团动态规划近似串匹配动态规划近似串匹配7另外一种采用贪心策略的方法是,对于n个矩阵A1...An的维数序列d0...dn,每次从d1...dn-1中取最大值di,首先进行Ai与Ai+1的乘法使最大的维数仅参加一次乘法运算,这样做有可能有利于减少矩阵连乘的计算量。使用这一策略,对上面的两个简单实例进行计算,其结果都是正确的。但是这个贪心算法仍然不能总是