算法设计与分析——凸多边形最优三⾓剖分（动态规划） ⼀、问题描述
业务激活多边形是平⾯上⼀条分段线性的闭曲线。也就是说，多边形是由⼀系列⾸尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。
⼀个简单多边形将平⾯分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本⾝构成多边形的边界；⽽平⾯上其余的点构成了多边形的外部。
球头销这⾥给出凸多边形的定义：
当⼀个简单多边形及其内部构成⼀个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。与凸多边形对应的就是凹多边形。 通常，⽤多边形顶点的逆时针序列来表⽰⼀个凸多边形，即P={v0 ,v1 ,… ,v n-1}表⽰具有n条边v0v1，v1v2，… ,v n-1v n的⼀个凸多边形，其中，约定v0=v n。
若v i与v j是多边形上不相邻的两个顶点，则线段v i v j称为多边形的⼀条弦。弦将多边形分割成凸的两个⼦多边形{v i ,v i+1 ,… ,v j}和{v j ,v j+1 ,… ,v i}。多边形的三⾓剖分是⼀个将多边形分割成互不相交的三⾓形的弦的集合T。图1是⼀个凸多边形的两个不同的三⾓剖分。
图1 ⼀个凸多边形的2个不同的三⾓剖分
陶瓷保险丝在凸多边形P的⼀个三⾓剖分T中，各弦互不相交，且弦数已达到最⼤，即P的任⼀不在T中的弦必与T中某⼀弦相交。在⼀个有n个顶点的凸多边形的三⾓剖分中，恰好有n-3条弦和n-2个三⾓形。
凸多边形最优三⾓剖分的问题是：给定⼀个凸多边形P={v0 ,v1 ,… ,v n-1}以及定义在由多边形的边和弦组成的三⾓形上的权函数ω。要求确定该凸多边形的⼀个三⾓剖分，使得该三⾓剖分对应的权即剖分中诸三⾓形上的权之和为最⼩。
可以定义三⾓形上各种各样的权函数ω。例如：定义 ω(v i v j v k)=|v i v j|+|v i v k|+|v k v j|，其中，|v i v j|是点v i到v j的欧⽒距离。相应于此权函数的最优三⾓剖分即为最⼩弦长三⾓剖分。
⼆、算法思路
检查井井座1、三⾓剖分的结构及其相关问题
凸多边形的三⾓剖分与表达式的完全加括号⽅式之间具有⼗分紧密的联系。正如所看到过的，矩阵连乘积的最优计算次序问题等价于矩阵链的完全加括号⽅式。这些问题之间的相关性可从它们所对应的完全⼆叉树的同构性看出。 ⼀个表达式的完全加括号⽅式对应于⼀棵完全⼆叉树，⼈们称这棵⼆叉树为表达式的语法树。例如，与完全加括号的矩阵连乘积 ((A1(A2A3))(A4(A5A6)))相对应的语法树如图2(a)所⽰。
图2 表达式语法树与三⾓剖分的对应
语法树中每⼀个叶⼦表⽰表达式中⼀个原⼦。在语法树中，若⼀结点有⼀个表⽰表达式E1的左⼦树，以及⼀个表⽰表达式E r的右⼦树，则以该结点为根的⼦树表⽰表达式(E1E r)。因此，有n个原⼦的完全加括号表达式对应于惟⼀的⼀棵有n个叶结点的语法树，反之亦然。
凸多边形{v0 ,v1 ,… ,v n-1}的三⾓剖分也可以⽤语法树来表⽰。例如，图1(a)中凸多边形的三⾓剖分可⽤图2(b)所⽰的语法树来表⽰。该语法树的根结点为边v0v6，三⾓剖分中的弦组成其余的内部结点。多边形中除v0v6
边外的每⼀条边是语法树的⼀个叶结点。树根v0v6是三⾓形v0v3v6的⼀条边，该三⾓形将原多边形分为3个部分：三⾓形v0v3v6，凸多边形{v0 ,v1 ,… ,v3}和凸多边形{v3 ,v4 ,… ,v6}。三⾓形v0v3v6的另外两条边，即弦v3v6和v0v3为根的两个⼉⼦。以它们为根的⼦树分别表⽰凸多边形{v0 ,v1 ,… ,v3}和凸多边形{v3 ,v4 ,… ,v6}的三⾓剖分。
在⼀般情况下，⼀个凸n边形的三⾓剖分对应于⼀棵有n-1个叶⼦的语法树。反之，也可根据⼀棵有n-1个叶⼦的语法树产⽣相应的⼀个凸n 边形的三⾓剖分。也就是说，凸n边形的三⾓剖分与n-1个叶⼦的语法树之间存在⼀⼀对应关系。由于n个矩阵的完全加括号乘积与n个叶⼦的语法树之间存在⼀⼀对应关系，因此n个矩阵的完全加括号乘积也与凸(n+1)边形的三⾓剖分之间存在⼀⼀对应关系。图2的(a)和(b)表⽰出了这种对应关系，这时n=6。矩阵连乘积A1A2..A6中的每个矩阵A i对应于凸(n+1)边形中的⼀条边v i-1v i。三⾓剖分中的⼀条弦
v i v j，i<j，对应于矩阵连乘积A[i+1:j ]。
事实上，矩阵连乘积的最优计算次序问题是凸多边形最优三⾓剖分问题的⼀个特殊情形。 对于给定的
矩阵链A1A2..A n，定义⼀个与之相应的凸(n+1)边形P={v0 ,v1 ,… ,v n}，使得矩阵A i与凸多边形的边v i-1v i⼀⼀对应。若矩阵A i的维数为p i-1×p i,i=1,2,…,n，则定义三⾓形
v i v j v k上的权函数值为： ω(v i v j v k)=p i p j p k。依此权函数的定义，凸多边形P的最优三⾓剖分所对应的语法树给出矩阵链A1A2..A n的最优完全加括号⽅式。
2、最优⼦结构性质
凸多边形的最优三⾓剖分有最优⼦结构性质。
3、最优三⾓剖分的递归结构
4、计算最优值
public static void minWeightTriangulation(int n) {
for(int i = 1; i <= n; i++) {
t[i][i] = 0;
}
数据存储安全检测for(int r = 2; r <= n; r++) {//i与j的差值
for(int i = 1; i <= n - r + 1; i++) {
int j = i + r - 1;
m[i][j] = m[i + 1][j] + w(i-1,i,j);//k==i的情况
s[i][j] =i;
for(int k = i + 1; k < i+r-1; k++) {
int u = m[i][k] + m[k + 1][j] + w(i-1,k,j);
新风控制系统
if(u <m[i][j]) {
m[i][j] =u;
s[i][j] =k;
}
}
}
}
}
与最⼤矩阵连乘问题matrixChain⼀样，该算法占⽤O(n2)空间，耗时O(n3)。
5、构造最优三⾓剖分
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议