备忘录方法之矩阵连乘积问题

在之前的文章中，我们学习了如何用动态规划算法实现矩阵的连乘积问题，由于矩阵连乘积问题具有子问题重叠性，所以采用递归算法求解时有些子问题会被反复计算多次，从而导致效率低下。如果在递归算法中引入二维数组 m[i][j] ，求解子问题后将解储存到 m[i][j] 中，下次可以直接读取使用。这样就可以得到一个基于递归算法的高效方法，即备忘录方法。备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解，需要注意的是，备忘录方法是动态规划算法的变形。

接下来我们用代码实现一下：

//用备忘录方法解决矩阵连乘积问题 

#include<stdio.h>

#define MAX_SIZE 100

int LookupChain(int i, int j, int p[MAX_SIZE], int m[MAX_SIZE][MAX_SIZE], int s[MAX_SIZE][MAX_SIZE]);
int MemoizedMatrixChain(int n, int m[MAX_SIZE][MAX_SIZE], int s[MAX_SIZE][MAX_SIZE]);

int MemoizedMatrixChain(int n, int p[MAX_SIZE], int m[MAX_SIZE][MAX_SIZE], int s[MAX_SIZE][MAX_SIZE])
{
	int i,j;
	//将最少数乘次数矩阵全部初始化为0 
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= n; j++)
		{
			m[i][j] = 0;
		}
	}
	return LookupChain(1,n,p,m,s);
}

int LookupChain(int i, int j, int p[MAX_SIZE], int m[MAX_SIZE][MAX_SIZE], int s[MAX_SIZE][MAX_SIZE])
{
	if ( m[ i ][ j ] > 0 ) 
		return m[ i ][ j ];
	//因为m[i][j]的值位于上三角区域，当i=j时为单一矩阵，无需计算，直接返回0 
  	if ( i == j ) 
	  	return 0;
  	//令k = i，即(i,k)~(k+1,j) 用于计算最小k值 
  	int u = LookupChain( i, i ,p, m, s ) + LookupChain( i + 1, j, p, m, s ) + p[ i - 1 ] * p[ i ] * p[ j ];
  	s[ i ][ j ] = i;
  	//该部分依次断开k=(i+1)~(j-1)，求出s和m 
  	for ( int k = i + 1; k < j; k++ )
  	{
    	int t = LookupChain( i, k ,p, m, s) + LookupChain( k + 1, j ,p, m, s) + p[ i - 1 ] * p[ k ] * p[ j ];
	 	if ( t < u )
    	{ 
      	u = t;
      	s[ i ][ j ] = k;
    	}
  	}
  	m[ i ][ j ] = u;
  	return u;
}

int main()
{
	int p[MAX_SIZE];//矩阵连乘积A1A2...An中矩阵的位数一维数组，其中Ai的维数为Pi-1*Pi，i=1,2,..,n 
	int n;//矩阵个数 
	int m[MAX_SIZE][MAX_SIZE];//最少数乘次数 
	int s[MAX_SIZE][MAX_SIZE];//A[i,j]的 最佳断开位置 
	int i;
	printf("请输入矩阵个数：\n");
	scanf("%d",&n);
	printf("请输入矩阵的维度，如现在有一个10*20，20*30的矩阵，那么P0=10，P1=20，P2=30\n");
	for(i = 0; i <= n; i++)
	{
		scanf("%d",&p[i]);
	}
	int minMuNum = MemoizedMatrixChain( n, p, m, s ); //最少数乘次数 
	printf("%d\n",minMuNum);
} 

这里我们需要注意一点，备忘录方法自顶向下计算，而动态规划算法是由对角线向右上角计算的。

运行结果如下：