矩阵连乘问题.cpp

算法分析部分

#include<iostream>
using namespace std;
/*
给定n个矩阵{A1,A2,...,An}，其中Ai与Ai+1是可乘的，i = 1,2...,n-1。我们
要计算出这n个矩阵的连乘积A1A2...An。
*/
/*
分析最优子结构：
设计求解具体问题的动态规划算法的第一步是刻画该问题的
最优结构的特征。为方便，将矩阵连乘AiAi+1...Aj简记为A[i:j]。
我们来看计算A[1:n]的一个最优次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开
，1<=k<n，则完全加括号方式为((A1...Ak)(Ak+1...An))。依此顺序
，我们先计算A[1:k]和A[k+1:n]，然后将计算结果相乘得到A[1:n].

问题的关键特征是：计算A[1:n]的一个最优次序所包含的计算矩阵A[1:k]和A[k+1:n]的次序也是最
优的。事实上，若有一个计算A[1:k]的次序需要的计算量更少，则用此次序替换原来的计算A[1:k]
的次序，得到的计算A[1:n]的次序需要的计算量将比最优次序所需要的计算量更少，这是一个矛盾。

因此，矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
一个问题的最优子结构性质，是该问题能够用动态规划算法求解的显著特征。
*/

/*
建立递归关系：
设计一个动态规划算法的第二步是递归地定义最优值。对于矩阵连乘积的最优计算次序
问题，设计算A[i:j]，1<=i<=j<=n，所需的最少数乘次数为m[i][j]，则原问题的最优
值为m[1][n]。
m[i][j]可以递归地定义为：
m[i][j]=0 (i==j)
m[i][j]=min{m[i][k] + m[k+1][j] + Pi-1PmPj}i<=k<j

若将对应于m[i][j]的断开位置k记为s[i][j]，在计算出最优值
m[i][j]后，可递归地由s[i][j]构造出相应的最优解
*/

/*
计算最优值
根据计算m[i][j]的递归式，容易写一个递归算法来计算m[1][n]
在递归计算的过程中，不同的子问题的个数只有O(n^2)个。事实上，对于1<=i<=j<=n不同的
有序对(i,j)对应于不同的子问题。因此不同子问题的个数最多只有(n,2)+n=O(n^2)个。
递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著
特征。

用动态规划算法解此问题时，可依据其递归式以自底向上的方式进行计算。在计算过程中，
保存已经解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而
避免了大量的重复计算，最终得到多项式的时间算法。下面所给出的计算m[i][j]的动态规划算法
中，输入参数{p0,p1,...,pn}存储于数组p中。算法除了输出最优数组m外，还输出记录最优断开
位置的数组s
*/

//p数组记录的是每个矩阵的维数
void MatrixChain( int *p,int n,int **m,int **s )
{
	for( int i = 1; i <= n; ++i )
	{
		m[i][i] = 0;
	}
	
	for( int r = 2; r <= n; ++r )
	{
		for( int i = 1; i <= n - r + 1; ++i )
		//是为了只计算i:j的最小乘法次数，其中要求i<j，因为i>j没意义
		{
			int j = i + r - 1;
			m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
			s[i][j] = i;
			cout<<s[i][j]<<" "<<endl;
			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;
				}
			}
		}
	}
}

/*
构造最优解
动态规划算法的第4步是构造问题的一个最优解。算法MatrixChain只是计算出了最优
值，并位给出最优解。

MatrixChain已记录了构造一个最优解所需要的全部信息。事实上，s[i][j]中的数k告诉我们
计算矩阵链A[i:j]的最佳方式应在矩阵Ak和Ak+1之间断开，即最优的加括号方式应为(A[i:k]
)(A[k+1:j])。因此，动s[1][n]中记录的信息可知计算A[1:n]的最优加括号方式为
(A[1:s[1][n])(A[s[1][n]+1:n)。
*/

/*
下面的算法Traceback按算法MaxtrixChain计算出的断点矩阵s
指示的加括号方式输出计算A[i:j]的最优计算顺序。
*/

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

int main()
{
	int n = 6;
	int *p = new int[7];
	p[1] = 35;
	p[2] = 15;
	p[3] = 5;
	p[4] = 10;
	p[5] = 20;
	p[6] = 25;

	int **m = new int*[7];
	int **s = new int*[7];
	for( int i = 0; i < 7; ++i )
	{
		m[i] = new int[7];
		s[i] = new int[7];
		for( int j = 0; j < 7; ++j )
		{
			m[i][j] = 0;
			s[i][j] = 0;
		}
	}

	MatrixChain( p,6,m,s );
	for( int t = 0; t < 7; ++t )
	{
		for( int q = 0; q < 7; ++q )
		{
			cout<<s[t][q]<<" ";
		}
		cout<<endl;
	}
	Trackback( 1, 6, s );

	return 0;
}