动态规划 - 矩阵链的乘法问题

佚名 4年前 (2020-04-03) 算法 1030人围观抢沙发百度已收录

1.1具体实例
 1.2子问题的划分和递推方程
2.动态规划算法的递归实现
SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
3.动态规划算法的迭代实现
4.动态规划算法的要素

这里用矩阵链的乘法问题来说明动态规划算法的设计要素。

$A_1,A_2,..,A_n$表示$n$个矩阵的序列，其中$A_i$为$P_{i-1} \times P_i$阶矩阵，$i=1,2,...,n$。
向量$P=<P_0,P_1,P_2..P_i>$表示矩阵链的输入，其中$P_0$是$A_1$的行数，$P_1$是$A_1$的列数，$P_1$是$A_2$的行数，以此类推。
计算这个矩阵需要做$n-1$次两个矩阵的相乘运算，可以用$n-1$对括号表示运算次序。
因为矩阵乘法满足结合律，所以无论采用那种顺序，最后结果都一样，但是采用不同的顺序计算的工作量不同。如何定义两个矩阵相乘的工作量呢？
所以假设$A_1$有$i$行$k$列，$A_2$有$k$行$j$列。所以$A_1$$A_2$相乘后的矩阵有$i$行$j$列，含$ij$个元素。
以元素相乘作为基本运算，乘积中每个元素的计算都需要做j次乘法，于是计算$A_1A_2$总共需要$ijk$次乘法。

1.1具体实例

假设输入的是$P=<10,100,5,50>$,说明有$3$个矩阵相乘。其中，
$A_1:10 \times 100$
$A_2:100\times 50$
$A_3:5 \times50$
有两种乘法次序：
$(A_1A_2)A_3$
$A_1(A_2A_3)$
执行第一种运算的基本运算次序：$10 \times 100\times5 + 10 \times 5 \times 50=7500$
执行第二种运算的基本运算次序：$10 \times 100\times50 + 100 \times 5 \times 50=75000$
工作量相差达10倍！
所以我们的问题是：给定向量P，确定一种乘法次序，使得基本运算的总次数最少。
蛮力算法时间复杂度太大，这里先不讨论。
我们尝试用动态规划算法，从子问题的划分，递归方程的确定，递归和迭代的实现方法，复杂度分析等方面介绍动态规划算法。

1.2子问题的划分和递推方程

我们的优化目标是：基本运算次数的最小化。
如何界定子问题的边界？令$A_i..n$表示输入的矩阵链。
如果从前向后划分，得$A_{1..i}$，i=1,2,...,n，得到的子问题只有后边界。但是在计算子问题$A_{1..j}$，j>i时，我们不仅需要知道子问题$A_{1..i}$，也得知道$A_{i+1..j}$的信息。
这说明子问题的划分需要前后两个边界。
用$A_i..j$定义矩阵链$A_i,A_{i+1},..,A_j$相乘的子问题，$m[i,j]$表示得到乘积$A_{i..j}$所用到的最小基本运算次数。
假定最后一次乘积发生在矩阵链$A_{i..k}$和$A_k+1..j$之间，即
$A_iA_{i+1}..A_j=(A_iA_{i+1}..A_k)(A_{k+1}A_{k+2}..A_j)$
$k=i,i+1,...,j-1$
所以子问题$A_i..j$的计算依赖于子问题$A_i..A_k$和$A_{k+1}..A_j$的计算结果。
即$m[i,j]$依赖于$m[i,k]$和$m[k+1,j]$的值。

k代表子问题的划分问题，考虑所有可能的划分，$i<=k<=j$，从中比较出最小的值。
$P_{i-1}P_kP_j$是最后把两个子矩阵链$A_{i..k}$和$A_{k+1}..j$的结果矩阵相乘所做的基本运算次数。
当$i=j$时，矩阵链只有一个矩阵$A_i$，这时乘法次数是$0$，对应了递推式的初值。
所以这个问题是满足优化原则的。因为当$m[i,j]$达到最小值时，子问题的优化函数值$m[i,k]$和$m[k+1,j]$也是最小的。

