算法导论之动态规划：矩阵链相乘

心已赠人 2022-07-24 06:21 187阅读 0赞

**矩阵链相乘**问题：给定n个矩阵的链<A1,A2,A3……,An>，矩阵Ai的规模为p(i-1)\*pi(1<=i<=n)，求完全括号化方案，使得计算乘积A1，A2，A3……An所需标量乘法次数最少。

我们通过分析可以得到如下一个最小代价括号化方案的递归求解公式：

m\[i\]\[j\]=0                                                                                如果i=j

m\[i\]\[j\]=min\{m\[i\]\[k\]+m\[k+1\]\[j\]+p(i-1)pkpj\}   (i<=k<j)        如果i<j

其中p(i-1)pkpj的含义是：

![20160516094553767][]

**实现代码**如下：

#include <stdio.h>
    #include <limits.h>
    
    struct Matrix{
    	int row;
    	int column;
    };
    typedef struct Matrix Matrix;
    
    void doMatrixChainOrder(Matrix chain[],int M[][6],int S[][6]){
    	int i,j,k,l,n=6,q;
    	for(k=1;k<n;k++){
    		for(i=0;i<n-k;i++){
    			j=i+k;
    			M[i][j]=INT_MAX;
    			for(l=i;l<j;l++){
    				q=M[i][l]+M[l+1][j]+chain[i].row*chain[l].column*chain[j].column;
    				if(q<M[i][j]){
    					M[i][j]=q;
    					S[i][j]=l;
    				}
    			}
    		}
    	}
    }
    
    void printOptimalParens(int S[][6],int i,int j){
    	if(i==j){
    		printf("A%d",i);
    	}else{
    		printf("(");
    		printOptimalParens(S,i,S[i][j]);
    		printOptimalParens(S,S[i][j]+1,j);
    		printf(")");
    	}
    }
    int main(int argc, char *argv[])
    {
    	Matrix chain[6];
    	chain[0].row=5;
    	chain[0].column=10;
    	chain[1].row=10;
    	chain[1].column=3;
    	chain[2].row=3;
    	chain[2].column=12;
    	chain[3].row=12;
    	chain[3].column=5;
    	chain[4].row=5;
    	chain[4].column=50;
    	chain[5].row=50;
    	chain[5].column=6;
    	int M[6][6]={
    		0
    	},S[5][6];
    	doMatrixChainOrder(chain,M,S);
    	printf("%d\n",M[0][5]);
    	printOptimalParens(S,0,5);
    	printf("\nM[i][j]:\n");
    	int i ,j;
    	for(i=0;i<6;i++){
    		for(j=0;j<6;j++){
    			printf("%d\t",M[i][j]);
    		}
    		printf("\n");
    	}
    	return 0;
    }

此算法的时间复杂度是Ω(n^3)。

**参考资料**：  
算法导论  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51422466  
作者：WSYW126

[20160516094553767]: /images/20220722/3372bfc6dc0e4b2bbff3411ebe404334.png