|
第九日：动态规划
今天开始来点有意思的
分治思想将问题分解为独立的子问题
解决子问题，并将答案合并就可以得到总问题的解
但是，很多情况下，分解开的子问题之间并不是相互独立的
动态规划方法利用了这种相关性，给出了一种通用的解决方案
动态规划可以解决这样一类问题：
1、如果问题的解决是需要分阶段的（可以分解为子问题）
2、每个子问题的解决都依赖于之前阶段子问题的解决，也就是说，存在子子问题，子问题和子子问题之间存在相关性，子问题共享子子问题的解
3、每个子子问题只出现一次，或者说，只有一个答案，存在最优解。这样，我们就可以建一个表，把它们记下来
用空间换取时间，这个道理说出来，大家都能理解
可是真正第一个提出问题并想到这种解决方法的人，无疑是天才
动态规划通常用于解决“最优问题”
这类问题通常存在很多解决方案，每个方案都对应一个值
我们希望求出得到最优(最大、最小)值的那个解决方案
动态规划算法的解决步骤可以采取以下四步
1、刻画最优解的结构
2、以递归的方法求最优解
3、回推，求得最优解的值
举一个矩阵连乘的例子
有一个矩阵序列(A_1,A_2,...,A_n)
如果我们希望计算矩阵的乘积A_1A_2...A_n
矩阵乘法仅定义了两两相乘的规则
一个p*q的矩阵和一个q*r的矩阵相乘，最终获得一个p*r的矩阵
算法如下：
MATRIX-MULTIPLY(A,B )
1 if columns[A] <> rows[B] //只有第一个矩阵的列数和第二个矩阵的行数相同，两个矩阵才可以相乘
2 then error "矩阵不相容"
3 else for i <- 1 to rows[A]
4 do for j <- 1 to columns[B]
5 do C[i,j] <- 0
6 for k <- 1 to columns[A]
7 do C[i,j] <- C[i,j] + A[i,k] * B[k,j]
8 return C
可以看出，为了计算两个矩阵的乘积，一共要进行(p*q*r)次乘法运算
我们的目标是要尽量减少连乘时乘法运算的次数，以加快运算速度
以三个矩阵连乘为例
我们有以下两种种计算最终结果的运算顺序
A_1(A_2A_3)
(A_1A_2)A_3
假设它们分别是10×100,100×5,5×50的矩阵
那么，第一种顺序的乘法次数为：100*5*50+10*100*50 = 25000+50000 = 75000
第二种顺序的乘法次数为： 10*100*5+10*5*50 = 5000+2500 = 7500
差距还是很大di
考虑这个问题的特点，乘法次数与矩阵的内容无关，仅与矩阵的下标相关
我们要做的就是给矩阵加括号，事实上也就是给下标加括号
n个矩阵连乘，加括号的方法一共有
P(n)={
1, if n = 1
sigma(k=1, to n-1, P(k)P(n-k)), if n >= 2
}
将相邻矩阵的重复下标去除后，矩阵序列A的下标序列记为：
p=(p_0,p_1,...,p_n)
解决问题的第一步是找到最优解的结构，也就是如何通过子问题的最优解构建总问题的最优
我们将子问题的最优解记为m[i,j]，如果求得了i=1,j=n时得m，问题就解决了
对于n个矩阵连乘，无论如何加括号，最终总是可以分解为两个矩阵的乘法
可以简记为(A_1...A_i)*(A_i+1...A_n)
前面括号里面乘积是一个矩阵，后面也是
那么这样一组括号总的乘法次数为
m[1,i]+m[i+1,n]+p_0*p_i*p_n
然后是递推求解过程
n个矩阵一个有n-1组括号
所以
m[1,n]=
={
0, if n = 1
min{m[1,k]+m[k+1,n]+p_0*p_k*p_n}, if n > 1
}
m[i,j]{
0, if i = j
min{m[i,k]+m[k+1,j]+p_i-1*p_k*p_j}, if i < j
}
通过序列p，可以把每个m[i,j]都计算出来，记录它们的结果
一共需要记录(n*(n+1)/2)个结果
最后，通过这个公式
m[i,i+1]=p_i-1*p_i*p_i+1
就可以得到最终结果了
这样只是得到了最终结果的值，如果我们希望知道括号是如何加的(对连乘计算过程有意义)
还需要在每次计算m[i,j]时，记录k的取值
循环形式的具体算法：
MATRIX-CHAIN-ORDER(p)
1 n <- length[p] - 1
2 for i <- 1 to n
3 do m[i,i] <- 0
4 for l <- 2 to n //l表示链长
5 do for i <- l to n-l+1
6 do j <- i+l-1
7 m[i,j] <- infinite
8 for k <- i to j-1
9 do q <- m[i,k]+m[k+1,j]+p_i-1*p_k*p_j
10 if q < m[i,j]
11 then m[i,j] <- q
12 s[i,j] <- k
13 return m and s
递归形式的算法留给大家自己写一下
这种方法大致运行时间为o(n^3)
空间消耗前面计算过，是n*(n+1)/2
作业：
1、写出递归形式的连乘算法
2、计算下标序列为
(5,10,3,12,5,50,6)
的矩阵连乘所需的最少乘法数
试着通过直觉提出一种算法
如果和你通过以上算法得到的答案一致的话
能不能证明这种直觉方法总是有效的？
|
