动态规划---矩阵连乘

引言：马上期末考试了，最近在复习计算机算法分析与程序设计；动态规划，这门课程中最难的几个部分之一，上课老师讲时自己懵懵懂懂的以为自己懂了，今天下午复习时。蒙圈了！！！。研究一个晚上，算是稍微开了点窍，遂做如下笔记：
一：问题提出：
给定n个矩阵{A1…..An}；其中A1….Ai+1是可以连乘的，先要求怎么样给这些矩阵加括号改变他们原来的乘积顺序使得最终相乘的次数达到最小：
二：求解
第一种方法：穷举法：
列出所有的可能结果然后一个一个对比：对于n个矩阵设有不同的计算次数P（n）。由于可以先在第k个和第k+1个矩阵之间将原矩阵分为两个矩阵子序列，k=1,2,3,4……n-1;然后然后分别对这两个矩阵完全加括号，最后得到的结果再加括号，得到原矩阵的一种完全加括号的方式。由此我们可以得到关于P（n）的如下递归式：

P(n).png
化简得到P(n)随着n呈现指数增长，所以穷举法不是一个有效的算法，遂提出使用动态规划的思想求解此题：
第二种方法：动态规划：
*第一步：分析其最优子结构：****
设矩阵AiA2…..Aj，就是我们所要求的目标；计做A[i,j];考察计算A[1:n]的最优计算次序；我们将矩阵在Ak和Ak+1出进行分割得到A1…Ak和Ak+1….An的连乘；其中1<=k<n；其相应的完全加括号方式为（（A1….Ak）（Ak+1….An））;；我们先计算A[1:k]和A[k+1:n]然后再将计算结果相乘便可以得到A[1:n];所以总的计算量就是A[1:k]计算量+A[k+1:n]计算量+A[1:k]和A[k+1:n]相乘的计算量。

