recurmatrixchain.java

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

public class RecurMatrixChain {

	public static int p[];  /* 矩阵链 */
	public static int s[][];  /* 记录断点的矩阵 */
	public static int Count[][]; /* 记录子区间被重复计算的次数 */
	
	/* 用递归算法计算最优矩阵链乘问题 */
	public static int recurMatrixChain(int i,int j)
	{
		Count[i][j]++; // 计算[i:j]区间的次数累加
		
		if (i==j) return 0;
		
		int u=recurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];
		s[i][j]=i;
		for (int k=i+1;k<j;k++) {
			int t=recurMatrixChain(i,k)+recurMatrixChain(k+1,j)
			     +p[i-1]*p[k]*p[j];
			if (t<u) {
				u=t;
				s[i][j]=k;
			}
		}
		return u;
	}
	
	public static void main(String[] args) {
		/* 初始化矩阵链 A1(30*35), A2(35*15), A3(15*5), A4(5*10) */
		p=new int[]{30,35,15,5,10};
		int n=p.length;
		
		/* 初始化断点矩阵 */
		s=new int[n][n];
		
		/* 初始化重复计算子问题次数矩阵，
		 * Count[i][j]表示子问题[i:j]被重复计算的次数 */		
		Count=new int[n][n];
		
		/* 求最优矩阵相乘计算次序 */
		System.out.println("min="+recurMatrixChain(1,n-1)+"\n");
		
		/* 输出子问题被重复计算的次数 */
		for (int i=1;i<n;i++)
		  for (int j=i;j<n;j++)
			  if (Count[i][j]>0) 
				  System.out.println("["+i+":"+j+"] "+Count[i][j]+" time(s)");				  
	}
}