精华内容
下载资源
问答
  • \课件\算法设计\凸多边形的最优三角剖分\凸多边形的最优三角剖分
  • 凸多边形的最优三角剖分问题

    千次阅读 2012-02-24 15:34:42
    凸多边形的最优三角剖分问题 问题描述  多边形是平面上一条分段线性的闭曲线。也就是说,多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点...
    凸多边形的最优三角剖分问题

    问题描述

        多边形是平面上一条分段线性的闭曲线。也就是说,多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点,则称该多边形为简单多边形。一个简单多边形将平面分为3个部分:被包围在多边形内的所有点构成了多边形的内部;多边形本身构成多边形的边界;而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时,称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。

        通常,用多边形顶点的逆时针序列来表示一个凸多边形,即P=<v,v,… ,vn-1>表示具有n条边v0v1,v1v2,… ,vn-1vn的一个凸多边形,其中,约定v0=vn 。

        若vi与vj是多边形上不相邻的两个顶点,则线段vivj称为多边形的一条弦。弦 将多边形分割成凸的两个子多边形<v,vi+1 ,… ,vj>和<v,vj+1 ,… ,vi>。多边形的三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合T。图1是一个凸多边形的两个不同的三角剖分。

    (a) (b)

    图1 一个凸多边形的2个不同的三角剖分

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

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

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

    注意:解决此问题的算法必须适用于任意的权函数。

    参考解答

    用动态规划算法也能有效地求解凸多边形的最优三角剖分问题。尽管这是一个计算几何学问题,但在本质上,它与矩阵连乘积的最优计算次序问题极为相似。

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

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

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

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

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

        凸多边形<v,v,… ,vn-1>的三角剖分也可以用语法树来表示。例如,图3(a)中凸多边形的三角剖分可用图3(b)所示的语法树来表示。该语法树的根结点为边v0v6,三角剖分中的弦组成其余的内部结点。多边形中除v0v6边外的每一条边是语法树的一个叶结点。树根v0v6是三角形v0v3v6的一条边,该三角形将原多边形分为3个部分:三角形v0v3v6,凸多边形<v,v,… ,v3>和凸多边形<v,v,… ,v6>。三角形v0v3v6的另外两条边,即弦v3v6和v0v3为根的两个儿子。以它们为根的子树分别表示凸多边形<v,v,… ,v3>和凸多边形<v,v,… ,v6>的三角剖分。

        在一般情况下,一个凸n边形的三角剖分对应于一棵有n-1个叶子的语法树。反之,也可根据一棵有n-1个叶子的语法树产生相应的一个凸n边形的三角剖分。也就是说,凸n边形的三角剖分与n-1个叶子的语法树之间存在一一对应关系。由于n个矩阵的完全加括号乘积与n个叶子的语法树之间存在一一对应关系,因此n个矩阵的完全加括号乘积也与凸(n+1)边形的三角剖分之间存在一一对应关系。图3的(a)和(b)表示出了这种对应关系,这时n=6。矩阵连乘积A1A2..A6中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj,i<j-1,对应于矩阵连乘积Ai+1..j 。

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

    2.最优子结构性质

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

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

        首先,定义t[i,j],1≤i<j≤n,为凸子多边形<vi-1 ,v,… ,vj>的最优三角剖分所对应的权值,即最优值。为方便起见,设退化的多边形<Vi-1 ,vi>具有权值0。据此定义,要计算的凸(n+1)边多边形P对应的权的最优值为t[1,n]。

        t[i,j]的值可以利用最优子结构性质递归地计算。由于退化的2顶点多边形的权值为0,所以t[i,i]=0,i=1,2,…,n 。当j一i≥1时,子多边形<vi-1 ,v,… ,vj>至少有3个顶点。由最优于结构性质,t[i,j]的值应为t[i,k]的值加上t[k+1,j]的值,再加上△vi-1vkvj的权值,并在i≤k≤j-1的范围内取最小。由此,t[i,j]可递归地定义为:

    4.计算最优值

        将(2.3)式与矩阵连乘积的最优计算次序问题中计算m[i,j]的(2.l)式进行比较容易看出,除了权函数的定义外,两个递归式是完全一样的。因此只要对计算m[i,j]的算法MATRIX_CHAIN_ORDER做很小的修改就完全适用于计算t[i,j]。

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

    Procedure MINIMUM_WEIGHT_TRIANGULATION(P,w);
    begin
      n:=length[p]-1;
      for i:=1 to n do t[i,i]:=0;
        for ll:=2 to n do
          for i:=1 to n-ll+1 do
            begin
              j:=i+ll-1;
              t[i,j]:=∞;
              for k:=i to j-1 do
                begin
                  q:=t[i,k]+t[k+1,j]+ω(△vi-1vkvj);
                  if q<t[i,j] then
                    begin
                      t[i,j]:=q;
                      s[i,j]:=k;
                    end;
                end;
            end;
      return(t,s);
    end;

    MATRIX_CHAIN_ORDER一样,算法MINIMUM_WEIGHT_TRIANGULATION占用θ(n2)空间,耗时θ(n3)。

    5.构造最优三角剖分

    如我们所看到的,对于任意的1≤i≤j≤n ,算法MINIMUM_WEIGHT_TRIANGULATION在计算每一个子多边形<vi-1 ,v,… ,vj>的最优三角剖分所对应的权值t[i,j]的同时,还在s[i,j]中记录了此最优三角剖分中与边(或弦)vi-1vj构成的三角形的第三个顶点的位置。因此,利用最优子结构性质并借助于s[i,j],1≤i≤j≤n ,凸(n+l)边形P=<v,v,… ,vn>的最优三角剖分可容易地在Ο(n)时间内构造出来。

    展开全文
  • 1、问题相关定义:  (1)凸多边形的三角剖分:将凸多边形分割成互不...要求确定该凸多边形的三角剖分,使得该三角剖分中诸三角形上权之和为最小。  凸多边形三角剖分如下图所示:  2、最优子结构性质:  若

     1、问题相关定义:

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

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

         凸多边形三角剖分如下图所示:

              2、最优子结构性质

         若凸(n+1)边形P={V0,V1……Vn}的最优三角剖分T包含三角形V0VkVn,1<=k<=n-1,则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]。

         

    #include <stdio.h>
    #include <iostream>
    #include <fstream>
    #include <string.h>
    using namespace std;
    
    const int N = 7;//凸多边形边数+1,凸6边形{v0,,v1,...,v5}
    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-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];
    }




    展开全文
  • 凸多边形内部划分成若干三角形,每一条线都带权 哪一种划法,让三角形权最小? 因其具有最优子结构: 所以,总问题最优解=子问题最优解+ 一个三角形权 即 举例来说:当程序运行到i=0,j=5,k=3时: ...

    学习自https://www.jianshu.com/p/b97b0bb78b6c

     

    一.问题分析:

     

    将凸多边形内部划分成若干三角形,每一条线都带权 

    哪一种划法,让\sum三角形的权最小?

     

    因其具有最优子结构:

    所以,总问题的最优解=子问题的最优解+ \sum一个三角形的权

    举例来说:当程序运行到i=0,j=5,k=3时:

     

     

     

     

     

    设: 求解的是多边形{V0,V1,........Vn-1}

    bestWeight[ i ] [ j ] =m 表示它的一个子多边形{Vi , Vi+1 , ... , Vj-1 , Vj}的最优解=m  (所以最终解为bsetWeight[ 0 ][ n-1 ])

    bestPoint[ i ] [ j ] = k  表示该子多边形出现最优解时,构成的三角形为{ Vi , Vk , Vj }.

     

    当i==j时,子问题退化成了点 ; 当i+1=j时,子问题退化成了一条线.

    此时要退出,并且bestWeight[ i ] [ j ] =0;bestPoint[ i ] [ j ] = -1

     

    二.代码实现

    const int N = 6;
    
    vector<vector<int>> weight = {// 给出权函数。
            {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} };
    
    //记录最优权值
    vector<int>tempWeight(N, 0);
    vector<vector<int>>bestWeight(N, tempWeight); //bestWeight[i][j]=m表示多边形{Vi, ... , ... , ... , Vj}的最优解=m
    
    //记录最优策略
    vector<int>tempPoint(N,-1);
    vector<vector<int>> bestPoint(N, tempPoint);// bestPoing[i][j]=k 表示 Vi、Vj 构成三角形第三个顶点 Vk 。
    
    //计算三角权重之和
    int getWeight(int i, int k, int j)
    {
        return weight[i][k] + weight[i][j] + weight[k][j];
    }
    
    //自底而上的DP算法, (组合子问题的解->父问题的解)
    int TriSplit(int n)
    {
        //i==j时是点;  j = i + 1时是边,此时的bestWeight[i][j]=0
        //但无需赋值,数组已默认全为0
    
        for (int scale = 2; scale < n; scale++)//遍历2~N-1条边的多边形
        {
    		for (int i = 0; i < N - scale; i++)//例如,边数=2时,(V0,V1,V2)~(V3,V4,V5)
    		{
    			int j = i + scale;  //多边形的Vj
    			int k = i + 1;
    			bestWeight[i][j] = bestWeight[i][k] + bestWeight[k][j] + getWeight(i, k, j);//记录第一个基准值
    			bestPoint[i][j] = k;
    			for (k = i + 2; k < j; k++)//( i < k < j )
    			{
                    int t = bestWeight[i][k] + bestWeight[k][j] + getWeight(i, k, j);
                    if (t < bestWeight[i][j])
                    {
                        bestWeight[i][j] = t;
                        bestPoint[i][j] = k;
                    }
    			}
    		}
        }
        return bestWeight[0][N - 1];//返回整体{V0~VN-1}的最优解
    }
    
    void TSPrint(int i, int j)
    {
        if (j == i + 1 || j == i)
        {
            return;
        }
        TSPrint(i, bestPoint[i][j]);
        cout << "V" << i << " -- V" << bestPoint[i][j] << " -- V" << j << " = " << getWeight(i,bestPoint[i][j],j)<<endl;
    	TSPrint(bestPoint[i][j], j);
    }
    

     

    main()

    cout << endl << "最优三角剖分的权值之和为:" << TriSplit(N) << endl << endl;
    			cout << "剖分结果为:" << endl;
    			TSPrint(0, N - 1);

     

    三.几个疑惑 

    1.当规模=2时,需求解多边形{V0,V1,V2} , {V1,V2,V3} , {V2,V3,V4} , {V3,V4,V5},实际上是六边形的4/6个角

    但没有取{V4,V5,V0} , {V5,V0,V1}这剩下的2个角

    2.当规模变大时也是一样.不能取余吗?

     

    展开全文
  • 该题题意大致为:一个n个角的凸多边形,,用互不相交弦将其分为一个个三角形,每个三角形权值都是由三角形边和弦组成权值函数w,求解如何划分才能使所有角上权值和达到最小。根据动态规划算法主要...

    该题的题意大致为:一个n个角的凸多边形,,用互不相交的弦将其分为一个个的三角形,每个三角形的权值都是由三角形的边和弦组成权值函数w,求解如何划分才能使所有的角上的权值和达到最小。

    根据动态规划算法的主要思想,可以把整个问题分成几个子问题,把这些自问题经过处理后得到整个问题的解以及最优解。

    如图:

    4370439e1a57

    假设是一个n边形,有n个顶点,那么需要有n-3条弦将其分为n-2个三角形,从而权值最小。

    首先,对该多边形的角进行由0到n的排序其中v0=vn,,可以在多边形内加入弦使得该多边形被分成多个小的多边形,假设大的多边形用t[1][n]表示从角0到角n的权值之和(即最终结果),那么可以把问题分解为:在已经划分好的多边形内,取一个三角形,如上左的图形中取v3,v4,v6,可以保证的是:

    t[1][6]+t[5][3]+w(v3,v4,v6)=t[1][7],其中t[1][6],t[5][3]代表的也是经过规划好的多边形v0,v1,v2,v3,v6和多边形v6,v5,v4的最小权值;可以得出,入下推断:

    4370439e1a57

    而本问题,也可以用递归算法来进行推断。直到多边形是一个可以计算出权值的三角形为止,如此得到的结果,可以正确的得到最小整体权值。

    一下是C++的代码实现:

    //3d5 凸多边形最优三角剖分

    #include "stdafx.h"

    #include

    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

    {

    s[i] = new int[N];

    t[i] = new int[N];

    }

    cout<

    cout<

    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

    {

    //将链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] = 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<

    }

    int Weight(int a,int b,int c)

    {

    return weight[a][b] + weight[b][c] + weight[a][c];

    }

    展开全文
  • 【分析】经典的最优三角剖分,这题的权值函数是三角形中弦长的平方和,此题数据很弱最多只有5个顶点;如果有错,欢迎指正 我再来加两组数据,具体分析看代码注释 INPUT 6 0 0 0 1 1 2 3 2 4 1 ...
  • 参考书籍《算法设计与分析》 王晓东 动态规划 1.问题描述 (注:是所有的三角形的权值之和,不是.../*** @Author:胡家威* @CreateTime:2011-11-10 下午12:31:16* @Description:凸多边形的最优三角剖分*/packa...
  • 凸多边形最优三角剖分 ...若凸(n+1)边形P={V0,V1……Vn}的最优三角剖分T包含三角形V0VkVn,1<=k<=n,则T的权为三个部分权之和:三角形V0VkVn的权,多边形{V0,V1……Vk}的权和多边形{Vk,Vk+1……Vn}的权
  • 动态规划法解凸多边形最优三角剖分 2.实验内容 2.1 问题描述 (1)凸多边形的三角剖分:将凸多边形分割成互不相交的三角形的弦的集合T。 (2)最优剖分:给定凸多边形P,以及定义在由多边形的边和弦组成的三角形上的权...
  • 动态规划-凸多边形最优三角剖分

    热门讨论 2011-11-16 22:52:01
    问题描述:描述了凸多边形最优三角剖分的问题背景 使用C++,实现了凸多边形最优三角剖分,有足够注释 内含可执行程序
  • 问题描述 当一个简单的多边形及其内部构成一个闭凸集时,则称该简单多边形为一个凸多边形。...凸多边形最优三角剖分问题:给定凸多边形P={V0,V1,V2…Vn-1},以及定义在由凸多边形的边和弦组成的三...
  • 算法:凸多边形最优三角剖分

    千次阅读 2019-10-31 18:20:49
    1、问题相关定义: (1)凸多边形的三角剖分:将凸多边形分割成互不相交的三角形的弦的集合T。 (2)最优剖分:给定凸多边形P,以及定义在由多边形的边和弦... 若凸(n+1)边形P={V0,V1……Vn}的最优三角剖分T包含三角形...
  • 凸多边形最优三角剖分 相关定义 凸多边形的三角剖分:将凸多边形分割成互不相交的三角形的弦的集合T。 最优剖分:给定凸多边形P,以及定义在由多边形的边和弦组成的三角形上的权函数w,要求确定该凸多边形的三角剖分...
  • 凸多边形最优三角剖分-动态规划

    千次阅读 2015-09-20 11:06:59
    凸多边形最优分割是典型的动态规划问题 凸多边形最优剖分:给定凸多边形,以及定义在... 若凸(n+1)边形P={V0,V1……Vn}的最优三角剖分T包含三角形V0VkVn,10VkVn的权,多边形{V0,V1……Vk}的最优三角剖分权值和多边形{V
  • 使用了两种动态规划算法处理凸多边形最优三角剖分问题,算法1直观,算法2 简洁。
  • (1)凸多边形的三角剖分:将凸多边形分割成互不相交的三角形的弦的集合T。 (2)最优剖分:给定凸多边形P,以及定义在由多边形的边和弦组成的三角形上的权... 若凸(n+1)边形P={V0,V1……Vn}的最优三角剖分T包含三角形...
  • 【算法设计与分析】 凸多边形最优三角剖分(动态规划) 【问题描述】 使用动态规划算法解凸多边形最优三角剖分问题,具体来说就是,依据递归式,按照顺序求得子问题,使得该三角剖分中诸三角形上权之和为最小。 ...
  • 算法设计与实现 王晓东 题目描述: 用多边形顶点的逆时针序列表示凸多边形,即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。 ... 给定凸多边形P,以及... 若凸(n+1)边形P={v0,v1,…,vn-1}的最优三角剖分T包含三...
  • 凸多边形的最优三角剖分问题也是动态规划经典题目,此类问题基本上都是在一个给定的凸多边形上规划三角形分割,使得剖分后得到的一系列三角形的某种结果最优,比如三角形的面积之和最大(或最小),或者是三角形的...
  • 我的代码改了一下:dp[i][j]表示从i到j的最优三角剖分。 好像最优三角剖分和表达式树有关系。留坑。 #include <bits/stdc++.h> using namespace std; int w[10][10]; int dp[10][10]; int s[10][10]; int dfs...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 151
精华内容 60
关键字:

凸多边形的最优三角剖分