凸多边形最优三角剖分
问题描述

(1)凸多边形的三角剖分：将凸多边形分割成互不相交的三角形的弦的集合T。

(2)最优剖分：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小。

最优子结构性质：

若凸(n+1)边形P={V0,V1……Vn}的最优三角剖分T包含三角形V0VkVn,1<=k<=n，则T的权为三个部分权之和：三角形V0VkVn的权，多边形{V0,V1……Vk}的权和多边形{Vk,Vk+1……Vn}的权之和。如下图所示：



可以断言，由T确定的这两个子多边形的三角剖分也是最优的。因为若有{V0,V1……Vk}和{V0,V1……Vk}更小权的三角剖分，将导致T不是最优三角剖分的矛盾。因此，凸多边形的三角剖分问题具有最优子结构性质。

递推关系：

设t[i][j],1<=i<j<=n为凸多边形{Vi-1,Vi……Vj}的最优三角剖分所对应的权值函数值，即其最优值。最优剖分包含三角形Vi-1VkVj的权，子多边形{Vi-1,Vi……Vk}的权，子多边形{Vk，Vk+1……Vj}的权之和






       因此，可得递推关系式：

问题描述
当一个简单的多边形及其内部构成一个闭凸集时，则称该简单多边形为一个凸多边形。即凸多边形边界上或内部任意两点所连成的直线上所有的点都在多边形内部或边界上。通常用顶点的逆时针序列来表示凸多边形，即P={V0,V1,V2…Vn-1},表示有n条边的凸多边形，如图我们约定V0=Vn：

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


分析最优子结构
多边形的最优三角剖分问题有最优子结构性质。事实上，若凸n+1 边形P={V0, V1, …Vn}的最优三角剖分T包含三角形V0VkVn (1≤k≤n-I)，则T的权为三角形V0VkVn的权、子多边形{V0, V1, … Vk}和{Vk, Vk+1, … Vn}的权之和。可以断言，由T确定的这两个子多边形的三角剖分也是最优的。因为若有{V0, V1, … Vk}或{Vk, Vk+1,… Vn}的更小权的三角剖分，将导致T不是最优三角剖分的矛盾。

这个结构和矩阵连乘问题一致：矩阵连乘

最优三角剖分的递归结构
首先我们定义t[i][j]（1<=i<j<=n）为凸k-i+2边形P={Vi-1,Vi,…Vj}三角剖分最优权值。为了方便处理，我们预处理Vi-1Vi=0,也就是说t[i][i]=0，由这个定义我们可以发现我们整个凸多边形的最优权值为t[1][n]，在从P={Vi-1,Vi,.....Vj}中选取一个顶点k作为剖分（i<=k<=j-1）,一共有j-i种取法，我们要从当中选取最优的一种剖分：



所以递推关系式可以描述如下：


动态规划实现
const int maxn=105;//顶点个数
int t[maxn][maxn];
void dpTriangle(int n,int t[][maxn],int s[][maxn])
{
    for(int i=0;i<n;i++) t[i][i]=0;//预处理
    for(int r=2;r<=n;r++)//r条边
    {
        for(int i=1;i<=n-r+1;i++)
        {
            int j=i+r-1;
            t[i][j]=t[i+1][j]+w(i-1,i,j);
            s[i][j]=i;//初始化为第一个值
            for(int k=i+1;k<j;k++)//在[i+1,i+r-1)区间内选择一个k点
            {
                int u=t[i][k]+t[k+1][j]+w(i-1,k,j);
                if(u<t[i][j])
                {
                    t[i][j]=u;
                    s[i][j]=k;
                }
            }
        }
    }
}

时间复杂度O(n^3)

空间复杂度O(n^2)

1.实验目的
动态规划法解凸多边形最优三角剖分
2.实验内容
2.1 问题描述
(1)凸多边形的三角剖分：将凸多边形分割成互不相交的三角形的弦的集合T。

(2)最优剖分：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小。
2.2 问题分析

前置知识

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

1.找出最优解的性质：满足三角形弦值和最小

2.递归地定义最优值：解该多边形的最优三角划分时，会包含多个子三角形划分，子三角形中面积重叠的部分，需要计算该部分划分三角形后的权值，选取最优值。反复调用，直到多边形是一个可以计算出权值的三角形为止。

3.自底向上，计算最优值：计算出一个三角形的最优值后，根据最优子结构，步步最优解，根据递归性质，可求得该问题的最优解。

3.实验过程及结果
3.1 数据输入
#定义一个顶点到其他顶点的权
weights=[[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]]

weights是一个邻接矩阵，
3.2 实验代码

求权值之和

#定义求三角形权之和的函数
def get_weight(i,j,k):
    weights = [[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]]
    if k<n:
        return weights[i][j]+weights[j][k]+weights[k][i]


计算最优决策

def desicion(n,m,s):
    for i in range(1,n):
        m[i][i]=0
        s[i][i]=0
        for r in range(2,n):
            for i in range(1,n-r+1):
                j=i+r-1
                m[i][j]=m[i+1][j]+get_weight(i-1,i,j)
                s[i][j]=i
            for k in range(i+1,j):
                t=m[i][k]+m[k+1][j]+get_weight(i-1,k,j)
                if t<m[i][j]:
                    m[i][j]=t
                    s[i][j]=k
    return m,s



自底向上求取最优值

def MAX(i,j,s):
    if i==j:
        return
        MAX(i, int(s[i][j]), s)
        MAX(int(s[i][j] + 1), j, s)
        print('v'+str(i-1)+',v'+str(j)+',v'+str(s[i][j]))
    print('最优三角剖分：'+str(m[1][n-1]))

3.3 实验结果

凸多边形最优三角剖分
相关定义

凸多边形的三角剖分：将凸多边形分割成互不相交的三角形的弦的集合T。
最优剖分：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w,要求确定该凸多边形的三角剖分，使三角剖分中诸三角形上权之和为最小。



（摘自：https://blog.csdn.net/pi9nc/article/details/9750091）

优化子结构
P=（v0,v1,v2,v3…vn）是n+1个顶点的凸多边形
Tp是P的优化三角剖分，包含三角形v0vkvn




递归关系的确定：


重叠子问题


代码见博客：连接