文档介绍：1第第5 5讲讲动态规划动态规划 2 学****要点: ?理解动态规划算法的概念。?掌握动态规划算法的基本要素?(1)最优子结构性质?(2)重叠子问题性质?掌握设计动态规划算法的步骤。?(1) 找出最优解的性质,并刻划其结构特征。?(2) 递归地定义最优值。?(3) 以自底向上的方式计算出最优值。?(4) 根据计算最优值时得到的信息,构造最优解。 3 ?通过应用范例学****动态规划算法设计策略。?(1)矩阵连乘问题; ?(2)最长公共子序列; ?(3)最大子段和?(4)凸多边形最优三角剖分; ?(5)多边形游戏; ?(6)图像压缩; ?(7)电路布线; ?(8)流水作业调度; ?(9)背包问题; ?( 10 )最优二叉搜索树。 4 ?动态规划算法与分治法类似, 其基本思想也是将待求解问题分解成若干个子问题算法总体思想算法总体思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = 5 ?但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时, 有些子问题被重复计算了许多次。算法总体思想算法总体思想 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 6 ?如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。算法总体思想算法总体思想 n= n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 n/2 T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n) 7动态规划基本步骤动态规划基本步骤?找出最优解的性质,并刻划其结构特征。?递归地定义最优值。?以自底向上的方式计算出最优值。?根据计算最优值时得到的信息,构造最优解。 8 ?完全加括号的矩阵连乘积可递归地定义为: ?设有四个矩阵,它们的维数分别是: ?总共有五中完全加括号的方式(1)单个矩阵是完全加括号的; (2)矩阵连乘积是完全加括号的,则可表示为 2个完全加括号的矩阵连乘积和的乘积并加括号,即 A ABC)( BC A?DCBA,,,10 50??A 40 10??B 30 40??C 530??D ))) (((D BC A))) (((DC AB) ))( ((D BC A ))) ((( CD BA )) )( (( CD AB 16000, 10500, 36000, 87500, 34500 完全加括号的矩阵连乘积完全加括号的矩阵连乘积 9矩阵连乘问题矩阵连乘问题?给定 n个矩阵,其中与是可乘的, 。考察这 n个矩阵的连乘积?由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。?若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用 2个矩阵相乘的标准算法计算出矩阵连乘积},..., ,{ 21nAAA iA 1?iA 1,..., 2,1??ni nAAA... 21 10 矩阵连乘问题矩阵连乘问题给定 n个矩阵{ A 1 ,A 2,…,A n},其中 Ai与 Ai+1 是可乘的, i=1 ,2…, n-1 。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。?穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。算法复杂度分析: 对于 n个矩阵的连乘积,设其不同的计算次序为 P(n )。由于每种加括号方式都可以分解为两个子矩阵的加括号问题: (A1...Ak)(Ak+1 … An) 可以得到关于 P(n )的递推式如下: )/4()(1 1)()( 1)( 2/3 11nnPn nknPkP nP n nk???????????????