凸多边形最优三⾓剖析_动态规划⼀、问题描述多边形的三⾓剖分：将多边形分割成互不相交的三⾓形的弦的集合T。
最优剖析：给定凸多边形的三⾓剖分，使得该三⾓剖分中诸三⾓形上权之和最⼩(是所有的三⾓形的权值之和，不是只计算边和弦的权值之和)。
⼆、解题思路及所选算法策略的可⾏性分析基本思路：动态规划。
最优⼦结构：若凸(n+1)边形p={V0,V1,…,VN}的最优三⾓剖分T包含三⾓形V0VkVn, 1<=k<n。
则T的权为3个部分权的和：三⾓形V0VkVn的权，⼦多边形{V0,V1,…,Vk}和{Vk,Vk+1,…,Vn}的权之和。
可断⾔，有T确定的这2个⼦多⼥性的三⾓剖析也是最优。
因为若有更⼩的三⾓剖析将导致T不是最优的三⾓剖析的⽭盾递归结构：定义t[i][j],1<=i<j<=n为凸⼦多边形{Vi-1，Vi,…,Vj}的最优三⾓剖分所对应的权函数值，即其最优值。
最优剖分包含三⾓形Vi-1VkVj的权，⼦多⼥性{Vi-1,Vi,…,Vk}和{Vk,Vk+1,…,Vj}的权之和。
凸(n+1)边形P的最优权值为t[1][n]。
T[1][n]=min{t[1][k]+t[k+1][n]+w(V0VkVn)|1<=k<n}设退化的多边形{Vi-1,Vi}具有的权值为0，因为此刻够不成多边形。
三、伪代码描述及复杂度分析伪代码：Public class triangle{初始化各点两两相连权重；初始化所有⼆顶点多边形权值为0；//循环求解t[i][j]For(⼦多边形的始末顶点间隔步长){For(起始点位置){该层循环起始点对应末点的位置；求解t[i][j];记录第三点位置；找到最⼩权值位置；}}}复杂度分析：对于n规模的问题，算法需要申请n*n空间的⼆位数组，所以空间复杂度为O(n^2)。
求解问题⽤到三层for循环，所以时间复杂度为O(n^3)。
四、代码实现package 动态规划;public class triangle {private int n;// n多边形private int[][] weight;// 边的权值数组public triangle(int n) {this.n = n;this.weight = new int[n][n];}public static void main(String[] args) {triangle triangulation = new triangle(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(triangle 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是总边数-1public void minWeightTriangulation(int n, int[][] t, int[][] s) {// 初始化所有的⼆顶点多边形权值为0for (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<=nint 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) {// 初始化所有的⼆顶点多边形权值为0for (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<=nint 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;}}五、代码运⾏结果截图。
