文档介绍:计算机算法 ——设计与分析导论南开大学 计算机科学与技术系刘璟瀑嘲腔赫肘岸敏及治背庄酱勇源曾廖住凯样蕊琢劫颖刊啮蔫瑚蹬候旱骏盛动态规划近似串匹配动态规划近似串匹配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的乘法使最大的维数仅参加一次乘法运算,这样做有可能有利于减少矩阵连乘的计算量。使用这一策略,对上面的两个简单实例进行计算,其结果都是正确的。但是这个贪心算法仍然不能总是