矩阵连乘

问题定义

• 输入：给定n个矩阵，矩阵间连乘

  a₁ ... a_n : a_i 与 a_{i + 1} 可乘

  令a₁：p₀ * p₁

    ...
  

  a_n：p_n-1 * p_n

  则：输入用一维数组表示，P:{p₀p₁p₂...p_n}

• 输出：求最少乘法次数的计算方法

  • 特征：无论在哪里断开，分开部分的矩阵作为一个整体不影响整个矩阵的连乘

  • 对于矩阵序列，不同的乘次序将导致不同的乘法次数

  • 例如：a₁ * a₂ * a₃的乘法次数

    (a₁ * a₂) * a₃ ：(p₀ * p₁ * p₂) + (p₀ * p₂ * p₃)

    a₁ * (a₂ * a₃)：(p₁ * p₂ * p₃) + (p₀ * p₁ * p₃)

  • 找出最优计算次序以使得矩阵连乘所需要的计算次数最少

蛮力法

枚举每一种划分括号的情况，计算出他们的乘法次数，取最小的划分情况

A1A2A3...An：添加括号，直到只有一个矩阵可以加括号，然后计算他们的连乘次数

A1(A2(A3...An))的连乘次数：p2 * ... * pn + p1 * p3 * pn + p0 * p1 * pn

递归分治

优化暴力枚举（用k表示分割的位置）

每次调用递归式时：传入分割后的矩阵列

递归出口：当传入的矩阵列中只有一个矩阵，返回0

回溯处理：计算两边分割乘法次数的和，计算两边合并的乘法次数再相加，取某个分割位置k时的最小值

• 优点：存在子问题最优解
• 缺点：存在重复计算部分
  • 为什么
    1. 递归使用帧无法保存太多的信息
    2. 子问题重叠，因为不同的部分划分可能由相同的子问题组成，那么递归调用中出现重复计算的子问题是随着递归深度变化的

动态规划法

• 使用空间换时间，将子问题记录下来

  • 那么就将递归分治的缺点改为优点，这下子，解决方法就是利用了动态规划的思想

• 令 m(i,j) ：为i，j之间的矩阵列的最小乘法次数，在这之间使用k作为划分的位置

  • 

  • 根据上述定义，二维表m的对角线上都是0，m(1,n)是我们需要的最少乘法次数

• 令s(i,j)：为i，j之间矩阵列的最优分割位置

• 时间复杂度：

  • for(1 to n)：枚举序列长度

    • for(0 to r)：枚举矩阵子列的起点

      • j = r

        for(k = i + 1 to j)：枚举矩阵子序列分割点

        s表记录最优的分割位置、m表最少乘法次数
        

  • 线性时间读s表，构造最优矩阵连乘的计算步骤

import java.util.Arrays;

public class MatrixChainTest {

    /**
     * @param p：矩阵维数序列，其长度减一为连乘矩阵的个数
     * @param memory：ai*...*aj的最小数乘次数
     * @param s：最佳括号断开位置
     * 操作数组时，从下标开始
     */
    public static void matrixChain(int[] p, int[][] memory, int[][] s) {
        int n = p.length - 1;//矩阵个数
        //初始状态对角线置为0
        for(int i = 0; i < memory.length; i++) {
            memory[i][i] = 0;
        }
        //矩阵长度从二(下标0，1)开始，计算不同子矩阵的数乘次数
        for(int r = 1; r < n; r++) {//r+1：矩阵列长度
            for(int i = 0; i < n - r; i++) {//从第一个矩阵开始，枚举r+1长度的矩阵列（的起点）
                int j = i + r;//矩阵列：A_(i+1)*...*A_(j+1)
                //矩阵列长度：j - i + 1
                //断开位置(矩阵列的第几个(从1开始算)位置)与下标关系：x_断 = x_(下+1)
                //设最先断开的位置是A_(i+1)
                memory[i][j] = memory[i][i] + memory[i+1][j] + p[i] * p[i + 1] * p[j + 1];
                s[i][j] = i + 1;
                //枚举断开位置，在矩阵列：A_(i+1)*...*A_(j+1)的从 i+2 到 j+1
                for(int k = i + 1; k < j; k++) {//断开位置从 k + 1开始
                    int temp = memory[i][k] + memory[k+1][j] + p[i] * p[k + 1] * p[j + 1];
                    if(temp < memory[i][j]) {
                        memory[i][j] = temp;
                        s[i][j] = k + 1;
                    }
                }
            }
        }
        System.out.println("矩阵连乘的最少乘法次数为" + memory[0][n - 1]);
    }

    /**
     * 利用矩阵序列最优的分割位置s，构造最优计算次序
     * @param s：最优分割位置
     * @return：矩阵序列p的最优计算次序
     */
    private static String matrixChainMake(int[][] s) {
        int n = s.length;
        String[] temp = new String[n];
        //矩阵序列初始化
        for(int i = 0; i < n; i++) {
            temp[i] = "A" + i;
        }
        //加括号
        for(int i = 0; i < n - 2; i++) {
            int k = s[i][n - 1];//获得分割的位置
            if(k - i > 1) {//括号包住两个以上的矩阵列
                temp[i] = "(" + temp[i];
                temp[k - 1] += ")";
            }
            if(n - k > 1) {
                temp[k] = "(" + temp[k];
                temp[n - 1] += ")";
            }
        }
        //最后答案处理
        StringBuilder rs = new StringBuilder();
        for(int i = 0; i < temp.length; i++) {
            rs.append(temp[i]);
        }
        System.out.println("最优计算次序为：" + rs.toString());
        return rs.toString();
    }

    /**
     *外部调用入口
     * @param p：矩阵列的维数
     * @return 返回矩阵连乘的最优计算次序
     */
    public static String matrixChain(int[] p) {
        int[][] m = new int[p.length - 1][p.length - 1];
        int[][] s = new int[p.length - 1][p.length - 1];
        MatrixChainTest.matrixChain(p, m, s);
        System.out.println("m：");
        array2dShow(m);
        System.out.println("s：");
        array2dShow(s);
        return matrixChainMake(s);
    }

    public static void main(String[] args) {
        int[] p = {30, 35, 15, 5, 10, 20, 25};
        matrixChain(p);
    }

    private static void array2dShow(int[][] s) {
        for(int i = 0; i <s.length; i++) {
            System.out.println(Arrays.toString(s[i]));
        }
    }

}

相关链接：

• 09_动态规划之矩阵连乘算法设计与分析哔哩哔哩_bilibili：推荐的讲解视频，前面的引入和后面的思维发散都很有趣，引人深思
• 矩阵连乘：和视频的讲解思路一致
• 动态规划之——矩阵连乘（全网最详细博文，看这一篇就够了！）：很详细，很尽心的博文（没代码纯思路，和视频讲解一样

学习别人的思想，总结自己的想法：

• 分析一个问题的解决方法，很容易想到暴力，然后再想着优化，发现问题可以被分割成独立的子问题，例如这题就朝分治递归去了；再分析递归分治的过程，发现存在重复计算的子问题，那么出现了动态规划问题的特性：最优子结构、子问题重叠
• 一步步的分析才能得到结果，不是观测就来的

动态规划基本步骤：
1.找出最优解的性质，并刻划其结构特征。
2.递归地定义最优值。
3.以自底向上的方式计算出最优值。
4.根据计算最优值时得到的信息，构造最优解。