minweighttriangulation.java

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

public class MinWeightTriangulation {

	public static int weight[][]; /* 点邻接矩阵 */
	
	/* 计算三角形三条边权值之和,i,j,k为三个顶点 */
	public static int w(int i,int j,int k)
	{
		return weight[i][j]+weight[j][k]+weight[k][i];	
	}
	
	/* 用动态规划法计算最优三角剖分
	 * 输入参数说明： 
	 * n--计算用的边最大编号,n的值是顶点数减1,参见课本,计算用到的边为A1~An
	 * t--保存最优值的二维数组,t[i][j]表示从边Ai到Aj的最优剖分权值之和
	 * s--保存断点的二维数组
	 * */
	public static void minWeightTriangulation(int n,int[][] t,int[][] s)
	{		
		for (int i=1;i<=n;i++) t[i][i]=0;
		for (int r=2;r<=n;r++)
		  for (int i=1;i<=n-r+1;i++) {
			  int j=i+r-1;
			  t[i][j]=t[i+1][j]+w(i-1,i,j); //注:顶点V(i-1),Vi与边Ai相关联
			  s[i][j]=i;
			  for (int k=i+1;k<j;k++) {
				  int u=t[i][k]+t[k+1][j]+w(i-1,k,j);
				  if (u<t[i][j]) {
					  t[i][j]=u;
					  s[i][j]=k;
				  }
			  }
		  }
	}
	
	/* 输入起始边i和终止边j，以及断点矩阵s，
	 * 递归构造一组剖分方案 */
	public static void traceback(int i,int j,int[][] s)
	{
		if  (i==j) return;
		traceback(i,s[i][j],s);		
		traceback(s[i][j]+1,j,s);
		System.out.println("(V"+(i-1)+",V"+s[i][j]+")--(V"
				+s[i][j]+",V"+j+")--(V"+j+",V"+(i-1)+")");
	}
	
	public static void main(String[] args) {
		/* 初始化带权值的邻接矩阵 */
		weight=new int[][]{{ 0, 1, 6,18, 1},
				           { 1, 0, 1,14,20},
				           { 6, 1, 0, 1, 2},
				           {18,14, 1, 0, 1},
				           { 1,20, 2, 1, 0}};
		int n=weight.length;
		int[][] t=new int[n][n];
		int[][] s=new int[n][n];
	
		/* 计算最优剖分 */
		minWeightTriangulation(n-1,t,s);
		System.out.println(t[1][n-1]);
		
		/* 输出最优剖分的一组方案 */
		traceback(1,n-1,s);		
	}

}