动态规划算法之矩阵连乘积问题1

首先我们了解一下什么是动态规划算法，动态规划算法与分治法类似，其基本思想也是将待求问题分解成若干个子问题。但是与分治法不同的是，适合于动态规划算法的问题经分解得到的子问题不是互相独立的。假若用分治法解决此类问题，由于子问题太多，导致最后求解需要耗费极大的指数时间。而动态规划算法就很好的解决了此类问题，为了避免大量运算和重复运算，我们可以采用一个表（可以为数组）来记录已经解决过的问题，倘若下回再利用的话，我们直接在表中查找就好，这样就避免了大量的重复运算。

下面以具体的例子矩阵连乘问题来说明如何运用动态规划算法的思想

• 给定n个矩阵{A1,A2,A3,......,An}，其中Ai与A(i+1)是可乘的，i=1,2,3,......,n-1。考察这n个矩阵的连乘积A1,A2,A3,......,An。

分析：

（1）矩阵乘法满足结合律，有不同的计算次序，用加括号的方式来确认

（2）若一个矩阵连乘积的计算次序完全确定，即该连乘积已完全加括号，则可依此次序反复调用 2 个矩阵相乘算法计算矩阵连乘积，完全加括号的矩阵连乘积可递归地定义为：

• 单个矩阵是完全加括号的
• 如矩阵连乘积 A 是完全加括号的，则 A 可以表示为 2 个完全加括号的矩阵连乘积 B 和 C 的乘积并加括号，即 A = ( BC )。

每一种加括号方式对应一种矩阵连乘积的计算次序，不同的“加括号”方法得到的计算次序其计算量差别可能很大。

考虑两个矩阵乘积所需的计算量：若 A 是一个 p * q 矩阵，B 是一个 q * r 矩阵，则其乘积 C = AB 是一个 p * r 矩阵。则上述矩阵相乘总共需要 pqr 次数乘。

我们用一个例子看一下在不同次序下计算量的区别

PS：推导过程部分图片来自西邮刘伟老师的课件内容。

从上图我们可以看出最少的计算量和最多的计算量差了8倍，因此我们找一个好的计算次序是非常有必要的。矩阵连乘积是一个最优化问题，可以采用动态规划法解决。为了解决n个矩阵A1,A2,A3,......,An连乘积的最优计算次序，先考虑它的子问题Ai,Ai+1,......,Aj的最优计算次序，若子问题解决，令i=1,j=n,原问题自然解决。

• 建立状态转移方程

所以，k=i~j-1，而Pi-1PkPj可以这样理解，现在有一个10*20，20*30的矩阵，那么P0=10，P1=20，P2=30。

代码实现如下：

// 动态规划算法求矩阵连乘积问题...

#include<stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 100 

void DPMatrixChain( int p[MAX_SIZE], int n, int m[MAX_SIZE][MAX_SIZE], int s[MAX_SIZE][MAX_SIZE] )
{
	int i,j,r;
	int t;
	int k;
    for(  i = 1; i <= n; i++ )//初始化对角线，因为m[i][j]的值位于上三角区域，当i=j时为单一矩阵，无需计算 
    	m[ i ][ i ] = 0;
  	for(  r = 2; r <= n; r++ )//变量r表示矩阵链长的递增，如r=2，表示AiA(i+1)，此处处理2~n的所有矩阵链 
  	{                         //上边的对角线初始化相当于r=1 
		for(  i = 1; i <= n - r + 1; i++ )//此处取矩阵子链，长度为r的矩阵子链共有n-r+1中组合方式 
		{ 
	   		j = i + r - 1;
	  		m[ i ][ j ] = m[ i + 1 ][ j ] + p[ i - 1 ] * p[ i ] * p[ j ];
	  		s[ i ][ j ] = i;
	  	  	for(  k = i + 1; k < j; k++ )
	  		{
         		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 printM(int m[MAX_SIZE][MAX_SIZE], int n)
{
	int i,j;
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= n; j++)
		{
			printf("%d\t",m[i][j]);
		}
		printf("\n"); 
	}
}

void printS(int s[MAX_SIZE][MAX_SIZE], int n)
{
	int i,j;
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= n; j++)
		{
			printf("%d\t",s[i][j]);
		}
		printf("\n"); 
	}
}

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]);
	}
	DPMatrixChain( p, n, m, s );
	printf("最少数乘次数矩阵 \n");
	printM(m ,n);
	printf("最佳断开位置矩阵 \n");
	printS(s, n);	
}

运行截图：