凸多边形最优三角剖分

 

具体的细节讲解，我就不多说啦。网上很多资料，而且讲的非常详细。下面我贴下我做的，虽然大概思路懂了，但是去实现的时候，还是遇到了很多问题。主要是没有正确的理清思路。写下来记录一下。。

 

 

<span style="font-size:18px">#include<iostream>  
using namespace std;  
  
#define MAX 1024  
int min[MAX][MAX];//m[i][j]节点i开始的连续j个节点的最小值  
int s[MAX][MAX];//记录需连接的弦  
int dis[MAX][MAX];//一对节点的权值  
  
int weight(int i,int j,int k)//得到任意三个节点的总权值  
{  
    return dis[i][j]+dis[i][k]+dis[j][k];  
}  
  
void printThePath(int i,int j)  
{  
    int k=s[i][j];  
    if(!k)  
        return;  
    cout<<i<<" "<<i+j-1<<" "<<s[i][j]<<endl;  
    printThePath(i,k-i+1);  
    printThePath(k,i+j-k);  
}  
void main()  
{  
    //可以自己输入  
    int N=6;  
    dis[1][1]=0;  
    dis[1][2]=2;  
    dis[1][3]=2;  
    dis[1][4]=3;  
    dis[1][5]=1;  
    dis[1][6]=4;  
  
    dis[2][1]=2;  
    dis[2][2]=0;  
    dis[2][3]=1;  
    dis[2][4]=5;  
    dis[2][5]=2;  
    dis[2][6]=3;  
  
    dis[3][1]=2;  
    dis[3][2]=1;  
    dis[3][3]=0;  
    dis[3][4]=2;  
    dis[3][5]=1;  
    dis[3][6]=4;  
  
    dis[4][1]=3;  
    dis[4][2]=5;  
    dis[4][3]=2;  
    dis[4][4]=0;  
    dis[4][5]=6;  
    dis[4][6]=2;  
  
    dis[5][1]=1;  
    dis[5][2]=2;  
    dis[5][3]=1;  
    dis[5][4]=6;  
    dis[5][5]=0;  
    dis[5][6]=1;  
  
    dis[6][1]=4;  
    dis[6][2]=3;  
    dis[6][3]=4;  
    dis[6][4]=2;  
    dis[6][5]=1;  
    dis[6][6]=0;  
    int i,j;  
    for(i=1;i<=N;i++)  
    {  
        for(j=1;j<=N;j++)  
        {  
              
            if(j<3)  
                min[i][j]=0;  
            else  
                min[i][j]=MAX;  
        }  
    }  
    /* 
    cout<<"输入多边形点的个数:"; 
    cin>>N; 
    int i,j; 
    for(i=1;i<=N;i++) 
    { 
        for(j=1;j<=N;j++) 
        { 
            cin>>dis[i][j]; 
            if(j<3) 
                min[i][j]=0; 
            else 
                min[i][j]=MAX; 
        } 
    }*/  
      
    int temp;  
    int k;  
    for(j=3;j<=N;j++)  
    {  
        for(i=1;i<=N-j+2;i++)  
        {  
            for(k=i+1;k<i+j-1;k++)  
            {  
                  
                temp=weight(i,k,i+j-1)+min[i][k-i+1]+min[k][i+j-k];//动态规划的核心  
                if(temp<min[i][j])  
                {  
                    min[i][j]=temp;  
                    s[i][j]=k;  
                }  
            }  
        }  
  
        for(i=1;i<=N-j+2;i++)  
        {  
            cout<<"min["<<i<<"]["<<j<<"]="<<min[i][j]<<" ";  
        }  
        cout<<endl;  
    }  
      
    cout<<min[1][N]<<endl;  
      
    cout<<"三角形剖片为:"<<endl;  
    printThePath(1,N);  
}</span>  

 

 

补充：软件开发 , C++ ,