动态规划矩阵连乘求最优值和最优解
- 问题描述
矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。给定n个矩阵:A1,A2,...,An,其中Ai与Ai+1是可乘的,i=1,2...,n-1。确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。比如A1(10*100),A2(100*5),A3(5*50)三个矩阵,相乘次序分别为((A1*A2)A3)和(A1(A2*A3))时,矩阵相乘的次数分别为7500(10*100*5+10*5*50)和75000(100*5*50+100*50*10),所以我们需要找到相乘次数最少的矩阵相乘次数(最优值)和矩阵相乘次序(最优解)。
- 基本思路
递归公式
m[i][j]=m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
这里的i是第一个相乘矩阵的序列数,j是最后一个所乘的矩阵序列数,其中k是最后一次相乘时序列数i到j中间的任意一个断点数。
m[i][j]存放的是从第i个矩阵到第j个矩阵的矩阵连乘的计算次数
实例:
例:现在有六个矩阵相乘,分别是A1、A2、A3、A4、A5、A6,矩阵的行数和列数分别是A1(30,35)、A2(35,15)、A3(15,5)、A4(5,10)、A5(10,20)、A6(20,25),则六个矩阵相乘经过计算解得最优值为:15125,且最优解为:(A1*(A2*A3))*((A4*A5)*A6)
笔算过程如下:
过程是分层运算的,只有1个矩阵时、有2个矩阵时、有三个矩阵时、、、
全部代码如下:
#include<iostream>
using namespace std;
int p[100];
int m[100][100], s[100][100];
int n;
//寻找最优值和断点位置
void matrixchain()
{
int i, r, j, k;
//初始化数组
for (i = 0; i < 100; i++)
{
for (j = 0; j < 100; j++)
{
m[i][j] = 0;
s[i][j] = 0;
}
}
for (r = 2; r <= n; r++)//矩阵连乘的规模为r,此时计算的矩阵连乘的个数是r个且是顺序连续并所有的。从2开始,因为只有一个矩阵相乘的次数为0。
{
for (i = 1; i <= n - r + 1; i++)//第一个矩阵的下标范围
{
j = i + r - 1;//最后一个矩阵的下标范围
m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];//因为m[i][i]为0,先对m[i][j]赋一个在该位置(第一个断点位置)相连乘的值
s[i][j] = i;//s[][]存储各子问题的决策点,前面m里面存的是在第一个断点位置的值,所以这里存1
for (k = i + 1; k < j; k++)//寻找在最优位置断点的最优值
{
int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (t < m[i][j])
{
m[i][j] = t;//将最优值赋给m
s[i][j] = k;//记录断点位置
}
}
}
}
}
//寻找最优解
void print(int i, int j)
{
if (i == j)
{
cout << "A[" << i << "]";
return;
}
cout << "(";
print(i, s[i][j]);
cout << "*";
print(s[i][j] + 1, j);
cout << ")";
}
int main()
{
cout << "请输入矩阵的个数n : " << endl;
cin >> n;
int i, j;
cout << "请依次输入每个矩阵的行数和最后一个矩阵的列数:" << endl;
for (i = 0; i <= n; i++)
cin >> p[i];//将第一个矩阵的列和第二个矩阵的行的下标置为相同的了
matrixchain();
cout << "最优值为:" << m[1][n] << endl;
cout << "最优解计算方法为:";
print(1, n);
cout << endl;
return 0;
}
结果如图:
2301_81787030: i<=n和i<=n-r+1都能成功运行呢
@碧血但马马: 可以的 懂了![表情包](https://g.csdnimg.cn/static/face/emoji/008.png)