算法导论15.2 矩阵链乘法

小鱼儿 2022-04-14 04:06 132阅读 0赞

下面讲述一下动态规划法的一个应用实例——矩阵链乘法。

下面是Java语言实现的矩阵链乘法，代码按照算法导论严格编写，大家可以对照着算法导论进行学习。

实现代码如下：

package homework.part2.work1;
    
    public class Matrix_Chain {
    	
    	public int[][] m;
    	public int[][] s;
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] array={5,10,3,12,5,50,6};
    		Matrix_Chain chain=new Matrix_Chain();
    		chain.matrix_chain_order(array);
    		chain.matrix_chain_print(chain.s, 0, array.length-2);
    	}
    	
    	public void matrix_chain_order(int[] array)
    	{
    		int n=array.length-1;
    		m=new int[n][n];s=new int[n][n];
    		for(int i=0;i<n;i++)
    		{
    			for(int j=0;j<n;j++)
    			{
    				m[i][j]=0;s[i][j]=0;
    			}
    		}
    		for(int chainlength=2;chainlength<=n;chainlength++)
    		{
    			for(int i=0;i<n-chainlength+1;i++)
    			{
    				int j=i+chainlength-1;
    				m[i][j]=Integer.MAX_VALUE;
    				for(int k=i;k<j;k++)
    				{
    					int q=m[i][k]+m[k+1][j]+array[i]*array[k+1]*array[j+1];
    					if(q<m[i][j])
    					{
    						m[i][j]=q;
    						s[i][j]=k;
    					}
    				}
    			}
    		}
    	}
    	
    	public void matrix_chain_print(int[][] s,int i,int j)
    	{
    		if(i==j)
    		{
    			System.out.print("A"+i);
    		}else
    		{
    			System.out.print("(");
    			matrix_chain_print(s,i,s[i][j]);
    			matrix_chain_print(s,s[i][j]+1,j);
    			System.out.print(")");
    		}
    	}
    }

利用上面的代码，现在对书中的例子和15.2-1练习题给出运行结果。

书中例子的运行结果：

((A0(A1A2))((A3A4)A5))

习题15.2-1的运行结果：

((A0A1)((A2A3)(A4A5)))