动态规划算法学习十例之八

128kj

矩阵链乘法最优结合问题
一、《问题的引出》

   看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50

按此顺序计算需要的次数（（A1*A2）*A3）:10X100X5+10X5X50=7500次

按此顺序计算需要的次数（A1*（A2*A3））:10X5X50+10X100X50=75000次

所以问题是：如何确定运算顺序，可以使计算量达到最小化。


二、问题描述
  已知：给定n个矩阵构成的一个矩阵链(A1, A2, ..., An)，矩阵Ai的维数为pi-1×pi

  求：决定该矩阵链的乘法结合顺序（即加括号），使得矩阵链乘法的运行时间最短


三、几个前提概念
   矩阵链乘法的运行时间将以乘法（单行×单列）的次数来衡量
   A是p×q矩阵，B是q×r矩阵，则A×B的运行时间为pqr
   矩阵乘法满足结合律




四、首先判断是否具有最优子结构
    假设Ai...Aj的矩阵链乘法的最优解是在Ak与Ak+1之间分开的，即(Ai...Ak)(Ak+1...Aj)，则子序列也必须是矩阵链乘法的最优解。

由此可知，问题的最优解包含子问题的最优解，满足最优子结构

五、递归表达式
设m[i, j]为矩阵链Ai...Aj的乘法的最短运行时间，m[1, n]即为问题所求的最优解的值
设s[i, j]为运行时间为m[i, j]时的k值，此函数用于递归构造最优解
递归表达式如下



其中矩阵Ai的维数为pi-1 x pi


六、然后进行自底向上的求解

矩阵m是一个上三角矩阵（不需要考虑i>j的情况），且对角线上的元素值均为0

由上面的递归表达式知，m[i, j]的值只取决于m[i, k]和m[k+1, j]（k≥i且k＜j），
因此自底向上的求解过程实际是按子序列的长度递增来进行的


最后构造最优解

在推导过程中记录s[i, j]的值，用于递归构造最优解（即矩阵链的圆括号添加顺序）

import java.util.Scanner; public class MatrixChain {   private int[] p;   private long[][] m;   private int[][] s;    public MatrixChain(int[] p,long[][] m,int[][] s){       this.p=p;       this.m=m;       this.s=s;    }    public long matrixChain() {        int n = p.length - 1;        for (int i = 1; i <= n; i++) {            m = 0;        }         for (int r = 2; r <= n; r++) {            for (int i = 1; i <= n - r + 1; i++) {                int j = i + r - 1;                m[j] = m+m[i + 1][j] + p[i - 1] * p * p[j];                s[j] = i;                for (int k = i + 1; k < j; k++) {                    long t = m[k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];                    if (t < m[j]) {                        m[j] = t;                        s[j] = k;                    }                }           }       }      return m[1][n];    }      public  void printResult(int i,int j)//输出最优加括号方式{         if(i==j)          System.out.print("A"+i);         else{          System.out.print("(");          printResult(i,s[j]);          printResult(s[j]+1,j);          System.out.print(")");         }   }           public static void main(String[] args) {        Scanner in=new Scanner(System.in);        int n=in.nextInt()+1;//矩阵个数        int p[]=new int[n];        for(int i=0;i<n;i++)          p=in.nextInt();//矩阵维数            long m[][] = new long[n][n];        int s[][] = new int[n][n];         MatrixChain mc = new MatrixChain(p,m,s);        System.out.println("最短运行时间="+mc.matrixChain());         for (int i = 1; i < n; i++) {            for (int j = 1; j < n; j++) {                System.out.print(m[j] + "     ");            }           System.out.println();        }        System.out.println();        for (int i = 1; i < n; i++) {            for (int j = 1; j < n; j++) {                System.out.print(s[j]+"  ");            }            System.out.println();        }       System.out.println("最好的结合顺序");       mc.printResult(1,n-1);     }}   

两次运行：
C:\test>java  MatrixChain
4
50 10 40 30 5
最短运行时间=10500
0     20000     27000     10500
0     0     12000     8000
0     0     0     6000
0     0     0     0

0  1  1  1
0  0  2  2
0  0  0  3
0  0  0  0
最好的结合顺序
(A1(A2(A3A4)))


C:\test>java  MatrixChain
6
30 35 15 5 10 20 25
最短运行时间=15125
0     15750     7875     9375     11875     15125
0     0     2625     4375     7125     10500
0     0     0     750     2500     5375
0     0     0     0     1000     3500
0     0     0     0     0     5000
0     0     0     0     0     0

0  1  1  3  3  3
0  0  2  3  3  3
0  0  0  3  3  3
0  0  0  0  4  5
0  0  0  0  0  5
0  0  0  0  0  0
最好的结合顺序
((A1(A2A3))((A4A5)A6))

下载源码：