凸多边形最优三角剖分问题

参考书籍《算法设计与分析》  王晓东   动态规划

1.问题描述

（注：是所有的三角形的权值之和，不是只计算边和弦的权值之和）

 

2.分析

 

 

 

3.编码实现：

/** 
 * @Author：胡家威  
 * @CreateTime：2011-11-10 下午12:31:16
 * @Description：凸多边形的最优三角剖分
 */

package ex2;

public class Triangulation {

  private int n;// n多边形
  private int[][] weight;// 边的权值数组

  public Triangulation(int n) {
    this.n = n;
    this.weight = new int[n][n];
  }

  public static void main(String[] args) {
    Triangulation triangulation = new Triangulation(6);
    initTriangulation(triangulation);
    int n = triangulation.getN();// 凸多边形的边数
    int[][] t = new int[n][n];// t[i][j]表示顶点{Vi-1,Vi...Vj}组成的多边形的最优三角形剖分的权值
    int[][] s = new int[n][n];// s[i][j]表示与Vi-1和Vj一起构成三角形的第三个顶点的位置
    triangulation.minWeightTriangulation2(triangulation.getN() - 1, t, s);
    System.out.println(t[1][5]);
  }

  // 初始化weight数组的信息
  public static void initTriangulation(Triangulation triangulation) {
    int[][] weight = { { 0, 2, 2, 3, 1, 4 }, { 2, 0, 1, 5, 2, 3 }, { 2, 1, 0, 2, 1, 4 }, 
        { 3, 5, 2, 0, 6, 2 }, { 1, 2, 1, 6, 0, 1 }, { 4, 3, 4, 2, 1, 0 } };
    triangulation.setWeight(weight);
  }

  // 得到最优的三角形剖分，n是总边数-1
  public void minWeightTriangulation(int n, int[][] t, int[][] s) {
    // 初始化所有的二顶点多边形权值为0
    for (int i = 1; i <= n; i++) {
      t[i][i] = 0;
    }
    // 循环求解t[i][j]
    for (int r = 2; r <= n; r++) {// (j-i)的范围[2,n]
      // 当r=2时，循环实际上是在给t赋边的值，即相邻的两个顶点的权值，例如t[1][2],t[2][3]...
      for (int i = 1; i <= n - r + 1; i++) {// i的范围[1,n+1-r]，这里i要保证i+r<=n
        int j = i + r - 1;
        t[i][j] = t[i + 1][j] + getWeight(i - 1, i, j);// 这里实际上就是k=i
        // t[i][j] = t[i][i] + t[i + 1][j] + getWeight(i - 1, i, j)
        s[i][j] = i;
        // i-1,i,j
        // 循环k，范围是[i+1,j-1]，求出最小的t[i][j]
        for (int k = i + 1; k < j; k++) {// k是i和j之间的中间顶点
          int u = t[i][k] + t[k + 1][j] + getWeight(i - 1, k, j);// 以k作为划分得到的权值
          if (u < t[i][j]) {// 如果权值更小，那么同时更新t[i][j]和s[i][j]
            t[i][j] = u;
            s[i][j] = k;
          }
        }
      }
    }
  }

  // 我的写法，在第二个循环这里不同，没有什么差别，只是我易于我理解
  public void minWeightTriangulation2(int n, int[][] t, int[][] s) {
    // 初始化所有的二顶点多边形权值为0
    for (int i = 1; i <= n; i++) {
      t[i][i] = 0;
    }
    // 循环求解t[i][j]
    for (int r = 1; r <= n; r++) {// r=(j-i)的范围[1,n]
      // 当r=1时，循环实际上是在给t赋边的值，即相邻的两个顶点的权值，例如t[1][2],t[2][3],t[3][4]...
      for (int i = 1; i <= n - r; i++) {// i的范围[1,n-r]，这里i要保证 j=i+r<=n
        int j = i + r;
        t[i][j] = t[i + 1][j] + getWeight(i - 1, i, j);// 这里实际上就是k=i
        // t[i][j] = t[i][i] + t[i + 1][j] + getWeight(i - 1, i, j)
        s[i][j] = i;// i-1,i,j
        // 循环k，范围是[i+1,j-1]，求出最小的t[i][j]
        for (int k = i + 1; k < j; k++) {// k是i和j之间的中间顶点
          int u = t[i][k] + t[k + 1][j] + getWeight(i - 1, k, j);// 以k作为划分得到的权值
          if (u < t[i][j]) {// 如果权值更小，那么同时更新t[i][j]和s[i][j]
            t[i][j] = u;
            s[i][j] = k;
          }
        }
      }
    }
  }

  // 计算一个三角形的权值之和
  public int getWeight(int i, int j, int k) {
    return weight[i][j] + weight[j][k] + weight[i][k];
  }

  public int getN() {
    return n;
  }

  public void setN(int n) {
    this.n = n;
  }

  public int[][] getWeight() {
    return weight;
  }

  public void setWeight(int[][] weight) {
    this.weight = weight;
  }

}

 

数据：

    

 

结果是： 24

通过 Wiz 发布