matrixchain.java

《算法设计与分析》王晓东编著

public class MatrixChain {

	
	public static void matrixChain(int[] p, int [][]m, int [][]s)
	{
		int n=p.length-1;
		for (int i=1;i<=n;i++) m[i][i]=0;
		for (int r=2;r<=n;r++)
		  for (int i=1;i<=n-r+1;i++) {
			  int j=i+r-1;
			  m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
			  s[i][j]=i;
			  for (int k=i+1;k<j;k++) {
				  int 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;
				  }
			  }
		  }		
	}
	
	/* 根据断点矩阵s，输出最优计算次序 */
	public static void traceback(int [][]s, int []p, int i, int j)
	{
		if (i==j) return;
		traceback(s,p,i,s[i][j]);
		traceback(s,p,s[i][j]+1,j);
		System.out.println("Multiply A("+p[i-1]+"*"+p[s[i][j]]+
				") and A("+p[s[i][j]]+"*"+p[j]+")");
	}
	
	public static void main(String[] args) 
	{
		/* 初始化矩阵链 
		 * A1(30*35), A2(35*15), A3(15*5), A4(5*10)
		 * A5(10*20), A6(20*25) */
		int[] p=new int[]{30,35,15,5,10,20,25};
		int n=p.length;
		
		/* 初始化最优结果矩阵 */
		int[][] m=new int[n][n];
		
		/* 初始化断点矩阵 */
		int[][] s=new int[n][n];
		
		/* 求最优矩阵相乘计算次序 */
		matrixChain(p,m,s);
		
		/* 输出结果 */
		System.out.println("min="+m[1][n-1]+"\n");
		traceback(s,p,1,n-1);
	}
}