欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法导论之使用动态规划法求解矩阵连乘最小乘法次数

程序员文章站 2022-07-03 14:43:36
...

最近看到使用动态规划法求解矩阵连乘最小乘法次数,网上的一些copy主,只是copy,也不改错。本文已将一些不正确的错误更改。

问题描述:

给定n个矩阵:A1,A2,…,An,其中Ai与Ai+1是可乘的,i=1,2…,n-1。确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数。

问题解析:

由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。
  
完全加括号的矩阵连乘积可递归地定义为:

 单个矩阵是完全加括号的;

 矩阵连乘积A是完全加括号的,则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号,即A=(BC)

例如,矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式:(A1(A2(A3A4))),(A1((A2A3)A4)),((A1A2)(A3A4)),((A1(A2A3))A4),(((A1A2)A3)A4)。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序,这决定着作乘积所需要的计算量。

看下面一个例子,计算三个矩阵连乘{A1,A2,A3};维数分别为10X100 , 100X5 , 5X50 按此顺序计算需要的次((A1A2)A3):10X100X5+10X5X50=7500次,按此顺序计算需要的次数(A1(A2A3)):100X5X50+10X100X50=75000次

所以问题是:如何确定运算顺序,可以使计算量达到最小化。

如果你还不明白是什么意思,在看下面这个例子:给定一个 n 的矩阵序列,我们希望计算它们的乘积:

A1·A2·A3····An
其中,Ai 是 算法导论之使用动态规划法求解矩阵连乘最小乘法次数 矩阵(i行,i+1列)

注意,这里不是要计算乘积,而是希望找到一个明确的计算次序,使得这个矩阵连乘的乘法次数最少,并求这个最小的乘法次数(m(1, n),这个值表示第 1 个到第 n 个矩阵相乘的最小乘法次数)。下面举举几个例子:

当 n=1 时,m(1,1) = 0;
当 n=2 时,m(1,2) = a1 * a2 * a3;
当 n=3 时,有两种情况:

   ((A1 · A2) · A3),这乘法次数为:a1*a2*a3 + a1*a3*a4;
   (A1 · (A2 · A3)),这乘法次数为:a2*a3*a4 + a1*a2*a4;

而,m(1,3) = min {a1*a2*a3 + a1*a3*a4,a2*a3*a4 + a1*a2*a4}
这里我解释下,肯定很多人有点懵,这里的A1你可以认为代表的是一个a1*a2的矩阵,A2是a2*a3的矩阵,A3是a3*a4的矩阵。

简单来说,这道题的目的,就是在计算矩阵连乘时,求出一种方案,使得计算所需的乘法次数最小,输出的结果是这个最小的乘法次数。

动态规划求解

用动态规划算法解此问题时,可依据其递归式以自底向上的方式进行计算。在计算过程中,保存以解决的子问题的答案,每个子问题只计算一次,而在后面用到时只需要简单查一下,避免了大量的重复计算,最后得到了多项式时间的算法。
主要计算公式如下:
算法导论之使用动态规划法求解矩阵连乘最小乘法次数
先求m(i,k)和m(k+1,j)的最小乘法次数,最后在求求m(i,k)和m(k+1,j)所对应的矩阵的乘法次数

动态规划问题,有一个非常明显的特点就是重叠子问题,上面的解法之所以时间复杂度那么高,一个重要的原因就是在使用递归方法时,有很多重复的计算,比如对于 m(1,2) 这个值,其实 m(1,3), m(1,4), m(1,5)… 都会用到,如何防止重复计算将是这个问题优化的一个重点,容易想到的方法就是使用空间换时间,在计算的过程中,额外申请一个二维数组(n*n)保存 m(i,j) 这个值,避免重复计算。

这个二维数据,也类似一个表格,下面的问题就是怎么填充这个表格(这个解法在算法导论上叫做自底向上的表格填充法)

这里,我们举个例子,有一个表格如下,首先,我们有:

m(i,j)=0,(i=j)

所以表格对角线上的值均为0,因为是要求 i < j的,所以这个表格对角线下面的空格的值是不需要去填充的。

假设这里,我们要去求 m(1,6)(图中红色的空格),根据 算法导论之使用动态规划法求解矩阵连乘最小乘法次数 这个公式,其实是需要下面几个空格的值(图中黄色空格的数值):

m(1,1), m(2,6);
m(1,2), m(3,6);
m(1,3), m(4,6);
m(1,4), m(5,6);
m(1,5), m(6,6);

这里是有一个规律的,那就是上面的值均在红线以下。而且最开始的对角线的值是有的,所以将对角线依次往右上方平移去计算,这样的话,在求 m(i,j) 时,其所需要的值都是已知的。
算法导论之使用动态规划法求解矩阵连乘最小乘法次数 右上角的深红色的点,就是我们要求解的最优解。

这部分的代码实现如下:

// a[0] 不使用,使用的是,1到 n+1
public int countMatricsChain(int[] a, int n) {
    int[][] m = new int[n + 1][n + 1];
    for (int i = 1; i <= n; i++) {
        m[i][i] = 0;
    }
    for (int l = 2; l <= n; l++) {
        for (int i = 1; i < n - l + 1; i++) {
            int j = i + l - 1;
            m[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int q = m[i][k] + m[k + 1][j] + a[i] * a[k + 1] * a[j + 1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                }
            }
        }
    }
    return m[1][n];
}