#矩阵相乘#
测试一 15个矩阵连乘问题。矩阵行列数目信息顺次为：
(10,45,35,80,25,60,70,15,100,40,50,30,75,20,65,10)
测试结果：
最少相乘次数：M[1][15] = 1.27575e+06
最优解(((((((A1A2)A3)A4)A5)A6)A7)(A8(A9(A10(A11(A12(A13(A14A15))))))))
测试二 7个矩阵连乘问题。矩阵行列数目信息顺次为：
(300,4500,150,60,6000,200,70,300)
测试结果：
最少相乘次数M[1][7] = 2.01e+08
最优解((A1(A2A3))(((A4A5)A6)A7))
以上测试一、测试二的算法耗时，是指真实矩阵相乘的耗时。可用相应规模的零矩阵实施连乘。
说明：
（1）编程语言：C
（2）编译平台：VS2019
（3）计算机配置：32/64
注意点：当相乘矩阵维数较大时，应选择相应较大的数据类型来存储数据。否则将导致数据溢出，进而导致最终得到的最优值和最优解是错误的；另外在64位系统下，运行同一个程序，所用时间明显少于在32位系统下运行所需时间
int N = -1;
void main()
{
while (N < 0)
{
cout << "请输入待相乘矩阵个数N：";
cin >> N;
if (N > 0)
break;
else
{
cout << "输入数值无效，请重新输入（N>0）：\n";
}
}
if (N == 1)
{
cout << "最优解为矩阵自身！\n";
system("pause");
return;
}
else
{
int* P = new int[N + 1];
cout << "请依次输入第一个矩阵的行数及各个矩阵的列数，共" << N + 1 << "个值：\n";
for (int i = 0; i <= N; i++)
{
cin >> P[i];
}
{
int T_start, T_end, time;
T_start = TimeSpend();
CommonMultiply(P, 1, N);//常规（顺序）方法矩阵相乘
T_end = TimeSpend();
time = T_end - T_start;
cout << "————常规（顺序）方法矩阵相乘耗时：" << time << "毫秒\n\n";
}
{
Big** M = CreateZeros(N + 1, N + 1);//N+1行
int** S = (int**)CreateZeros(N + 1, N + 1);
//MatrixChain(P, N, M, S);
RecurMatrixChain(P,1, N, M, S);
//cout << "最优断开位置：\n";
//for (int i = 1; i <= N; i++)//输出最优断开数组
//{
// for (int j = i + 1; j <= N; j++)
// {
// cout << "S[" << i << "][" << j << "] = " << S[i][j] << "\t";
// }
// cout << "\n\n";
//}
cout << "最少连乘次数：" << M[1][N] << "\n";
//for (int i = 1; i <= N; i++)//输出最少连乘次数
//{
// for (int j = i; j <= N; j++)
// {
// cout << "M[" << i << "][" << j << "] = " << M[i][j] << "\t";
// }
// cout << "\n\n";
//}
cout << "最优断开位置：\n";
Traceback(1, N, S);//输出最优解（加括号）
int T_start, T_end, time;
T_start = TimeSpend();
DynamicRecursionMultiply(P, 1, N, S);//动态规划矩阵相乘
T_end = TimeSpend();
time = T_end - T_start;
cout << "\n————动态规划矩阵相乘耗时：" << time << "毫秒\n\n";
}
}
system("pause");
}
//测试一：10 45 35 80 500 60 70 15 100 40 50 300 75 20 65 10
//测试二：300 4500 150 60 6000 200 70 300
测试一截图：
测试二截图：
所用函数：
#include<Windows.h>
using namespace std;
#define Big long double
#define MAX 10000000000000
int TimeSpend();//时间函数
Big** CreateZeros(int r, int c);//创建零矩阵
Big** CopyMatrix(int r, int c, Big** A);//复制矩阵
void PrintMatrix(int r, int c, Big** C);//输出运算结果矩阵
Big** matrixMultiply(Big** A, Big** B, int ra, int ca, int cb);//两个矩阵相乘
Big** CommonMultiply(int* p, int set, int end);//set:参与运算的第一个矩阵为给定矩阵的第set个;end:参与运算的最后一个矩阵为给定矩阵的第set个
void MatrixChain(int* p, int n, Big** m, int** s);//获取最优值及最优解的循环（穷举）方法
Big RecurMatrixChain(int* a, int i, int j, Big** m, int** s);//获取最优值及最优解的递归方法
void Traceback(int i, int j, int** s);//得到最优解
Big** DynamicRecursionMultiply(int* p, int i, int j, int** s);//使用得到的最优解进行矩阵连乘
int TimeSpend()
{
SYSTEMTIME time;
GetLocalTime(&time);//获取当前时间对象
return time.wMinute * 60 * 1000 + time.wSecond * 1000 + time.wMilliseconds;
}
Big** CreateZeros(int r, int c)
{
Big** C = new Big * [r];
for (int i = 0; i < r; i++)
{
C[i] = new Big[c];
for (int j = 0; j < c; j++)
C[i][j] = 0;
}
return C;
}
Big** CopyMatrix(int r, int c, Big** A)
{
Big** C = new Big* [r];
for (int i = 0; i < r; i++)
{
C[i] = new Big[c];
for (int j = 0; j < c; j++)
{
C[i][j] = A[i][j];
}
}
return C;
}
void PrintMatrix(int r, int c, Big** C)
{
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cout << C[i][j] << "\t";
}
cout << "\n";
}
}
Big** matrixMultiply(Big** A, Big** B, int ra, int ca, int cb)//两个矩阵相乘
{
{
Big** C = CreateZeros(ra, cb);
for (int i = 0; i < ra; i++)
{
for (int j = 0; j < cb; j++)
{
C[i][j] = 0;
for (int k = 0; k < ca; k++)
{
C[i][j] = C[i][j] + A[i][k] * B[k][j];
}
}
}
return C;
}
}
Big** CommonMultiply(int* p, int set, int end)
{
int i = set;
Big** C;
int rC, cC;
rC = p[i - 1];
cC = p[i];
C = CreateZeros(rC, cC);//第一个矩阵本身
i++;
while (i <= end)
{
long double** A, ** B;
int rA, cA;
int rB, cB;
rA = rC;
cA = cC;
A = CopyMatrix(rC, cC, C);//A=C,C为前面矩阵相乘的结果
rB = p[i - 1];
cB = p[i];
B = CreateZeros(rB, cB);
rC = rA;
cC = cB;
C = matrixMultiply(A, B, rA, cA, cB);//C=A*B
i++;
delete[]A;
delete[]B;
}
return C;
}
void MatrixChain(int* p, int n, Big** m, int** s)//循环求最优解
{
for (int i = 1; i <= n; i++)
{
s[i][i] = 0;//初始化为0
m[i][i] = 0;//初始化：矩阵到自身所需乘法次数为0
for (int j = i + 1; j <= n; j++)
{
m[i][j] = MAX;//初始化：第i个矩阵累乘至第j个矩阵所需乘法次数为无穷大
s[i][j] = i;//初始化：第i个矩阵至第j个矩阵连乘时，在第i个矩阵后加括号
}//for
}//for
for (int r = 2; r <= n; r++)//最外层循环表示相乘的矩阵个数——如n=15，r=5
{
for (int i = 1; i <= n - r + 1; i++)//在要求r个矩阵连乘的前提下，可取得的起始矩阵下标最大为n-r+1——i<=11
{
int j = i + r - 1;
//m[i][j]——————第i个矩阵累乘至第j个矩阵所需乘法次数
//m[i+1][j]—————第（i+1）个矩阵累乘至第j个矩阵所需乘法次数（累乘效果为：变成一个行数为p[i]，列数为p[j]的矩阵）
//p[i-1]*p[i]*p[j]——第i个矩阵*（m[i+1][j]的累乘后的矩阵），第i个矩阵行数为p[i-0]，行数为p[i]
m[i][j] = m[i + 1][j] + (Big)p[i - 1] * p[i] * p[j];
for (int k = i + 1; k < j; k++)
{
Big t = m[i][k] + m[k + 1][j] + (Big)p[i - 1] * p[k] * p[j];
if (t < m[i][j])//按加括号后计算矩阵相乘，所需乘法次数较按顺序累乘少；另一种加括号解法更优
{
m[i][j] = t;
s[i][j] = k;//括号应加在第k，k+1个矩阵之间
}//if
}//for
}//for
}//for
}
Big RecurMatrixChain(int* p, int i, int j, Big** m, int** s)//递归求最优解
{
if (i == j)
{
m[i][j] = 0;
s[i][j] = i;
}
else
{
m[i][j] = MAX;//当i和j不相等时，将此时的第i个到矩阵第j个矩阵相乘的次数记为无穷大，MAX应尽量大，若小于实际矩阵相乘次数，将出现数据错误
for (int k = i; k < j; k++)//从i开始一直到j开始画括号，找寻最小值
{
Big t = RecurMatrixChain(p, i, k, m, s) + RecurMatrixChain(p, k + 1, j, m, s) + (Big)p[i - 1] * p[k] * p[j];//递归求解子问题的解
if (t < m[i][j])
{
m[i][j] = t;
s[i][j] = k;
}
}
}
return m[i][j];//返回当前问题对应的最小乘法次数
}
void Traceback(int i, int j, int** s)
{
if (i == j)
{
cout << "A" << i;
}
else
{
cout << "(";
Traceback(i, s[i][j], s);
Traceback(s[i][j] + 1, j, s);
cout << ")";
}
}
Big** DynamicRecursionMultiply(int* p, int i, int j, int** s)//使用得到的最优解进行矩阵连乘
{
Big** C;
if (i == j)
{
C = CreateZeros(p[i - 1], p[j]);//当只有一个矩阵时，返回矩阵本身（生成一个零矩阵）
}
else
{
int k = s[i][j];//在第k个矩阵后断开
int rA = p[i - 1], cA = p[k];//rA、cA分别表示矩阵A的行列数
int rB = p[k], cB = p[j];
Big** A, ** B;
A = DynamicRecursionMultiply(p, i, k, s);//左半部分矩阵相乘结果
B = DynamicRecursionMultiply(p, k + 1, j, s);//右半部分矩阵相乘结果
C = matrixMultiply(A, B, rA, cA, cB);//A*B
}
return C;
}
投递阿里国际数字商业集团等公司10个岗位 >