动态规划 - 矩阵连乘问题

给定n+1个矩阵[A0, A1, A2, ……, An-1]，其中Ai与Ai+1是可乘的，i=0,1,2,...,n-2。

矩阵乘法满足结合律。考察这n个矩阵的连乘积，得出运算次数最少的结合。

首先，考虑两个矩阵相乘。

如果A、B两个矩阵可以相乘，那么A、B的形式必定满足：A[p][q]、B[q][r]，

设C=A*B，那么C满足C[p][r]

C[i][j]=A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][k]*B[k][j] + ... + A[i][q-1]*B[q-1][j]，其中k=0,1,2,...,q-1

一横 一竖 对应相乘再相加，共q次乘法，q次加法

C=C[0][0],...C[i][j],...C[p-1][r-1]，其中，i=0,1,2,...,p-1；j=0,1,2,...,r-1

所以，C=A*B 共需p*q*r次乘法。

例子：三个矩阵A1，A2，A3，分别为10*100,100*5,5*50

按照(A1*A2)*A3，需要 10*100*5+10*5*50=7500 次乘法

按照A1*(A2*A3)，需要 10*100*50+100*5*50=75000 次乘法

由此，可以看出，矩阵连乘时，如何结合，对最终的运算量影响极大。因此，需要在开始运算连乘积之前，得出如何使用结合律使得运算量最小。

(1)最优子结构

整个问题的最优解，一定由一些子问题的最优解组成

连乘矩阵的维度必然符合:

P0*P1 P1*P2 P2*p3 ... Pi*Pi+1 ... Pn-1*Pn

A0 A1 A2 ... Ai ... An-1

将Ai*...*Aj记作A[i][j]，那么整个问题即为A[0][n-1]

假设A[0][n-1]的最优解为 A[0][k] * A[k+1][n-1]，那么A[0][k]和A[k+1][n-1]也要分别取到对应的最优解，如果不是，那么就矛盾了。

整个问题的最优解包含了子问题的最优解，这种性质称为 最优子结构性质

(2) 建立递归关系

自顶向下，建立递归关系，至最原子态的问题

由(1)可得到求出A[0][n-1]的最优解，即是整个问题的最优解。

设置min[i][j]为A[i][j]的最优解，0<=i<=j<=n-1

如果i==j，A[i][j]为Ai自身，无计算，故min[i][i]=0，i=0,1,2,...,n-1

如果i!=j，则取i~j之间的每种结合的最小值。假设A[i][j]的最优解在A[k]和A[k+1]之间断开，那么min[i][j] = min[i][k] + min[k+1][j] + Pi*Pk+1*Pj+1。

所以min[i][j] =MIN(min[i][k] + min[k+1][j] + Pi*Pk+1*Pj+1) k=i,i+1,...,j

(3) 自底向上，计算各个子问题的最优解

由最原子态的问题的最优解开始，构建全部子问题的最优解，并记录过程

由(2)可看出，很容易即可写出一个递归算法来算出min[0][n-1]

((A0(A1A2))((A3A4)A5))15125