算法分析与设计——矩阵链乘（动态规划）

矩阵链乘问题

对于给定的n个矩阵，M1， M2 ，…， Mn，其中矩阵Mi 和Mj 是可乘的，要求确定计算矩阵连乘积 （ M1M2 …Mn ）的计算次序，使得按照该次数计算 矩阵连乘积时需要的乘法次数最少

1、描述最优解结构

目标：
求出矩阵链乘Mi Mi+1 ┅Mj-1 Mj（i<j） 所需的最少乘法次数
分析：
共有j-i+1个矩阵，按照做最后一次乘法的位置进行划分，矩阵链乘一共可分为j-i种情况
最优解可表示为：
(Mi ┅ Mk) (Mk+1 ┅ Mj)（i≤k<j）

2、递归地定义最优值（写出动态规划方程）

记第t个矩阵Mt的列数为rt
令r0为矩阵 M1的行数 ，则第t个矩阵的行数为rt-1
故Mi ┅ Mk连乘所得是ri-1rk维矩阵 ，Mk+1 ┅ Mj连乘所得是rkrj维矩阵
两这两个矩阵相乘做ri-1rkrj次乘法

记(Mi ┅ Mk)和(Mk+1 ┅ Mj)的最少乘法次数，记为m[i][k]和m[k+1][j]
故(Mi … Mk)(Mk+1 … Mj)的最少乘法次数为m[i][k]+m[k+1][j]+ri-1rkrj
将满足i≤k<j 的共j-i种情况逐一进行比较，
可知m[i][j]=min{m[i][k]+m[k+1][j]+ri-1rkrj}
而当i=j时，矩阵链中只包含一个矩阵，故m[i][j]=0

3、以自底向上的递推方式计算出最优值 

算法：
MATRIX-CHAIN

for i=1 to n
     do m[i][i]=0
 for l=1 to n-1  //l为链表的长度，即链乘矩阵的个数
      do for i=1 to n-l+1
             do j=i+l-1
              for k=i to j-1
                   m[i][j]=min{m[i][k]+m[k+1][j]+ri-1*rk*rj}

可知，算法复杂度为Θ(n^3)

4、根据计算最优值时得到的信息，以递归方法构造一个最优解

MATRIX-CHAIN算法可说明计算矩阵乘积时的最少次数，但并不能直接说明如何对这些矩阵进行相乘。
通过一个二维数组表来记录对Mi ┅ Mj进行划分的k值
故d[i,j]=k 表示Mi ┅ Mj的划分情况是(Mi … Mk)(Mk+1 … Mj)
利用递归思想，划分子结构即可

算法：
PRINT-CHAIN(i,j,d[i][j])

if i=j
   then print "Mi"
   else print "("
           PRINT-CHAIN(i,d,d[d,i])
           PRINT-CHAIN(d,j,d[d,j])
           print ")"

具体题目：

给定6个矩阵 A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ；确定这6个矩阵的乘法次序，使得乘次最小。

最后的结果为：((A1(A2A3))((A4A5)A6)) 最小的乘次为15125。

java代码：

//无成员数据，仅有方法组成的MatrixMutiply类
public class MatrixMutiply{

    //成员函数MatrixChain()：得出乘法最少次数，即最优值
    //m[][]是存放最优值，M[i:j]链乘最少次数 m[i][j]
    //r[]存放矩阵的维数，r[i]表示Mi的行数，r[i+1]表示Mi的列数
    //d[][]存放分割位置k
    public static void MatrixChain(int m[][],int r[],int d[][]){

        int n=m.length-1;

        for(int i=1;i<=n;i++){
            m[i][i]=0;
        }

        //l为链长，即链乘矩阵的个数
        for(int l=2;l<=n;l++){
            for (int i=1;i<=n-l+1;i++){
                int j=i+l-1;
                m[i][j]=999999;
                //k为分割点
                for(int k=i;k<j;k++){
                    int temp=m[i][k]+m[k+1][j]+r[i-1]*r[k]*r[j];
                    if(m[i][j]>temp){
                        m[i][j]=temp;
                        d[i][j]=k;
                    }
                }
            }
        }
        System.out.print(m[1][n]);
    }


    //成员函数PrintChain()：输出乘法次数最少时的乘法情况，即最优解
    //利用递归思想
   public static void PrintChain(int i,int j,int d[][]){
        if(i==j){
            System.out.print("M"+i);
        }
        else{
            System.out.print("(");
            PrintChain(i,d[i][j],d);
            PrintChain(d[i][j]+1,j,d);
            System.out.print(")");
        }
    }

    //静态函数不可直接调用非静态函数
    public static  void  main(String[]agrs){
        int array[][]=new int[7][7];
        int p[]=new int[]{30,35,15,5,10,20,25};
        int a[][]=new int[7][7];
        MatrixChain(array,p,a);
        System.out.println();
        PrintChain(1,6,a);
    }
}