[数据结构与算法]矩阵连乘C++

给定n个矩阵 { A 1 , A 2 , . . . , A n } \{A_1,A_2,...,A_n\} {A1?,A2?,...,An?}，其中$A_i$和$A_{i+1}$是可乘的（$i=1,2,...,n?1$）。考察这n个矩阵连乘积$A_1,A_2,...,A_n$。
由于矩阵连乘法满足结合律，因此计算矩阵连乘积可有不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说，该连乘积完全加括号，则可依次序反复调用两个矩阵相乘的标准算法计算出矩阵乘积。完全加括号的连乘可递归定义为：

• 单个矩阵式完全加括号的；
• 矩阵连乘积A是完全加阔i好的，则A可表示为两个完全加快了括号的矩阵连乘积B和C的乘积并加括号。

首先考虑计算两个矩阵连乘积所需的计算量。计算两个矩阵乘积的标准算法如下，其中ra,ca和rb,cb分别表示矩阵A和B的行数和列数

void matrixMultioply(int** a, int** b, int** c, int ra, int ca, int rb, int cb)
{
	if (ca!=rb)
	{
		error("矩阵不可乘");
	}
	for (int i = 0; i < ra; i++)
	{
		for (int j = 0;j < cb;j++)
		{
			int sum = a[i][0] + b[0][j];
			for (int k = 1; k < ca; k++)
			{
				sum += a[i][k] * b[k][j];
			}
			c[i][j] = sum;
		}
	}
}

分析最优解的结构

设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解的特征结构。为方便起见，将矩阵连乘积$A_i{A}_{i+1}...A_j$简计$A[1:n]$的最优计算次序。

建立递归关系

设计动态规划算法的第2步时递归地定义最优值。对于矩阵连乘积地最优计算次序问题，设计算$A[i:j]$，所的最少数乘积次数为$m[i[[j]$，则原问题的最优值为$m[1][n]$
当$i=j$时，$A[i:j]=A_i$为单一矩阵，无须计算，因此$m[i][i]=0(i=1,2,..,n)$
当$i<j$时，可利用最优子结构性质来计算$m[i][j]$。事实上，若计算$A[i:j]$的最优次序在$A_k(i\le k<j)$和$A_{k+1}$之间断开，则$m[i][j]=m[i][k]+m[k+1][j]+p_{i?1}{p}_k{p}_j$。由于在计算时并不知道断开点k的位置，所有k还未定。不过k的位置只有$j?i$个可能，即$k\in i,i+1,...,j?=1$。因次，k是这j-i个位置中使计算量达到最小的哪个位置。从而，$m[i][j]$可递归地定义为
m [ i ] [ j ] = { 0 i = j min ? i ≤ k < j { m i n [ i ] [ k ] + m [ k + 1 ] [ j ] + p i ? 1 p k p j } i < j m[i][j]=\left \{ \begin {aligned} 0 &&&&&&i=j \\ \min_{i\le k<j}\{min[i][k]+m[k+1][j]+p_{i-1}p_kp_j\}&&&&&& i<j \end {aligned} \right . m[i][j]=????0i≤k<jmin?{min[i][k]+m[k+1][j]+pi?1?pk?pj?}??????i=ji<j?
若将对应$m[i][j]$的断开位置k记为$s[i][j]$，在计算出最优值$m[i][j]$后，递归地由$s[i][j]$构造出相应地最优解

计算最优值

void MatrixChian(int* p, int n, int** m, int** s)
{
	for (int i = 0; i <= n; i++)
	{
		m[i][i] = 0;
	}
	for (int  r = 0; r <= n; r++)
	{
		for (int i = 1;i <= n - r + 1;i++)
		{
			int j = i + r - 1;
			m[i][j] = m[i + 1][j] + p[i+1]*p[i] * p[i];
			s[i][j] = i;
			for (int 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;
					s[i][j]= k;
				}
			}
			{

			}
		}
	}
}

构造最优解

void Traceback(int i, int j, int** s)
{
	if (i == j)
		return;
	Traceback(i, s[i][j], s);
	Traceback(s[i][j] + 1, j, s);
	cout << "Multiply A" << i << "," << s[i][j];
	cout << "and A" << (s[i][j] + 1) << "，" << j << endl;
}