关键：计算A[1:n的最有次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。（当然是最优的）证明如下：
若有一个计算A[1:k]的次序需要的计算量更少，则用此次序替换原来的A[1:k]的次序，得到的计算A[1:n]的计算量将比最优次序所需要计算量更少，自相矛盾。同理可知，计算A[1:n]的最有次序所包含的计算矩阵子链A[k+1:n]的次序也是最优的。
所以：矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。满足最有子结构性质。

2：建立递归关系：
计算A[i:j]1<=i<=j<=n；所需要的最少乘次数为m[i][j]，则原问题的最优值为
M[1][n]。
当i=j时，A[i:j]=Ai，为单一矩阵不需要计算：所以m[i][i] =0;i=1,2,3…..n。
当i<j时，可以利用最优子结构性质来计算m[i][j]。事实上，若计算A[i:j]最有次序在Ak和Ak+1之间断开时i<=k<j;m[i][j] = m[i][k]+m[k+1][j]+P(i-1)PkPj;由于在计算时我们并不知道k的具体位置k可以去j-i种可能。所以k是这j-i种可能中使得计算量达到最小的那个位置，从而m[i][j]可以递归定义为：

1.png
3:计算最优值
对于1≤i≤j≤n不同的有序对(i,j) 对于不同的子问题，因此不同子问题的个数最多只有o(n*n).但是若采用递归求解的话，许多子问题将被重复求解，所以子问题被重复求解，这也是适合用动态规划法解题的主要特征之一。

用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。
具体代码如下：

package Ceshi;

public class Strassen {
    //Arrays[i][j]表示Ai....Aj连乘最少计算次数；
    private int[][] Arrays;
    //s[i][j] = k;表示矩阵分为Ai...Aj的最优子结构为Ai...Ak和Ak+1...Aj
    private int[][] s;
    //p[i]表示Ai的行数，p[i+1]表示Ai的列数
    private int[] p;
    //提供的默认的构造方法
    public Strassen(){
        //我们在这里并没有构建具体的矩阵，仅仅有一个一维数组来模拟矩阵的行列；四个矩阵就需要5个数字
        //矩阵的分别为：A1[2][4];A2[4][5];A3[5][5];A4[5][3];
        p = new int[]{2,4,5,5,3};
        //用来存储相应个矩阵连乘的最小次数
        Arrays = new int[4][4];
        //存储分割点k;
        s = new int[4][4];
    } 
//你也可以自己去设计矩阵的具体情况
    public Strassen(int n,int p[]){
        this.p = new int[n+1];
        this.Arrays = new int[n][n];
        this.s = new int[4][4];
        for(int i =0;i<p.length;i++){
            this.p[i] = p[i];
        }
    }
    public void martixChain(){
        int n = Arrays.length;
        //当矩阵链的长度为1时：即矩阵个数只有的一个情况
        for(int i =0;i<n;i++){
            Arrays[i][i] = 0;
        }
        //这里的r是用来控制矩阵链的长度与
        for(int r = 2;r<=n;r++){
            //这里的i表示第i个矩阵
            for(int i =0;i<=n-r;i++){
                //j表示第j个矩阵：两者合起来的意思就是：A[i:j]从矩阵连乘Ai....Aj；
                int j = i+r-1;
                //这里原本等于Arrays[i][i]+Arrays[i+1][j]+p[i]p[i+1]*p[j+1]
                //p[i]表示第i个矩阵的行数，p[i+1]表示第i个矩阵的列数，p[j+1]表示第j个矩阵的列数
                Arrays[i][j] = Arrays[i+1][j]+p[i]*p[i+1]*p[j+1];
                //表示连乘的分割点是i；即将连乘的矩阵分为第一个矩阵自成一队，后面剩余的的矩阵成一队；
                s[i][j] = i;
                //循环选出连乘数目最小的情况：例如：当n=6，r=3：i=0时
                //A1*A2*A3:这三个矩阵连乘情况可以为：(A1*A2)*A3或者A1*(A2*A3)选出乘积次数最小的情况
                for(int k =i+1;k<j;k++){
                    int temp = Arrays[i][k]+Arrays[k+1][j]+p[i]*p[k+1]*p[j];
                    if(temp<Arrays[i][j]){
                        Arrays[i][j] = temp;
                        s[i][j] = k;
                    }
                }
            }
            
        }
    }
    public void traceBack(int a,int b){  
        if(a<b){  
            traceBack(a, s[a][b]);  
            traceBack(s[a][b]+1, b);  
            System.out.println("先把A"+a+"到A"+s[a][b]+"括起来，在把A"+(s[a][b]+1)+"到A"+b+"括起来，然后把A"+a+"到A"+b+"括起来");  
        }  
    } 
      public void printM(){
          int length = Arrays.length;
            for (int i=0;i<length;i++){
                for (int j=0;j<length;j++){
                    System.out.print(Arrays[i][j]+ "   ");
                }
                System.out.println();
            }
        }
    //测试
    public static void main(String[] args) {
        Strassen stra = new Strassen();
        stra.martixChain();
        stra.traceBack(0, 3);
        stra.printM();
    }
}

下图摘自：陈斌彬的技术博客
图示主要是为了展示具体的求解过程，使用了6个矩阵连乘，方便大家理解

计算过程图.jpg
第三种解法：备忘录法：
备忘录方法就是动态规划算法的变形。和动态规划算法一样，备忘录方法也会使用表格保存已经解决子问题的答案，在需要时，只需要简单的查看；和动态规划不同的是，备忘录的递归算法是第定向下的，而动态规划算法则是自底向上递归的，因此备忘录的控制结构和直接递归方法的控制结构是一样的，却别在于备忘录方法为每一个已经解决的子问题建立了备忘录以备需要时查看，避免相同的子问题重复求解；

/**
*备忘录法求解矩阵连乘问题 * 这个方法是初始化存储矩阵相乘次数的数
*备忘录法求解矩阵连乘问题
*/ 
//这个方法是初始化存储矩阵相乘次数的数组
public int MemoizedMatrixChain(int n){
          for(int i =0;i<n;i++){
              for(int j =i;j<n;j++){
                 Arrays[i][j] = 0; 
              }
          }
          return LookUpChain(0,n-1);
      }
      public int LookUpChain(int i,int j){
          //如果相应位置的相乘次数已经计算出来了，直接返回计算次数；
          if(Arrays[i][j]>0){
              return Arrays[i][j];
          }
          //表示只有一个矩阵时的情况
          if(i==j){
              return 0;
          }
          //矩阵连乘A[i:j]分割成A[i:i]和A[i+1：j]两个矩阵的全括号方式；
          int temp = LookUpChain(i,i)+LookUpChain(i+1,j)+p[i]*p[i+1]*p[j+1];
          //记录当前的分割点
          s[i][j] = i;
          //
          for(int k =i+1;k<j;k++){
                int t = LookUpChain(i,k)+LookUpChain(k+1,j)+p[i]*p[k+1]*p[j];
                if(t<temp){
                    temp = t;
                    s[i][j] = k;
                }
          }
          Arrays[i][j] = temp;
          return temp;
      }