算法设计与分析矩阵连乘问题的动态规划与备忘录算法对比分析

阅读量：

问题描述

设有n个矩阵依次为A₁, A₂, …, Aₙ，在每对相邻的两个矩阵A_i和A_{i+1}之间存在相乘的可能性（其中i=1, 2, …, n-1）。我们的目标是找到最优的矩阵相乘顺序，并确定这一顺序下所有矩阵相乘所需的标量乘法次数最少。

动态规划解题思路

该函数用于构建两个二维数组m[][]和s[][], 其中分别对应不同的计算结果

当s[i][j]=k时，则表示将矩阵链段i…j最优地分解为i…k和k+1…j两部分

复制代码

    public static void matrixChain(int []p,int [][]m,int [][]n){
    	int n=p.length-1;
    	for(int i=1;i<=n;i++)
    		m[i][i]=0;//初始化存储矩阵链的数组对角线
    				  //矩阵链中只有一个矩阵时，次数为0，注意m[0][X]是未使用的
    	for(int r=2;r<=n;r++){//矩阵链长度，长度从2开始
    		for(int i=i;i<=n-r+1;i++){//根据矩阵链长度，控制链的最大起始点
    			int j=i+r+1;//定义矩阵链的末尾矩阵
    			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//向右开始矩阵相乘

全部评论 (0)

还没有任何评论哟~