矩阵链乘法

如果给出了矩阵链,则必须找到要相乘的正确矩阵序列的最小数目。

我们知道矩阵乘法是关联的,因此四个矩阵ABCD可以在这些序列中乘以A(BCD),(AB)(CD),(ABC)D,A(BC)D。像这些序列一样,我们的任务是找到可以有效相乘的顺序。

在给定的输入中,有一个数组说arr,其中包含arr [] = {1,2,3,4}。这意味着矩阵的数量级为(1 x 2),(2 x 3),(3 x 4)。

输入输出

Input:

输入矩阵的阶数. {1, 2, 3, 4}. 这意味着矩阵是

{(1 x 2), (2 x 3), (3 x 4)}.

Output:

最少的运算次数需要将这三个矩阵相乘。这里的结果是18。

算法

matOrder(array, n)

输入-矩数组表,列表中的矩阵数。

输出-矩阵乘法的最小数量。

Begin

   定义大小为 n x n 的表 minMul,最初填充所有0

   for length := 2 to n, do

      fir i:=1 to n-length, do

         j := i + length – 1

         minMul[i, j] := ∞

         for k := i to j-1, do

            q := minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j]

            if q < minMul[i, j], then minMul[i, j] := q

         done

      done

   done

   return minMul[1, n-1]

End

示例

#include<iostream>

using namespace std;

int matOrder(int array[], int n) {

   int minMul[n][n];          //存放所需标量乘法的数量

   for (int i=1; i<n; i++)

      minMul[i][i] = 0;        

   for (int length=2; length<n; length++) {        //从2开始计算链的长度

      for (int i=1; i<n-length+1; i++) {

         int j = i+length-1;

         minMul[i][j] = INT_MAX;     //设为无穷大

         for (int k=i; k<=j-1; k++) {

            //每次存储的存储成本

            int q = minMul[i][k] + minMul[k+1][j] + array[i- 1]*array[k]*array[j];

            if (q < minMul[i][j])

               minMul[i][j] = q;

         }

      }

   }

   return minMul[1][n-1];

}

int main() {

   int arr[] = {1, 2, 3, 4};

   int size = 4;

   cout << "最小矩阵乘法数: " << matOrder(arr, size);

}

输出结果

最小矩阵乘法数: 18

以上是 矩阵链乘法 的全部内容, 来源链接: utcz.com/z/334645.html

回到顶部