动态规划：凸多边形最优三角剖分算法思路及代码分析（Java）_java 三角刨分

选定基准点a，自底向上计算子多边形内的最优解。
1、 初始化，当只有一个点时，即i=j：

t[a][a]=0；

2、 两个点：a，a+1时，不计算；

3、 三个点开始计算，k=a，多边形a-1，a，a+1的解：

当前多边形的最优解即为：

t[a][a+1] = t[a][a] + t[a+1][a+1] + w(va-1,va,va+1)；

遍历所有基准点，计算三个点时的最优解。（为什么这里就要计算？见4）

4、4个点：a-1，a，a+1，a+2，解：

k = a+1
t[a][a+2] = t[a][a+1] + t[a+2][a+2] + w(va-1,va+1,va+2)；

除此，还有第二个解：

k=a

t[a][a+2] = t[a][a] + t[a+1][a+2] + w(va-1,va,va+2)；

t[a+1][a+2]=?
t[a+1][a+2]是由a,a+1,a+2三个点组成的多边形，三个点的解应该在第3步，所以第3步应该计算出所有最小子问题（三个点）的解。
比较计算出的两个解，找出最小的解，并记录切割点k
遍历所有基准点，计算最优解并记录k

5、 五个点：a-1，a，a+1，a+2，a+3，解：

k=a

t[a][a+3] = t[a][a] + t[a+1][a+3] + w(va-1,va,va+3)

k=a+1
t[a][a+3] = t[a][a+1] + t[a+2][a+3] + w(va-1,va+1,va+3)

k=a+2
t[a][a+3] = t[a][a+2] + t[a+3][a+3] + v(va,va+2,va+3)

比较求出最优解并记录k
…

算法代码（Java）：

//N：多边形边数+1（int[a]范围int[0]~int[a-1]，+1为了方便后面使用N可以直接理解为几条边）
//w[N][N]：记录凸多边形的权值，w[a][b]表示点a和点b之间连线的权值
//s[i][j]表示点i-1到j组成的凸多边形的最优剖分点
//t[i][j] 表示点i-1到j组成的凸多边形的最优三角剖分的解
public class 凸多边形最优三角剖分 {
    //六边形
    static int N = 7;
    //给定六边形的权值
    static int[][] w = {{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}};

    public static void main(String[] args) {
        MinWeightTriangulation(N, w);
    }

    public static void MinWeightTriangulation(int N, int[][] w) {
        int[][] s = new int[N][N];//存放最优剖分点k
        int[][] t = new int[N][N];//存放解
        //初始化
        for (int i = 0; i < N; i++)
            t[i][i] = 0;
        //r为间隔边数，先从两条边开始，即三个点组成的凸多边形（三角形）
        for (int r = 2; r < N; r++) {
            for (int i = 1; i < N - r; i++) {//i的范围 (N-1-1)-(i-1)>=r → i<N-r 或 i<=N-r+1，N两次-1分别是：1、初始N为边数加一 2、顶点编号从0开始
                int j = i - 1 + r;//j为i加上间隔边数
                t[i][j] = t[i][i] + t[i + 1][j] + Weight(i - 1, i, j);
                s[i][j] = i;//记录k值
                //开始考虑不同的k值
                for (int k = i + 1; k < j; k++) {
                    int min = t[i][k] + t[k + 1][j] + Weight(i - 1, k, j);
                    if (min < t[i][j]) {//有更优解
                        t[i][j] = min;
                        s[i][j] = k;
                    }
                }
            }
        }
        System.out.println("最优解：" + t[1][N - 2]);
        Traceback(1, N - 2, s);
    }
    
    static void Traceback(int i, int j, int[][] s) {
        if (i == j) return;
        //子问题的k值
        Traceback(i, s[i][j], s);
        Traceback(s[i][j] + 1, j, s);
        System.out.println("剖分点："+(i - 1) + "  " + j + "  " + s[i][j]);
    }

    public static int Weight(int a, int b, int c) {//求三角形的权值
        return w[a][b] + w[b][c] + w[a][c];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

结果：