精华内容
下载资源
问答
  • 凸多边形最优三角形剖分
    千次阅读
    2020-04-13 23:38:31

    问题描述

    当一个简单的多边形及其内部构成一个闭凸集时,则称该简单多边形为一个凸多边形。即凸多边形边界上或内部任意两点所连成的直线上所有的点都在多边形内部或边界上。通常用顶点的逆时针序列来表示凸多边形,即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.实验目的 3.实验原理 4.实验设计 ...(包括输入格式、算法、输出格式) ...(除了截图外,实验结果还用图表进行了分析) ...
  • 计算机算法设计与分析 凸多边形最优三角剖分
  • 算法:凸多边形最优三角剖分

    千次阅读 多人点赞 2019-10-31 18:20:49
    1、问题相关定义: (1)凸多边形的三角剖分:将凸多边形分割成互不相交的三角形的弦的集合T。 (2)最优剖分:给定凸多边形P,以及定义在由多边形的边和弦... 若(n+1)边形P={V0,V1……Vn}的最优三角剖分T包含三角形...

    1、问题相关定义:

     (1)凸多边形的三角剖分:将凸多边形分割成互不相交的三角形的弦的集合T。
    
    (2)最优剖分:给定凸多边形P,以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分,使得该三角剖分中诸三角形上权之和为最小。
    
     凸多边形三角剖分如下图所示:
    

    在这里插入图片描述

          2、最优子结构性质:
    
     若凸(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不是最优三角剖分的矛盾。因此,凸多边形的三角剖分问题具有最优子结构性质。
    
         3、递推关系:
    
     设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]。
    

    在这里插入图片描述
    在这里插入图片描述
    详细解析:
    (1)什么是凸多边形?

    如下图所示,是一个凸多边形
    在这里插入图片描述

    如下图所示,不是一个凸多边,因为v1v3连线落在了多边形的外部

    在这里插入图片描述

    凸多边形不相邻的两个顶点的连线称为凸多边形的弦

    (2)什么是凸多边形的三角剖分?

    凸多边形的三角剖分是指将一个凸多边形分割成互不相交的三角形的弦的集合。如下图所示,都是三角形的剖分,三角形的剖分有很多种:

    在这里插入图片描述

    如果我们在给定凸多边形及定义在边,弦上的权值,即任意两点之间定义一个数值作为i权值,如图所示:
    在这里插入图片描述

    三角形上权值之和是指三角形的3条边上的权值之和:

    w(vi vk vj)=|vi vk| + |vk vj | + |vi vj|

    如图所示,w(v0v1v4)=|v0v1| + |v1v4| + |v0v4| = 22+8+5=15.

    (3)什么是凸多边形最优三角剖分?

    一个凸多边形的三角剖分有很多种,最优三角剖分就是划分的各三角形上权函数之和最小的三角剖分。

    在这里插入图片描述

     凸多边形最优三角剖分满足动态规划的最优子结构性质,可以从自底向上逐渐推出整体的最优。
    
    (1)确定合适的数据结构
    
    采用二维数组weight[ ][ ]记录各个顶点之间的连接权值,二维数组t[ ][ ]存放各个子问题的最优值,二维数组s[ ][ ]存放各个子问题的最优策略。
    
    (2)初始化
    
    输入顶点数n,然后依次输入各个顶点之间的连接权值存储在二维数组weight[ ][ ]中,令n=n-1(顶点标号从v0开始),
    
    t[i][i]=0,s[i][i]=0,其中i=1,2,3,4……,n-1。
    
    (3)循环
    
    按照递归关系式计算3个顶点{v i-1,vi,vi+1}的最优三角剖分,j=i+1,将最优值存入t[i][j],同时将最优策略存入s[i][j],i=1,2,3,……,n-1。
    按照递归关系式计算4个顶点{v i-1,vi,vi+1,vi+2}的最优三角剖分,j=i+2,将最优值存入t[i][j],同时将最优策略存入s[i][j],i=1,2,3,……,n-2。
    以此类推,直到求出所有顶点{v0,v1,v2,……,vn}的最优三角剖分,并将最优值存入t[1][n],将最优策略记入s[1][n]
    (4)构造最优解
    
    根据最优决策信息数组s[ ][ ]递归构造最优解,即输出凸多边形的最优剖分的所有弦。s[1][n],表示凸多边形最优三角剖分位置。
    
    如果子问题1为空,即没有一个顶点,说明V0Vs[1][n]是一条边,不是弦,不需要输出,否则,输出该弦V0Vs[1][n]
    如果子问题2为空,即没有一个顶点,说明Vs[1][n]Vn是一条边,不是弦,不需要输出,否则,输出该弦Vs[1][n]Vn
    递归构造两个子问题{ v0,v1,v2,……,Vs[1][n] }{ Vs[1][n] ,v1,v2,……,vn },一直递归到子问题为空停止。
    

    在这里插入图片描述
    源代码:

    #include<bits/stdc++.h>
    using namespace std;
     
    const int M =1111;
    int n; //顶点数
    int s[M][M];//记录最优策略二维数组
    double t[M][M];//记录最优值二维数组
    double weight[M][M];//记录各顶点之间权值的二维数组
     
    void MinWeightTriangulation()
    {
        for (int i=1;i<=n;i++) //初始化
        {
            t[i][i]=0;
            s[i][i]=0;
        }
        for(int r=2;r<=n;r++)//r为问题规模,r=2实际上有三个点 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]+weight[i][j]+weight[i-1][j];//将链ij划分为A(i) * ( A[i+1:j] )这里实际上就是k=i
                //策略为k=i的情况
                s[i][j]=i;
                for (int k=i+1;k<j;k++) //枚举划分点i到j所有情况
                {
                	//将链ij划分为( A[i:k] )* (A[k+1:j])
                    double u=t[i][k]+t[k+1][j]+weight[i-1][k]+weight[k][j]+weight[i-1][j];
                    if(t[i][j]>u)
                    {
                        t[i][j]=u;
                        s[i][j]=k;
                    }
                }
            }
        }
    }
     
    void Traceback(int i,int j)  //递归求解所有子问题的弦。
    {
        if(i==j)
            return ;
        Traceback(i,s[i][j]);
        Traceback(s[i][j]+1,j);
        cout<<"三角剖分顶点:V"<<i-1<<",V"<<j<<",V"<<s[i][j]<<endl;
    }
     
    int main()
    {
        int i;
        int j;
        cout << "请输入顶点个数n:"<< endl;
        cin >> n;
        n--;
        cout << "请依次输入各顶点的连接权值:" << endl;
        for (i=0;i<=n;++i)
        {
            for (j=0;j<=n;++j)
            {
                cin >> weight[i][j];
            }
        }
        MinWeightTriangulation();
        cout << "最优三角剖分的权值和是:" << endl;
        cout << t[1][n]<< endl;
        cout << "三角剖分顶点:"<< endl;
        Traceback(1,n);
        return 0;
    }
    

    在这里插入图片描述
    在这里插入图片描述
    运行效果1:
    在这里插入图片描述
    运行效果2:在这里插入图片描述

    展开全文
  • 一.题目描述 通常,用多边形顶点的序列来表示一个凸多边形,即P=<v0 ,v1 ,… ,vn-1>...多边形三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合T。 如上图为一个凸多边形的两个不同

    一.题目描述

    通常,用多边形顶点的序列来表示一个凸多边形,即P=<v0 ,v1 ,… ,vn-1>表示具有n条边v0v1,v1v2,… ,vn-1vn的一个凸多边形,其中,约定v0 = vn 。
    若vi与vj是多边形上不相邻的两个顶点,则线段vivj称为多边形的一条弦。弦将多边形分割成凸的两个子多边形<vi ,vi+1 ,… ,vj>和<vj ,vj+1 ,… ,vi>。多边形的三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合T
    在这里插入图片描述
    在这里插入图片描述

    如上图为一个凸多边形的两个不同的三角剖分.n在凸多边形P的一个三角剖分T中,各弦互不相交且弦数已达到最大,即P的任一不在T中的弦必与T中某一弦相交。

    有n个顶点的凸多边形的三角剖分中,恰好有n-3条弦和n-2个三角形。
    凸多边形最优三角剖分的问题是:给定一个凸多边形P=<v0,v1,… ,vn-1>以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分,使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小!

    可以定义三角形上各种各样的权函数W。例如:定义 ω(△vivjvk) = |vivj| + |vivk| + |vkvj|,其中,|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。
    注意:解决此问题的算法必须适用于任意的权函数。

    二.解题思路

    这是计算几何学问题,但在本质上与矩阵连乘积的最优计算次序问题极为相似。可用动态规划算法。

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

    凸多边形的三角剖分与表达式的完全加括号方式之间具有十分紧密的联系。正如矩阵连乘积的最优计算次序问题等价于矩阵链的完全加括号方式.这些问题之间的相关性可从它们所对应的完全二叉树的同构性看出。所谓完全二叉树是指叶结点以外的所有结点的度数都为2的二叉树。

    一个表达式的完全加括号方式对应于一棵完全二叉树,这棵二叉树叫作表达式的语法树。
    例:与完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))对应的语法树如图(a)。
    在这里插入图片描述

    叶结点:表达式中一个原子。在语法树中,表达式(ELEr)对应一棵子树,其左子树表示表达式EL,其右子树表示表达式ER。有n个原子的完全加括号表达式与一棵有n个叶结点的语法树一一对应。

    凸多边形<v0 ,v1 ,… ,vn-1>的三角剖分也可以用语法树来表示。例如,图3(a)中凸多边形的三角剖分可用图(b)所示的语法树来表示。该语法树的根结点为边v0v6,三角剖分中的弦组成其余的内部结点。

    除v0v6以外的边是叶结点。树根v0v6是三角形v0v3v6的一条边,该三角形将原多边形分为3个部分:一个三角形,两个凸多边形.
    三角形v0v3v6的另外两条边,即弦v3v6和v0v3为根的两个儿子。以它们为根的子树分别表示凸多边形<v0 ,v1 ,… ,v3>和凸多边形<v3 ,v4 ,… ,v6>的三角剖分
    在这里插入图片描述

    一个凸n边形的三角剖分与n-1个叶子的语法树一一对应。由于n个矩阵的完全加括号乘积与n个叶子的语法树之间存在一一对应关系,因此n个矩阵的完全加括号乘积也与凸(n+1)边形的三角剖分之间存在一一对应关系。上图中(a)和(b)表示出了这种对应关系,这时n=6。矩阵连乘积A1A2…A6中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj,i<j-1,对应于矩阵连乘积Ai+1…j 。

    n矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的一个特殊情形。

    对于给定的矩阵链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.最优子结构性质

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

    若凸(n+1)边形P=<v0 ,v1 ,… ,vn>的一个最优三角剖分T包含三角形v0vkvn , 1≤k≤n-1,则T的权为3个部分权的和,即三角形v0vkvn的权,子多边形<v0 ,v1 ,… ,vk>的权和<vk ,vk+1 ,… ,vn>的权之和。由T所确定的这两个子多边形的三角剖分也是最优的,因为若有<v0 ,v1 ,… ,vk>或<vk ,vk+1 ,… ,vn>的更小权的三角剖分,将会导致T不是最优三角剖分的矛盾。

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

    定义t[i,j],1≤i<j≤n,为凸子多边形<vi-1 ,vi ,… ,vj>的最优三角剖分所对应的权值,即最优值。
    设退化的多边形<Vi-1 ,vi>权值为0,那么凸(n+1)边形对应的权的最优值为t[1,n]。
    t[i,j]的值可以利用最优子结构性质递归地计算。由于退化的2顶点多边形的权值为0,所以t[i,i]=0,i=1,2,…,n 。当j-i≥1时,子多边形<vi-1 ,vi ,… ,vj>至少有3个顶点。

    由最优子结构性质,t[i,j]的值应为t[i,k]的值加上t[k+1,j]的值,再加上△vi-1vkvj的权值,并在i≤k≤j-1的范围内取最小。由此,t[i,j]可递归地定义为:
    在这里插入图片描述

    4.计算最优值

    上式与矩阵连乘积的最优计算次序问题中计算m[i,j]的公式(P40)几乎完全一样(除了权函数的定义外),因此,对计算m[i,j]的算法Matrix_Chain略做修改就可用于计算t[i,j]。

    计算凸(n+1)边形P=<v0 ,v1 ,… ,vn>的三角剖分最优权值的动态规划算法,输入是凸多边形P=<v0 ,v1 ,… ,vn>的权函数ω,输出是最优值t[i,j]和使得t[i,k]+t[k+1,j]+ω(△vi-1vkvj)达到最优的位置(k=)s[i,j],1≤i≤j≤n 。

    5.构造最优三角剖分

    对于任意的1≤i≤j≤n ,上述算法在计算每一个子多边形<vi-1 ,vi ,… ,vj>的最优三角剖分所对应的权值t[i,j]的同时,还在s[i,j]中记录了此最优三角剖分中与边(或弦)vi-1vj构成的三角形的第三个顶点的位置。

    因此,利用最优子结构性质并借助于s[i,j],1≤i≤j≤n ,凸(n+l)边形P=<v0 ,v1 ,… ,vn>的最优三角剖分可容易地在Ο(n)时间内构造出来

    代码如下:

    // 凸多边形最优三角剖分
    // 与矩阵连乘一样的思路。矩阵连乘的最优计算次序问题是凸多边形最优三角剖分问题的特殊情形
    #include<bits/stdc++.h>
    using namespace std;
    
    const int N = 7; //凸多边形边数+1
    int weight[][N] = {{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}};//凸多边形的权
    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构成三角形的第三个顶点的位置
        system("pause");
        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)
            {
                int j = i+r-1;
                t[i][j] = t[i+1][j] + Weight(i-1, i, j);
                s[i][j] = i;
                for(int k=i+1; k<i+r-1; k++)
                {
                    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];
    }
    

    运行结果:

    本篇文章参考我的老师毕方明《算法设计与分析》课件.
    欢迎大家访问我的个人博客 — 乔治的编程小屋,和我一起为大厂offer努力吧!

    展开全文
  • 动态规划-凸多边形最优三角剖分

    热门讨论 2011-11-16 22:52:01
    问题描述:描述了凸多边形最优三角剖分的问题背景 使用C++,实现了凸多边形最优三角剖分,有足够的注释 内含可执行程序
  • 一、问题描述多边形是平面上一条分段线性的闭曲线。也就是说,多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了...

    一、问题描述

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

    一个简单多边形将平面分为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是一个凸多边形的两个不同的三角剖分。

    de18645ff2b4150742106a8caba53948.png

    图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)所示。

    76d6bb5d8b790a24f317b19b342f684c.png

    图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

    事实上,矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的一个特殊情形。 对于给定的矩阵链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、最优子结构性质

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

    ed8f7d945d9d48337c200529fabb49a5.png

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

    de78ac3ec0e32b701a155dabc092ce7f.png

    d4a9306a30c296c3b7b60c56b3ce6489.png

    4、计算最优值

    a5a1b26d5833b1cdf69b51dc08e12a54.png

    public static void minWeightTriangulation(intn) {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]=u;

    s[i][j]=k;

    }

    }

    }

    }

    }

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

    5、构造最优三角剖分

    b8206ad0dec014f0a7b0cc867ff1763c.png

    展开全文
  • 凸多边形最优三角剖分(C语言编写) 算法
  • 选定基准点a,自底向上计算子多边形内的最优解。 1、 初始化,当只有一个点时,即i=j: t[a][a]=0; 2、 两个点:a,a+1时,不计算; 3、 三个点开始计算,k=a,多边形a-1,a,a+1的解: 当前多边形的最优解即为...
  • 【算法设计与分析】 凸多边形最优三角剖分(动态规划) 【问题描述】 使用动态规划算法解凸多边形最优三角剖分问题,具体来说就是,依据递归式,按照顺序求得子问题,使得该三角剖分中诸三角形上权之和为最小。 ...
  • 一:题目: 给定n边凸多边形P,要求确定该凸多边形的三角剖分(将多边形分割成n-2个三角形),使得该三角剖分中诸三角形上权之和为最小。...最优三角剖分中诸三角形上权值和。 输入样例: 6 0 2 2 3 1 4 0 1 5 2 3 0 2
  • 1.问题分析 我们可以把披萨饼看作是一个凸多边形凸多边形是指多边形的任意两点的连线均落在多边形的内部或边界上。 (1)什么是凸多边形?...凸多边形三角剖分是指将一个凸多边形分割成互不相交的三角形...
  • 实现第五版,王晓东编著的第三章3.5凸多边形最优三角剖分问题的代码。课本62页。 #include #include int x[50],y[50]; using namespace std; double w(int i,int k,int j); void MinWeightTriangulation(int n,int *...
  • 凸多边形上的最优三角剖分问题也是动态规划经典题目,此类问题基本上都是在一个给定的凸多边形上规划三角形分割,使得剖分后得到的一系列三角形的某种结果最优,比如三角形的面积之和最大(或最小),或者是三角形的...
  • 【问题描述】使用动态规划算法解凸多边形最优三角剖分问题,具体来说就是,依据递归式,按照顺序求得子问题,使得该三角剖分中诸三角形上权之和为最小。 【输入形式】在屏幕上输入多边形顶点个数和顶点坐标。 ...
  • 动态规划法解凸多边形最优三角剖分 2.实验内容 2.1 问题描述 (1)多边形的三角剖分:将多边形分割成互不相交的三角形的弦的集合T。 (2)最优剖分:给定多边形P,以及定义在由多边形的边和弦组成的三角形上的权...
  • #include<stdio.h> #include<stdlib.h> #include<math.h> int **s;...void back(int a, int c) { if (a == c - 1) return ;... printf("选择的三角形为%d-%d-%d\n", a, s[a][c], c);...
  • 凸多边形最优三角剖分 相关定义 多边形的三角剖分:将多边形分割成互不相交的三角形的弦的集合T。 最优剖分:给定多边形P,以及定义在由多边形的边和弦组成的三角形上的权函数w,要求确定该多边形的三角剖分...
  • 动态规划-凸多边形最优三角形剖分

    千次阅读 2020-04-17 00:02:59
    凸多边形最优三角剖分问题:给定多边形P={V0,VI, … Vn},以及定义在由多边形的边和弦组成的三角形上的权函数w,要求确定该多边形的三角剖分,使得该三角剖分所对应的权,即三角剖分中诸三角形上权之和为最小。...
  • 一、动态规划  和分治法类似,把原问题划分成若干个子问题,不同的是,分治法(子问题间互相独立),动态规划(子问题不独立) ...二、凸多边形最优三角剖分 三角剖分将多边形分割成互不想交的...
  • "最优三角: V%d V%d V%d.\n" , a - 1 , p [ a ] [ b ] , b ) ; } int main ( ) { int n ; scanf ( "%d" , & n ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j...
  • —【动态规划】凸多边形最优三角剖分
  • 这是一个凸多边形。对于这个凸多边形,我们可以将弦连接,将其分为多个三角形。 那么问题来了,怎么做才能使这些三角形的权值之和最小呢? 在这里,权值可以是任何和弦长,边长有关的权函数,一般来说,我们使用...
  • 就是把一个n边凸多边形划分成全都化成三角形(n-2),然后算所有三角形的周长加起来总的最小的(公共弦得重复计算)。 (2)基本思路 最小的大凸多边形等于 “左子多边形的最小” + “右子多边形的最小” + “中间的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,786
精华内容 714
关键字:

凸多边形最优三角剖分

友情链接: zice.zip