矩阵连乘（动态规划）

系统管理员 2022-06-05 07:51 213阅读 0赞

题目描述：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。例如：

A1=\{30x35\} ; A2=\{35x15\} ;A3=\{15x5\} ;A4=\{5x10\} ;A5=\{10x20\} ;A6=\{20x25\} ;

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

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

![这里写图片描述][SouthEast]

public class Test { 
        private static final int  count = 6;
        /** * 存储的是i+1到j+1的最小乘次，因为是从0开始 */
        static int[][] min_part = new int[count][count];
    
        /** * 计算矩阵最小乘次数 * @param p 保存矩阵行列的数组 * @param n 矩阵的个数 * @param min_part 保存最小乘次数 * @return */
        public static int function(int[] p, int n, int[][]min_part) {
            int j = 0;
    
            for (int i = 0; i < n; i++) {
                min_part[i][i] = 0;
            }
    
            //r为连乘矩阵的个数
            for (int r = 2; r <= n; r++) {
                //i表示连乘矩阵的第一个,从连乘矩阵个数为2开始计算 需要算n-r个
                for (int i = 0; i <= n - r; i++) {
                    //j表示连乘矩阵中的最后一个
                    j = i + r - 1;
                    min_part[i][j] = Integer.MAX_VALUE;
    
                    for (int k = i; k <= j-1; k++) {
                        //在第一个与最后一个之间寻找最合适的断开点
                        int tmp = min_part[i][k] + min_part[k+1][j] + p[i]*p[k+1]*p[j+1];
    
                        if (tmp < min_part[i][j]) {
                            min_part[i][j] = tmp;
                        }
                    }
                }
            }
            return min_part[0][n-1];
        }
    
        public static void main(String[] args) {
            int[] p = new int[count+1];
            p[0] = 30;
            p[1] = 35;
            p[2] = 15;
            p[3] = 5;
            p[4] = 10;
            p[5] = 20;
            p[6] = 25;
    
            int ans = function(p,count,min_part);
            System.out.println(ans);
        }
    }

从2个矩阵开始计算: m\[0\]\[1\] m\[1\]\[2\] m\[2\]\[3\] m\[3\]\[4\] m\[4\]\[5\] //m\[0\]\[1\]表示第一个矩阵与第二个矩阵的最小乘次数、

以此类推 3个矩阵计算m\[0\]\[2\] m\[1\]\[3\] m\[2\]\[4\] m\[3\]\[5\]  
。。。  
一直到6个矩阵计算 m\[0\]\[5\]即为结果

每次计算均取到上一矩阵计算保存的结果

[SouthEast]: /images/20220605/82ffbe532b11489c8ed33cf9f089e6e6.png