文档介绍：动态规划法(Dynamic Programming)
与分治法类似,动态规划法
也是把问题一层一层地分解为规模逐渐减小的同类型的子问题。
动态规划法与分治法的一个重要的不同点在于,
用分治法分解后得到的子问题通常都是相互独立的,
而用动态规划法分解后得到的子问题很多都是重复的。
因此,对重复出现的子问题,只是在第一次遇到时才进行计算,
然后把计算所得的结果保存起来;当再次遇到该子问题时,
就直接引用已保存的结果,而不再重新求解。
下面我们先看一个例子: 矩阵连乘问题
. 设有矩阵M1,M2,M3,M4,
其维数分别是10´20, 20´50, 50´1 和1´100,
现要求出这4个矩阵相乘的结果。
我们知道,若矩阵A的维数是p´q,矩阵B的维数是q´r,
则A与B相乘后所得矩阵AB的维数是p´r。
按照矩阵相乘的定义,
求出矩阵AB中的一个元素需要做q次乘法(及q-1次加法)。
这样,要计算出AB就需要做p´q´r次乘法。
为简单起见,且由于加法比同样数量的乘法所用时间要少得多,
故这里我们暂不考虑加法的计算量。
由于矩阵连乘满足结合律,故计算矩阵连乘的方式可以有多种。
例如,我们可以按M1(M2(M3M4))的方式去计算,
也可以按(M1(M2M3))M4的方式去计算,所得结果是相同的。
但是值得注意的是,
按前一方式计算需要做125,000次乘法,
而按后一方式计算只需要做2,200次乘法。
由此可见,矩阵连乘的运算次序对于所需要的计算量
(所需乘法次数)有着极大的影响。
M3M4:50*1*100=5,000;M2(M3M4):20*50*100=100,000
M1(M2(M3M4)):10*20*100=20,000
(M2M3):20*50*1=1000; (M1(M2M3)):10*20*1=200 ;
(M1(M2M3))M4:10*1*100=1000
但另一方面,按前一章所述,
n个矩阵连乘的加括号的方法数是一Catalan数,
即加括号的方法数是指数量级的,
因此,把每一种加括号的方法所需乘法次数
都一一加以检查和比较是不太现实的。
如何解决这一问题?分析:
设要求出矩阵连乘MiMi+1┅Mj-1Mj(i<j)所需的最少乘法次数。
因共有j-i+1个矩阵,故称这个矩阵连乘的规模是j-i+1。
按照做最后一次乘法的位置进行划分,
该矩阵连乘一共可分为j-i种情况即有(j-i)种断开方式:
Mi(Mi+1┅Mj),(MiMi+1)(Mi+2┅Mj),┅,(MiMi+1┅Mj-1)Mj。
其中任一对括号内的矩阵个数(即规模)不超过j-i。
若我们已知任一个规模不超过j-i的矩阵连乘所需的最少乘法次数,我们就可以很容易地计算出矩阵连乘MiMi+1┅Mj-1Mj(i<j)
所需的最少乘法次数,其方法如下。
将上述的j-i种情况表示为通式:(Mi┅Mk) (Mk+1┅Mj)(i≤k<j)。记第t个矩阵Mt的列数为rt,并令r0为矩阵M1的行数。
则Mi┅Mk连乘所得是ri-1´rk维矩阵,
Mk+1┅Mj连乘所得是rk´rj维矩阵,
故这两个矩阵相乘需要做ri-1´rk´rj次乘法。
由于在此之前我们已知
任一个规模不超过j-i的矩