2016-10-07

MatrixChain

动态规划 —— 矩阵连乘积问题

问题描述：

给定n个矩阵{A1,A2,…,An}，其中Ai和Ai+1是可乘的，i=1，2…，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

算法分析：

问题的解空间：

n个矩阵可能的完全加括号方式有P(n)=Catalan(n-1)，所以P(n)是随n的指数级增长的，因此穷举法不是一个有效的算法。

最优子结构：

设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]。

当i=j时，A[i:j]=Ai，因此，m[i][i]=0，i=1,2,…,n

当i<j时，若A[i:j]的最优次序在Ak和Ak+1之间断开，i<=k<j,则：m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj。

由于在计算是并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i个可能。因此，k是这j-i个位置使计算量达到最小的那个位置。

递归的定义最优解

重叠子问题：

一般取原问题规模为4-6的来验证是否存在重叠子问题

根据动态规划方程设计数据结构：

1)很显然这里使用二维数组，然后根据递归方程的特点确定填表的方式，这里采用 对角线填法
2) 填充顺序原则： 要保证当前填充的这个格子的子问题都已经计算出来了。

计算最优值

/* 计算矩阵连乘积的动态规划算法 */
#define N 51
int p[N];		//存放矩阵的阶 
int m[N][N];	//m[i][j]代表A[i,j]最少的乘法次数, 即最优值 
int s[N][N];	//s[i][j]代表A[i,j]的最优次序中的断开位置 k, 根据s[i][j]的值可构造出相应的最优解
void MatrixChain(int n)		//n表示矩阵个数 
{
	for(int i = 1; i <= n; i++)
	{
		m[i][i] = 0;	//r = 1, 只有一个矩阵的情况 
	}
	
	// 填表：对角线填法 
	// r表示矩阵链的长度 
	for(int r = 2; r <= n; r++)
	{
		for(int i = 1; i <= n-r+1; i++)	// n-r+1是对角线的长度 
		{
			int j = i + r - 1;			//i, j表示对角线的下标 
			m[i][j] = 2000000000;
			//搜寻最优值 
			for(int k = i; k < j; k++)	//寻找代价最小的那个 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;		//记录最优值的那个k 
				}
			}
		}
	}
}

构造最优解

/* 构造最优解 */
void TrackBack(int i, int j)
{
	if( i == j )
		printf("A%d", i);
	else
	{
		cout << "(";
		TrackBack(i, s[i][j]);
		TrackBack(s[i][j]+1, j);
		cout << ")";
	}
}

自顶向下的递归算法(备忘录)

#define N 51
int p[N];		//存放矩阵的阶 
int m[N][N];	//m[i][j]代表A[i,j]最少的乘法次数, 即最优值 
int s[N][N];	//s[i][j]代表A[i,j]的最优次序中的断开位置 k, 根据s[i][j]的值可构造出相应的最优解
int Recurve(int i, int j)
{
	if(m[i][j] > 0)
		return m[i][j];
	if(i == j)
		return 0;
		
	int u = Recurve(i, i) + Recurve(i+1, j) + p[i-1] * p[i] * p[j];
	s[i][j] = i;
	
	for(int k = i+1; k < j; k++)
	{
		int t = Recurve(i, k) + Recurve(k+1, j) + p[i-1] * p[k] * p[j];
		if(t < u)
		{
			u = t;
			s[i][j] = k;
		}
	}
	m[i][j] = u;	//将结果存入备忘录 
	return u;
}