2.动态规划算法的递归实现

为了确定每次相乘时加括号的位置，需要设计表$s[i,j]$记录$m[i,j]$达到最小值时k的划分位置。
算法RecurMatrixChain(P,i,j)
输入：矩阵链$A_i..j$的输入为向量$P=<P_0,P_1,P_2..P_i>$，其中$i<=k<=j$
输出：计算$A_{i..j}$的所需最小乘法次数$m[i,j]$和最后一次运算的位置$s[i,j]$

if i=j
then m[i,j] <- 0 ; s[i,j] <- i ; return m[i,j]
m[i,j] <- 无穷
s[i,j] <- i
for k <- i to j-1 do        //考虑所有可能的划分位置
    q <- RecurMatrixChain(P,i,k) + RecurMatrixChain(P,k+1,j) + Pi-1PkPj
    if q < m[i,j]
    then m[i,j] <- q
         s[i,j] <- k
return m[i,j]

求解n个矩阵相乘，只需代入i=1，j=n。
下面考虑时间复杂度

算法在行5执行for循环，k从1到n-1。
每次进入循环体都在行6进行两个子问题的递归求解，其余工作量都是常数时间。
化简得：

现在介绍一个定理：当$n>1$时，$T(n)= \Omega(2^{n-1}) $ 证明：$n=2，T(2)>=C=C_12^{n-1}，C_1=C/2$为某个正数假设对于任何小于n大于等于2的k，$T(k)>=C_12^{{k-1}$，则存在某个常数$C}’$，使得

可以看到，通过使用了动态规划的设计思想，相比于蛮力算法，时间复杂度有所改善，但是并没有得到多项式时间的高效算法。为什么？
以矩阵链$A_{1..5}$为例：

时间复杂度高的原因：在递归调用中同一个子问题被多次重复计算。
在整个递归计算中总计产生了$1+8+24+32+16=81$个子问题。
规模为1的子问题有5个，以此类推，得到不同的子问题个数只有$5+4+3+2+1=15$个
说明算法计算的81个子问题中有许多是重复的。

3.动态规划算法的迭代实现

迭代计算的关键

每个子问题只计算一遍
迭代过程
1. 从最小子问题开始
2. 考虑计算顺序，以保证后面用到的值前面已经计算好
3. 存储结构保存计算结果--备忘录（存储子问题的优化函数值和划分边界）
解的追踪
1. 设计标记函数标记每步的决策
2. 考虑根据标记函数追踪解的算法
  
  $r$为链长
  算法MatrixChain(P,n)
  输入：矩阵链$A_{1..n}$的输入向量$P=<P_0,P_1,P_2..P_i>$
  输出：计算$A_{i..j}$的所需最小乘法次数$m[i,j]$和最后一次运算的位置$s[i,j]$

令所有的m[i,j]得初值为0
for r<-2 to n do                                //r为链长（子问题规模）
    for i<-1 to n-r+1                           //左边界i，n-r+1是最后一个r链的前边界
        j<-i+r-1                                //右边界
        m[i,j] <- m[i+1,j] + Pi-1PiPj
        s[i,j] <- i
        for k<-i+1 to j-1 do
            t<-m[i,k]+m[k+1,j]+Pi-1PiPj
            if t<m[i,j]
            then m[i,j]<-t
                 s[i,j]<-k

时间复杂度：
行2,3,7都是$O(n)$，嵌套循环执行$O(n^3)$次，内部为$O(1)$，$W(n)=O(n^3)$

解的追踪：
$S[1,5]=3 => (A_1A_2A_3)(A_4A_5)$
$S[1,3]=1 => A_1(A_2A_3)$
输出：
计算顺序：$(A_1(A_2A_3))(A_4A_5)$
最少的乘法次序：$m[1,5]=11875$