动态规划：凸多边形最优三角剖分（文末附有手写版例题）_凸多边形最优三角剖分动态规划伪代码

一、问题描述

多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。

一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。

这里给出凸多边形的定义：

当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。与凸多边形对应的就是凹多边形。

通常，用多边形顶点的逆时针序列来表示一个凸多边形，即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 一个凸多边形的2个不同的三角剖分

在凸多边形P的一个三角剖分T中，各弦互不相交，且弦数已达到最大，即P的任一不在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角剖分中，恰好有n-3条弦和n-2个三角形。

凸多边形最优三角剖分的问题是：给定一个凸多边形P={v0 ,v1 ,… ,vn-1}以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。

可以定义三角形上各种各样的权函数ω。例如：定义  ω(vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。

二、算法思路

1、三角剖分的结构及其相关问题

凸多边形的三角剖分与表达式的完全加括号方式之间具有十分紧密的联系。正如所看到过的，矩阵连乘积的最优计算次序问题等价于矩阵链的完全加括号方式。这些问题之间的相关性可从它们所对应的完全二叉树的同构性看出。

一个表达式的完全加括号方式对应于一棵完全二叉树，人们称这棵二叉树为表达式的语法树。例如，与完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))相对应的语法树如图2(a)所示。

图2    表达式语法树与三角剖分的对应

语法树中每一个叶子表示表达式中一个原子。在语法树中，若一结点有一个表示表达式E1的左子树，以及一个表示表达式Er的右子树，则以该结点为根的子树表示表达式(E1Er)。因此，有n个原子的完全加括号表达式对应于惟一的一棵有n个叶结点的语法树，反之亦然。

凸多边形{v0 ,v1 ,… ,vn-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中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，i<j，对应于矩阵连乘积A[i+1:j ]。

事实上，矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的一个特殊情形。 对于给定的矩阵链A1A2..An，定义一个与之相应的凸(n+1)边形P={v0 ,v1 ,… ,vn}，使得矩阵Ai与凸多边形的边vi-1vi一一对应。若矩阵Ai的维数为pi-1×pi,i=1,2,…,n，则定义三角形vivjvk上的权函数值为： ω(vivjvk)=pipjpk。依此权函数的定义，凸多边形P的最优三角剖分所对应的语法树给出矩阵链A1A2..An的最优完全加括号方式。

2、最优子结构性质

凸多边形的最优三角剖分有最优子结构性质。

3、最优三角剖分的递归结构

4、计算最优值

与最大矩阵连乘问题matrixChain一样，该算法占用O(n2)空间，耗时O(n3)。

5、构造最优三角剖分

6、代码

	凸多边形最优三角剖分  
    #include <stdio.h>
    #include <iostream>   
    using namespace std;   
    
    const int N = 7;//凸多边形边数+1  
    int weight[][N] = {{0,2,3,1,5,6},{2,0,3,4,8,6},{3,3,0,10,13,7},{1,4,10,0,12,5},{5,8,13,12,0,3},{6,6,7,5,3,0}};//凸多边形的权  
      
    int MinWeightTriangulation(int n,int **t,int **s);
    void Traceback(int i,int j,int **s);//构造最优解 
    int Weight(int a,int b,int c);//权函数  
      
    int main()  
    {  
        int **s = new int *[N];    
        int **t = new int *[N];    
        for(int i=0;i<N;i++)      
        {      
            s[i] = new int[N];    
            t[i] = new int[N];    
        }   
      
        cout<<"此多边形的最优三角剖分值为："<<MinWeightTriangulation(N-1,t,s)<<endl;    
        cout<<"最优三角剖分结构为："<<endl;    
        Traceback(1,5,s); //s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置  
      
        return 0;  
    }  
      
    int MinWeightTriangulation(int n,int **t,int **s)  
    {  
        for(int i=1; i<=n; i++)  
        {  
            t[i][i] = 0;  
        }  
        for(int r=2; r<=n; r++) //r为当前计算的链长（子问题规模）    
        {  
            for(int i=1; i<=n-r+1; i++)//n-r+1为最后一个r链的前边界    
            {  
                int j = i+r-1;//计算前边界为r，链长为r的链的后边界    
      
                t[i][j] = t[i+1][j] + Weight(i-1,i,j);//将链ij划分为A(i) * ( A[i+1:j] )这里实际上就是k=i  
      
                s[i][j] = i;  
      
                for(int k=i+1; k<j; k++)  
                {  
                    //将链ij划分为( A[i:k] )* (A[k+1:j])     
                    int u = t[i][k] + t[k+1][j] + Weight(i-1,k,j);  
                    if(u<t[i][j])  
                    {  
                        t[i][j] = u;  
                        s[i][j] = k;  
                    }  
                }  
            }  
        }  
        return t[1][N-2];  
    }  
      
    void Traceback(int i,int j,int **s)  
    {  
        if(i==j) return;  
        Traceback(i,s[i][j],s);  
        Traceback(s[i][j]+1,j,s);  
        cout<<"三角剖分顶点：V"<<i-1<<",V"<<j<<",V"<<s[i][j]<<endl;  
    }  
      
    int Weight(int a,int b,int c)  
    {  
         return weight[a][b] + weight[b][c] + weight[a][c];  
    }  

7、例题

求下图的最优三角剖分