文档.txt

用两种方法求解上述问题(针对任意权的和针对本问题的)

#include    "windows.h"
#include    <iostream>
using    namespace    std;

/*
  问题描述:
        把多边形0,...,n-1剖分成n-2个三角形,求给定的权值最小
        本程序定义权为:剖分弦的长度和
  程序功能:
        用两种方法求解上述问题(针对任意权的和针对本问题的)
        解法本质都是动态规划
     PS   :    
        动态规划很难,本程序难免会有错误,但是基本思路是正确的
        注释得很详细了
*/

const    V=5 ;

void    LoadData(float dist[][V]);
/*
        重新定义权为:剖分弦的长度和加上多边形的周长(显然等价),重新求解
        本函数还适用于任何定义在剖分后的三角形上的权的情况(修改一下)
        例如权为三角形的面积的面积平方和
*/
void    minWeightTriangulation(int n, float dist[][V], float t[][V], int s[][V]);
void    ShowSolution(int s[][V], int i, int j);

void    end();

int    main()
{
    float    dist[V][V];
    float    t[V][V];
    int    s[V][V];
    LoadData(dist);
    
    minWeightTriangulation(V, dist, t, s);
    cout<<"最优剖分权:"<<t[1][4] - 2 - 1.414 * 3<<"\t剖分弦:\t";//要减去周长
    ShowSolution(s, 1, 4);
    cout<<endl;
    
    return    0;
}

void    LoadData(float    dist[][V])
{
    dist[0][1] = dist[1][0] = 1;
    dist[1][2] = dist[2][1] = 1;
    dist[2][3] = dist[3][2] = 1.414;
    dist[3][4] = dist[4][3] = 1.414;
    dist[4][0] = dist[0][4] = 1.414;
    dist[0][2] = dist[2][0] = 1.414;
    dist[0][3] = dist[3][0] = 2;
    dist[1][3] = dist[3][1] = 2.236;
    dist[1][4] = dist[4][1] = 2.828;
    dist[2][4] = dist[4][2] = 2;
}

float    Weight(float dist[][V], int i, int j, int k)
{
    return dist[i][j] + dist[j][k] + dist [k][i];
}

void    minWeightTriangulation(int n, float dist[][V], float t[][V], int s[][V])
{
/*
    t[i][j]表示顶点为i-1,i,...,j的多边形的最优三角剖分值
    s[i][j]表示顶点为i-1,i,...,j的多边形的最优三角剖分方法,剖分点为s[i][j]
    退化情况1:s[i][j]==i   剖分成 三角形i-1,i,j    和 多边形i,...,j
    退化情况2:s[i][j]==j-1 剖分成 多边形i-1,...,j-1和 三角形i-1,j-1,j
    一般情况:k = s[i][j]   剖分成 多边形i-1,...,k  和 多边形 k,...,j
    权的定义:多边形的周长+剖分的弦长,所以对两种特殊情况进行了处理
*/
    for (int i = 1; i < n; i++)
        t[i][i] = 0;//只有两个顶点认为权是0
    for (int r = 2; r < n; r++)//r+1边形
    {
        for (i = 1; i <= n - r; i++)
        {
            int j = i + r -1;
            /*当i-1,i,j是相邻三个顶点时(r==2),权为
              t[i+1][j] + Weight(dist, i-1, i, j)
              否则,权为
              t[i+1][j] + Weight(dist, i-1, i, j) - dist[i][j]
              因为t[i+1][j]和eight(dist, i-1, i, j)分别计算了
              一次dist[i][j]
            */
            t[i][j] = t[i+1][j] + Weight(dist, i-1, i, j) -
                (r==2?0:dist[i][j]);
            s[i][j] = i;

            for (int k = i + 1; k < j; k++)
            {/*
               当取剖分i-1,j-1时权为
               t[i][k] + t[k+1][j] + dist[i-1][j] + dist[k][j]
               因为t[k+1][j]退化,权为0,故把边dist[k][j]补上
               否则权为t[i][k] + t[k+1][j] + dist[i-1][j]
             */
                float u = t[i][k] + t[k+1][j] + dist[i-1][j] +
                    (k+1==j?dist[k][j]:0);
                if (u<t[i][j])
                {
                    t[i][j] = u;
                    s[i][j] = k;
                }
            }
        }
    }
}

void    ShowSolution(int s[][V], int i, int j)
{
    if (i + 1 >= j)    return;
    int k = s[i][j];

    if (k == i)
    {//退化情况1:s[i][j]==i   剖分成 三角形i-1,i,j    和 多边形i,...,j
        cout<<'('<<i<<','<<j<<") ";
        ShowSolution(s, i+1, j);
    }
    else
        if (k==j-1)
        {//退化情况2:s[i][j]==j-1 剖分成 多边形i-1,...,j-1和 三角形i-1,j-1,j
            ShowSolution(s, i, j-1);
            cout<<'('<<i-1<<','<<j-1<<") ";
        }
        else
        {//一般情况:k = s[i][j]   剖分成 多边形i-1,...,k  和 多边形 k,...,j
            ShowSolution(s, i, k);
            cout<<'('<<i-1<<','<<k<<") ";
            cout<<'('<<k<<','<<j<<") ";
            ShowSolution(s, k+1, j);
        }
}

float    Distance(float dist[][V], int i, int j)
{
    if (i == (j + 1)%V || j == (i +1)%V)
        return 0;
    return dist[i][j];
}