第四章动态规划法.ppt

文档介绍：第四章动态规划
1
算法设计与分析
矩阵连乘问题
给定n个矩阵:A1, A2, …, An,其中Ai与Ai+1是可乘的。确定一种连乘的顺序,使得矩阵连乘的计算量为最小。
设A和B分别是p×q和q×r的两个矩阵,则乘积C=AB为p×r的矩阵,计算量为pqr次数乘。
但是对于多于2个以上的矩阵连乘,连乘的顺序却非常重要,因为不同的顺序的总计算量将会有很大的差别。
2
算法设计与分析
不同计算顺序的差别
设矩阵A1, A2和A3分别为10×100, 100×5和5×50的矩阵,现要计算A1A2A3 。
若按((A1A2)A3)来计算,则需要的数乘次数为10×100×5 + 10×5×50 = 7500
若按(A1(A2 A3))来计算,则需要的数乘次数为100 ×5 ×50+ 10×100×50 = 75000
后一种计算顺序的计算量竟是前者的10倍!
所以,求多个矩阵的连乘积时,计算的结合顺序是十分重要的。
3
算法设计与分析
不同计算顺序的数量
设n个矩阵的连乘积有P(n)个不同的计算顺序。
先在第k个和第k+1个矩阵之间将原矩阵序列分成两个矩阵子序列,k=1,…,n;再分别对两个子序列完全加括号,最后对结果加括号,便得到原序列的一种完全加括号方式。
由此可得出关于P(n)的递归式:
P(n) =
n = 1
n–1
∑P(k) P(n–k) n>1
k=1
解此递归方程可得P(n) = C(n–1),其中
C(n) =
1
n+1
2n
n
= Ω(4n/n3/2)
所以P(n)随n的增长呈指数增长。因而穷举搜索法不是有效的算法。
4
算法设计与分析
分解最优解的结构
将矩阵连乘积AiAi+1…Aj记为A[i: j]。
若A[1: n] 的一个最优解是在矩阵Ak和Ak+1处断开的,即A[1: n] = (A[1: k] A[k+1: n]),则A[1: k]和A[k+1: n]也分别是最优解。
事实上,若A[1: k]的一个计算次序所需计算量更少的话,则用此计算次序替换原来的次序,则得到A[1: n]一个更少的计算量,这是一个矛盾。同理A[k+1: n]也是最优解。
最优子结构性质:最优解的子结构也最优的。
5
算法设计与分析
建立递归关系
令m[i][j] , 1≤i, j≤n,为计算A[i, j] 的最少数乘次数,则原问题为m[1][n]。
当i = j时,A[i, j]为单一矩阵, m[i][j] = 0;
当i<j时,利用最优子结构性质有:
m[i][j] =
min{m[i][k] + m[k+1][j] + pi–1pkpj}
i≤k<j
其中矩阵Ai ,1≤i≤n,的维数为pi–1×pi。
根据此递归式就可以直接用递归程序来实现。
6
算法设计与分析
直接递归的时间复杂性
根据前面的递归式不难得出的时间复杂性为
n–1
1 + ∑(T(k) + T(n–k) + 1)
k=1
T(n) ≥
n–1
= 1 + (n – 1) +∑(T(k) + T(n–k))
k=1
n–1 n–1
= n +∑T(k) + ∑T(n–k)
k=1 k=1
可用数学归纳法证明T(n)≥2n–1 = Ω(2n)。
直接递归算法的时间复杂性随n的指数增长。
n–1
= n + 2∑T(k)
k=1
7
算法设计与分析
直接递归中有大量重复计算
直接递归中有大量重复计算,如A[1: 4]计算中:
1: 4
1: 1
2: 4
1: 2
3: 4
1: 3
4: 4
2: 2
3: 4
2: 3
4: 4
1:1
2: 2
3: 3
4: 4
1: 1
2: 3
1: 2
3: 3
3: 3
4: 4
2: 2
3: 3
2: 2
3: 3
1: 1
2: 2
图中红框标出的都是重复计算。
8
算法设计与分析
消除重复的计算
要消除重复计算,可在在计算过程中保存已解决的子问题的答案。这样,每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免重复计算。
计算方式可依据递归式自底向上地进行。
注意到在此问题中,不同的有序对(i, j)就对应不同的子问题,2+ n = (n2)个。
这样便可以得到多项式时间的算法。
9
算法设计与分析
自底向上的计算
例如对于A1A2A3A4,依据递归式以自底向上的方式计算出各个子问题,其过程如下:
m[1][1]
m[2][2]
m[3][3]
m[4][4]
m[1][2]
m[2][3]
m[3][4]
m[1][3]
m[2][4]
m[2][4]
其中
m[i][i] = 0