矩阵连乘_动态规划

问题描述

　　》给定n个矩阵{A1，A2，...，An}，其中Ai与Ai+1是可乘的(即Ai的列数与Ai+1的行数相等)

　　》如何确定矩阵连乘积的计算次序，使得总计算次数最少

　　》用加括号方法表示矩阵连乘次序，不同加括号方法对应的计算次序是不同的

例：

　　三个矩阵A1A2A3连乘共有两种加括号的方式：(A1A2 )A3和A1 (A2A3 )

　　四个矩阵A1A2A3A4连乘共有五种加括号的方式：(A1 (A2 (A3A4 )))、 ((A1A2 )(A3A4 ))、((A1 (A2A3 ))A4 )、 (A1 ((A2A3 )A4 ))及(((A1A2 )A3 )A4 )。

　　设四个矩阵A, B, C和D，维数分别为A=50 × 10，B=10 × 40，C=40 ×30，D=30 × 5。

　　　　总共有五种完全加括号的方式：

　　　　　　(A((BC)D))：10*40*30 + 10*30*5 + 50*10*5 = 16000

　　　　　　(A(B(CD)))：40*30*5 + 10*40*5+50*10*5 = 10500

　　　　　　((AB)(CD))：50*10*40 + 40*30*5 + 50*40*5 = 36000

　　　　　　(((AB)C)D)：50*10*40 + 50*40*30 + 50*30*5 = 87500

　　　　　　((A(BC))D)：10*40*30 + 50*10*30 + 50*30*5 = 34500

采用穷举法

采用动态规划

第一步分析最优解的结构

　　◼将AiAi+1…Aj记作A[i：j]，假设求解A[1：n]最优计算次序在Ak和Ak+1之间断开, k∈[1,n]. 则

　　◼完全加括号方式为((A1…Ak )(Ak+1…An ))

　　◼ 总计算量=A[1:k]的计算量 + A[k+1:n]的计算量 + A[k]的结果矩阵乘以A[k+1]的结果矩阵的计算量

　　◼最优序列的子序列划分也是最优的。假如(A1...Ak)不是最优子序列，则将比它更好的子序列与(Ak+1...An)合并后，原序列不是最优，与已知矛盾

　　◼问题的最优子结构性质是该问题可用动态规划算法求解的显著特征

矩阵连乘算法数据结构

　　形参中应有矩阵个数n和存储矩阵行数的一维数组p[n]。因为要使矩阵可乘，Ai的列数必须与Ai+1的行数一致，所以只需用p[0]存储A1的行数，其他矩阵只存储列数即可

　　算法需要两个二维数组：

　　　　用A[i, j]表示A[i: j]的总计算量，二维数组m[n][n]存储A[i, j]的最小值，即最小数乘次数

　　　　二维矩阵s[n][n]，每个元素s[i][j]为A[i: j]的断点位置

第二步建立递归关系

　　令m[i][j]为A[i: j]的最小数乘次数，则m[1][n]则为A[i: j]的解

　　令i= j，则m[i][j]为单矩阵的数乘次数，为0

　　当i< j，利用最优子结构性质有：

　　　　m[i, j] = 　　　　　　0　　　　　　　　　　　　　　　i = j

　　　　　　　　min(i<= k < j){m[i, k] + m[k+1, j] + Pi-1PkPj}　　i < j

　　　　k的位置只有j-i种可能

递推算法

　　MatrixChain(形参表)

　　{

　　初始化；//初始化是将m[i][i]，即对角线元素，赋值为0

　　自底向上地计算每一个m[i][j]并将结果填入表中；//底是m[i][i]，即对角线元素。最顶层是m[1][n]

　　}

package 动态规划;

import java.util.Scanner;

public class 矩阵连乘 {
    static void matrixChain(int n,int p[],int m[][],int s[][])//递推
    {
       for(int i=1;i<=n;i++){//对角线先为0
        m[i][i]=0;
       }
       for(int r=2;r<=n;r++){//一共n-1个对角线
        for(int i=1;i<=n-r+1;i++){//第i行
            int j=i+r-1;//在该行的对角线上的点对应的j值，这个j控制的是矩阵链的结束位置，即A[i: j]中的j
            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//初始化此时在i处取得最优解，因为m[i][i]为0，所以此处没写
            s[i][j]=i;
            for(int k=i+1;k<j;k++){//如果有更小的则被替换，由于计算时并不知道k的位置，所以k未定，但只有j-i种可能，即k属于{i，i+1，...，j-1 }
                int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(t<m[i][j])
                {
                    m[i][j]=t;
                    s[i][j]=k;
                }
            }
        }
       }
    }
    
    static void print_optimal_parents(int s[][],int i,int j)//打印划分的结果
     {
         if( i == j)
             System.out.print("A"+i);
         else
         {
             System.out.print("(");
             print_optimal_parents(s,i,s[i][j]);
             print_optimal_parents(s,s[i][j]+1,j);
             System.out.print(")");
         }

     }
    
    public static void main(String argc[])
    {
        int p[] = new int[1000];//每个矩阵的行数和最后一个的列数
        int m[][] = new int[100][100];//存储最优子结构
        int s[][] = new int[100][100];//存储当前结构的最优断点
        System.out.println("请输入矩阵的个数");
        int n;
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        System.out.println("请依次输入每个矩阵的行数和最后一个矩阵的列数");
        for(int i=0;i<=n;i++){
            p[i] = in.nextInt();
        }
        matrixChain(n,p,m,s);
        System.out.println("这些矩阵相乘的最少次数是"+m[1][n]);

        System.out.println("结果是:");
         print_optimal_parents(s,1,n);
    }
}

运行结果：