凸多边形的最优三角剖分

《凸多边形的最优三角剖分》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、凸多边形的最优三角剖分演讲人：问题相关定义分析两个要素问题相关描述分析动态规划步骤目录问题描述凸多边形最优三角剖分的问题是：给定一个凸多边形P={v0,v1,…,vn-1}以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。问题相关定义（1）凸多边形的三角剖分：将凸多边形分割成互不相交的弦的集合T。（2）最优剖分：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小。E

2、xample通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P={v0,v1,…,vn-1}表示具有n条边v0v1，v1v2，…,vn-1vn的一个凸多边形，其中，约定v0=vn。若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成凸的两个子多边形{vi,vi+1,…,vj}和{vj,vj+1,…,vi}。多边形的三角剖分是一个将多边形分割成互不相交的三角形的弦的集合T。图1是一个凸多边形的两个不同的三角剖分。图1一个凸多边形的两个不同的三角剖分性质：在凸多边形P的一个三角形部分T中，各弦互不相交，

3、且弦数已达到最大，即P的任一不在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角部分中，恰好有n-3条弦和n-2个三角形。分析两个基本要素最优子结构性质若凸(n+1)边形P={V0,V1……Vn}的最优三角剖分T包含三角形V0VkVn,1<=k<=n-1，则T的权为三个部分权之和：三角形V0VkVn的权，多边形{V0,V1……Vk}的权和多边形{Vk,Vk+1……Vn}的权之和。如下图所示：V0VnVkT可以断言，由T确定的这两个子多边形的三角剖分也是最优的。因为若有{V0,V1……Vk}和{Vk+1,……Vn}更小权的三角剖分

4、，将导致T不是最优三角剖分的矛盾（利用剪贴法）。因此，凸多边形的三角剖分问题具有最优子结构性质。分析两个基本要素递推结构设t[i][j],1<=i

5、进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率。子问题重叠1,51,12,51,23,51,34,5……..2,23,52,34,53,34,53,34,5凸多边形的三角剖分与矩阵链乘法完全加括号方式之间具有十分紧密的联系。正如所看到过的，矩阵连乘积的最优计算次序问题等价于矩阵链的完全加括号方式。这些问题之间的相关性可从它们

6、所对应的完全二叉树的同构性看出。一个表达式的完全加括号方式对应于一棵完全二叉树，人们称这棵二叉树为表达式的语法树。例如，与完全加括号的矩阵链乘积((A1(A2A3))(A4(A5A6)))相对应的语法树如图2(a)所示。(a)(b)图2表达式语法树与三角剖分的对应图1(a)中凸多边形的三角剖分可用图2(b)所示的语法树来表示。该语法树的根结点为边v0v6，三角剖分中的弦组成其余的内部结点。多边形中除v0v6边外的每一条边是语法树的一个叶结点。树根v0v6是三角形v0v3v6的一条边，该三角形将原多边形分为3个部分：三角形v0v3v6，凸多边

7、形{v0,v1,…,v3}和凸多边形{v3,v4,…,v6}。三角形v0v3v6的另外两条边，即弦v3v6和v0v3为根的两个儿子。以它们为根的子树分别表示凸多边形{v0,v1,…,v3}和凸多边形{v3,v4,…,v6}的三角剖分。A1A2A3A4A5v0v1v2v3v4v5A1A2A3A4A5循环程序IntMinWeightTriangulation(intn,int**t,int**s)  {for(inti=1; i<=n; i++)    {t[i][i] = 0;     }for(intr=2; r<=n; r++) //r为

8、当前计算的链长（子问题规模）{for(inti=1; i<=n-r+1; i++)//n-r+1为最后一个r链的前边界{intj = i+r-1;//计算前边界为r，链长为r的链