连乘次数
A是一个p × q矩阵,B是一个q × r矩阵,AB相乘,得到的矩阵元素个数为p × r,每个元素由q次乘法得到,因此所需乘法次数为p × q × r。
问题描述
在计算矩阵连乘积时,加括号的方式对计算量有影响。
例如有三个矩阵A1,A2,Ag连乘,它们的维数分别为
10x100,100×5,5×50。用第一种加括号方式(A1A2)A3计算,则所需数乘次数为10×100×5+ 10×5×50 = 7500。用第二种加括号方式A1(A2A3)计算,需要
100×5×50+10×100 x50=75000次数乘。
Sample Input
6
30 35
35 15
15 5
5 10
10 20
20 25
Sample Output
15125
((A1(A2A3))((A4A5)A6))
解题思路:
先引入以下符号:
- n表示矩阵的个数。
- 表示第i个矩阵。
- A[i: j]表示矩阵连乘
![]()
- 表示 的列数
- 表示 的行数
- k表示矩阵连乘断开的位置为k,表示在 和
之间断开
- m[i,j]表示A[i:j]的最少乘次,m[1, n]即问题的最优解
符号解释:由矩阵相乘的条件可知:前一个矩阵的列数 = 后一个矩阵的行数。因此, 既是 的列数,也是 的行数。结合下面的示意图有助于理解:
该问题有一个关键特征:计算矩阵链A[1:n]的最优计算方式,包含了子矩阵链A[1:k]和A[k+1:n]的最优计算方式。
一般地,如果原问题的最优解,包含了其子问题的最优解,则我们称这种性质为最优子结构性质。若问题具有最优子结构性质,则可用动态规划算法求解。
首先,建立递归关系,写出递归公式:
公式解释:假设k是对矩阵链A[i:j]一分为二得到最优解时的断开位置,则m[i,k]和m[k+1,j]分别是两个子矩阵链A[i,k]和A[k+1,j]的最优解。两个矩阵最后要相乘才能得到A[i,j],因此,最后要加上,也就是两子矩阵相乘的数乘次数,才能得到总的数乘次数。
然后,根据递归公式计算最优解。
在程序中,m的实现是一个二维数组,也就是一张二维表,为了方便计算,m的下标从1开始。要计算A[1:n]的最少乘次,本质上是求m[1][n]的值,也就是二维表表右上角的值。
例如,连乘矩阵个数为6,维数分别为:
A1(30×35),A2(35×15),A3(15×5),A4(5×10),A5(10x20),A6(20×25)
填表方式如下图所示:
原问题现已转化为填表问题,要填充的是矩阵右上三角部分的值。
根据递归公式,对角线的值为0。其他值需要根据于断开位置k的值来得到,k ∈[i,j),我们要遍历所有k,就要访问所求值的所有同一行左边的值和同一列下方的值。因此,在代码中我们可以使用自底向上、从左到右的计算顺序来依次填充,最终得到右上角的值。
伪代码如下:
for i<-1 to n do
dp[i][i] = 0
for length<-2 to n do //length是相乘矩阵链的长度
for begin<-1 to n-length+1 do //begin是相乘矩阵链的第一个矩阵
end = begin + length - 1 //end是相乘矩阵链的最后一个矩阵
dp[begin][end]<-∞
for index <- begin to end-1 do
temp = dp[begin][index] + dp[index+1][end] + p[begin-1]*p[index]*p[end]
if temp < dp[begin][end] then
dp[begin][end] = temp
完整代码
#include<iostream>
using namespace std;
const int N = 100;
int A[N];//矩阵规模
int m[N][N];//最优解
int s[N][N];
void MatrixChain(int n)
{
int r, i, j, k;
for (i = 0; i <= n; i++)//初始化对角线
{
m[i][i] = 0;
}
for (r = 2; r <= n; r++)//r个矩阵连乘
{
for (i = 1; i <= n - r + 1; i++)//r个矩阵的r-1个空隙中依次测试最优点
{
j = i + r - 1;
m[i][j] = m[i][i]+m[i + 1][j] + A[i - 1] * A[i] * A[j];
s[i][j] = i;
for (k = i + 1; k < j; k++)//变换分隔位置,逐一测试
{
int t = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];
if (t < m[i][j])//如果变换后的位置更优,则替换原来的分隔方法。
{
m[i][j] = t;
s[i][j] = k;
}
}
}
}
}
void print(int i, int j)
{
if (i == j)
{
cout << "A[" << i << "]";
return;
}
cout << "(";
print(i, s[i][j]);
print(s[i][j] + 1, j);//递归1到s[1][j]
cout << ")";
}
int main()
{
int n;//n个矩阵
cin >> n;
int i, j;
for (i = 0; i <= n; i++)
{
cin >> A[i];
}
MatrixChain(n);
cout << "最佳添加括号的方式为:";
print(1, n);
cout << "\n最小计算量的值为:" << m[1][n] << endl;
return 0;
}
例题:
对知矩阵规模序列<5,10,3,12,5,50,6>,求矩阵链最优括号化方案
文章来源:https://www.toymoban.com/news/detail-765556.html
思路文章链接:https://www.jianshu.com/p/59f6fac01315
来源:简书文章来源地址https://www.toymoban.com/news/detail-765556.html
到了这里,关于动态规划:矩阵连乘问题(文末附有手写版例题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!