matrix_chain.java

由于矩阵连乘不同结合方式的运算工作量很不一样. 工作量相差也非常大；所以要寻找一种最佳的结合方式, 然后再执行矩阵乘法运算

/**
 *动态规划：矩阵连乘结合
 */
public class Matrix_Chain
{
	public static void main(String[] args)
	{
		/*假设矩阵：
		int[][] A0=new int[10][30];
		int[][] A1=new int[30][70];
		int[][] A2=new int[70][1];
		int[][] A3=new int[1][200];
		*/
		int[] r={10,30,70,1,200};
	
		int[][] d=new int[r.length-1][r.length-1];
				
		matrixChain(r,d);
		
		System.out.println("\nD矩阵如下所示:");
		for(int i=0;i<d.length;i++)
		{
			for(int j=0;j<d[0].length;j++)
			{
				System.out.print(d[i][j]);
				System.out.print("\t");
			}
			System.out.println();
		}
		
		System.out.println("\n结合方式：");		
	    printMatrix(d,0,d.length-1);
		System.out.println();
	}
	
	
	/**
	 *计算D矩阵元素的数值
	 */
	public static void matrixChain(int[] r,int[][] d)
	{
		int n=r.length-1;
		for(int i=0;i<n;i++)
			d[i][i]=0;
		
		for(int i=0;i<=n-2;i++)
		{
			for(int j=0;j<=n-i-2;j++)
			{
				d[j][j+i+1]=Integer.MAX_VALUE;
				for(int k=0;k<=i;k++)
				{
					int q=d[j][k+j]+d[j+k+1][i+j+1]+r[j]*r[j+k+1]*r[j+i+2];
					if(q<d[j][j+i+1])
					{
						d[j][j+i+1]=q;
						d[j+i+1][j]=j+k;
					}
				}
					
			}	
		}
	}
	
	/**
	 *给出矩阵Mi Mi+1 … Mj 连乘运算量最小的结合方式
	 */
	public static void printMatrix(int[][] d,int i,int j)
	{
		if(i==j)
			System.out.print("p["+i+"]");
		else 
		{
			System.out.print("(");
			printMatrix(d,i,d[j][i]);
			printMatrix(d,d[j][i]+1,j);
			System.out.print(")");
		}
	}
}