2019-02-21 249 views 评论

解析动态规划问题（2）

最优三角剖分

与矩阵连乘的不同点

不同点就在于递归公式的不同，最优三角剖分的递归公式如下：
当i=j的时候，m[i][j]=0；
当i<j的时候，m[i][j]=min{m[i][k]+m[k+1][j]+w(v(i-1)vkvj)}

图解示例

我们以一个凸多边形为例，其每条边的权重如下表所示

g[][]	0	1	2	3	4	5
0	0	2	3	1	5	6
1	2	0	3	4	8	6
2	3	3	0	10	13	7
3	1	4	10	0	12	5
4	5	8	13	12	0	3
5	6	6	7	5	3	0

（1）初始化：令m[i][i]=0，s[i][i]=0
（2）计算赋值如下：

m[][]	1	2	3	4	5
1	0	8	22	40	54
2		0	17	41	52
3			0	35	42
4				0	20
5					0\|3

s[][]	1	2	3	4	5
1	0	1	2	3	3
2		0	2	3	3
3			0	3	3
4				0	4
5					0

所以最优权值为m[1][5]=54
（3）构造最优解。过程与矩阵快速相乘类似，都是根据s[][]对应的位置来分成子问题，所以首先是看到s[1][5]=3，所以分为了v0~ v3 和 v3~v5。

因为v0~v3中有结点，所以子问题1不为空，输出该弦v0v3；同理，输出v3v5。
对于子问题1进行递归，读取s[1][3]=2，因为v0~v2有结点，所以输出v0v2……
最后输出的最优解为v0v3,v3v5,v0v2。

代码实现

void  Convexpolygontriangulation()
{
    for(int i = 1 ;i &lt;= n ; i++)    // 初始化
    {
        m[i][i] = 0 ;
        s[i][i] = 0 ;
    }
    for(int d = 2 ;d &lt;= n ; d++)         // 枚举点的个数
      for(int i = 1 ;i &lt;= n - d + 1 ; i++)  // 枚举起始点
      {
          int j = i + d - 1 ;         // 终点
          m[i][j] = m[i+1][j] + g[i-1][i] + g[i][j] + g[i-1][j] ;
          s[i][j] = i ;
          for(int k = i + 1 ;k &lt; j ; k++)     // 枚举中间点
          {
              double temp = m[i][k] + m[k+1][j] + g[i-1][k] + g[k][j] + g[i-1][j] ;
              if(m[i][j] &gt; temp)
              {
                  m[i][j] = temp ;   // 更新最优值
                  s[i][j] = k ;      // 记录中间点
              }
          }
      }
}
void print(int i , int j)  // 输出所有的弦
{
    if(i == j)  return ;
    if(s[i][j]&gt;i)
      cout&lt;&lt;"{v"&lt;&lt;i-1&lt;&lt;"v"&lt;&lt;s[i][j]&lt;&lt;"}"&lt;&lt;endl;
    if(j&gt;s[i][j]+1)
      cout&lt;&lt;"{v"&lt;&lt;s[i][j]&lt;&lt;"v"&lt;&lt;j&lt;&lt;"}"&lt;&lt;endl;
    print(i ,s[i][j]);
    print(s[i][j]+1 ,j);
    //cout&lt;&lt;"{ v"&lt;&lt;i-1&lt;&lt;" , v"&lt;&lt;s[i][j]&lt;&lt;" , v"&lt;&lt;j&lt;&lt;" }"&lt;&lt;endl; //输出所有剖分后的三角形
}

void Convexpolygontriangulation()

{

for(int i = 1 ;i <= n ; i++) // 初始化

{

m[i][i] = 0 ;

s[i][i] = 0 ;

}

for(int d = 2 ;d <= n ; d++) // 枚举点的个数

for(int i = 1 ;i <= n - d + 1 ; i++) // 枚举起始点

{

int j = i + d - 1 ; // 终点

m[i][j] = m[i+1][j] + g[i-1][i] + g[i][j] + g[i-1][j] ;

s[i][j] = i ;

for(int k = i + 1 ;k < j ; k++) // 枚举中间点

{

double temp = m[i][k] + m[k+1][j] + g[i-1][k] + g[k][j] + g[i-1][j] ;

if(m[i][j] > temp)

{

m[i][j] = temp ; // 更新最优值

s[i][j] = k ; // 记录中间点

}

void print(int i , int j) // 输出所有的弦

{

if(i == j) return ;

if(s[i][j]>i)

cout<<"{v"<<i-1<<"v"<<s[i][j]<<"}"<<endl;

if(j>s[i][j]+1)

cout<<"{v"<<s[i][j]<<"v"<<j<<"}"<<endl;

print(i ,s[i][j]);

print(s[i][j]+1 ,j);

//cout<<"{ v"<<i-1<<" , v"<<s[i][j]<<" , v"<<j<<" }"<<endl; //输出所有剖分后的三角形

}

石子合并

递归公式：

设Min[i][j]代表从第i堆石子到第j堆石子合并的最小花费，Min[i][k]代表从第i堆石子到底k堆石子合并的最小花费，Min[k+1][j]代表从第k+1堆石子到第j堆石子合并的最小花费。那么递推式如下：
Min[i][j]=0,i=j
Min[i][j]=min{m[i][k]+m[k+1][j]+w(i,j)} i<j
同理，设Max[i][j]代表从第i堆石子到第j堆石子合并的最大花费，Max[i][k]代表从第i堆石子到底k堆石子合并的最大花费，Max[k+1][j]代表从第k+1堆石子到第j堆石子合并的最大花费。那么递推式如下：
Max[i][j]=0,i=j
Max[i][j]=max{m[i][k]+m[k+1][j]+w(i,j)} i<j

代码实现

void straight(int a[],int n)
{
    for(int i=1;i&lt;=n;i++)  // 初始化
        Min[i][i]=0, Max[i][i]=0;
    sum[0]=0;
    for(int i=1;i&lt;=n;i++)
       sum[i]=sum[i-1]+a[i];
    for(int v=2; v&lt;=n; v++) // 枚举合并的堆数规模
    {
        for(int i=1; i&lt;=n-v+1; i++) //枚举起始点i
        {
            int j = i + v-1; //枚举终点j
            Min[i][j] = INF; //初始化为最大值
            Max[i][j] = -1; //初始化为-1
            int tmp = sum[j]-sum[i-1];//记录i...j之间的石子数之和
            for(int k=i; k&lt;j; k++) {   //枚举中间分隔点
                Min[i][j] = min(Min[i][j], Min[i][k] + Min[k+1][j] + tmp);
                Max[i][j] = max(Max[i][j], Max[i][k] + Max[k+1][j] + tmp);
            }
        }
    }
}
void Circular(int a[],int n)
{
    for(int i=1;i&lt;=n-1;i++)
        a[n+i]=a[i];
    n=2*n-1;
    straight(a, n);
    n=(n+1)/2;
    min_Circular=Min[1][n];
    max_Circular=Max[1][n];
    for(int i=2;i&lt;=n;i++)
    {
        if(Min[i][n+i-1]&lt;min_Circular)
           min_Circular=Min[i][n+i-1];
        if(Max[i][n+i-1]&gt;max_Circular)
           max_Circular=Max[i][n+i-1];
    }
}

void straight(int a[],int n)

{

for(int i=1;i<=n;i++) // 初始化

Min[i][i]=0, Max[i][i]=0;

sum[0]=0;

for(int i=1;i<=n;i++)

sum[i]=sum[i-1]+a[i];

for(int v=2; v<=n; v++) // 枚举合并的堆数规模

{

for(int i=1; i<=n-v+1; i++) //枚举起始点i

{

int j = i + v-1; //枚举终点j

Min[i][j] = INF; //初始化为最大值

Max[i][j] = -1; //初始化为-1

int tmp = sum[j]-sum[i-1];//记录i...j之间的石子数之和

for(int k=i; k<j; k++) { //枚举中间分隔点

Min[i][j] = min(Min[i][j], Min[i][k] + Min[k+1][j] + tmp);

Max[i][j] = max(Max[i][j], Max[i][k] + Max[k+1][j] + tmp);

}

void Circular(int a[],int n)

{

for(int i=1;i<=n-1;i++)

a[n+i]=a[i];

n=2*n-1;

straight(a, n);

n=(n+1)/2;

min_Circular=Min[1][n];

max_Circular=Max[1][n];

for(int i=2;i<=n;i++)

{

if(Min[i][n+i-1]<min_Circular)

min_Circular=Min[i][n+i-1];

if(Max[i][n+i-1]>max_Circular)

max_Circular=Max[i][n+i-1];

}

时间复杂度为O(n³)

改进算法

最小值可以用四边形不等式来优化。
复杂度为O(n²)

void get_Min(int n)
{
    for(int v=2; v&lt;=n; v++) // 枚举合并的堆数规模
    {
        for(int i=1; i&lt;=n-v+1; i++) //枚举起始点i
        {
            int j = i + v-1; //枚举终点j
            int tmp = sum[j]-sum[i-1];//记录i...j之间的石子数之和
            int i1=s[i][j-1]&gt;i?s[i][j-1]:i;
            int j1=s[i+1][j]&lt;j?s[i+1][j]:j;
            Min[i][j]=Min[i][i1]+Min[i1+1][j];
            s[i][j]=i1;
            for(int k=i1+1; k&lt;=j1; k++) //枚举中间分隔点
                if(Min[i][k]+ Min[k+1][j]&lt;Min[i][j])
                {
                    Min[i][j]=Min[i][k]+Min[k+1][j];
                    s[i][j]=k;
                }
            Min[i][j]+=tmp;
        }
    }
}

void get_Max(int n)
{
    for(int v=2; v&lt;=n; v++) // 枚举合并的堆数规模
    {
        for(int i=1; i&lt;=n-v+1; i++) //枚举起始点i
        {
            int j = i + v-1; //枚举终点j
            Max[i][j] = -1; //初始化为-1
            int tmp = sum[j]-sum[i-1];//记录i...j之间的石子数之和
            if(Max[i+1][j]&gt;Max[i][j-1])
               Max[i][j]=Max[i+1][j]+tmp;
            else
               Max[i][j]=Max[i][j-1]+tmp;
        }
    }
}

void straight(int a[],int n)
{
    for(int i=1;i&lt;=n;i++)  // 初始化
        Min[i][i]=0, Max[i][i]=0, s[i][i]=0;
    sum[0]=0;
    for(int i=1;i&lt;=n;i++)
       sum[i]=sum[i-1]+a[i];
    get_Min(n);
    get_Max(n);
}
void Circular(int a[],int n)
{
    for(int i=1;i&lt;=n-1;i++)
        a[n+i]=a[i];
    n=2*n-1;
    straight(a, n);
    n=(n+1)/2;
    min_Circular=Min[1][n];
    max_Circular=Max[1][n];
    for(int i=2;i&lt;=n;i++)
    {
        if(Min[i][n+i-1]&lt;min_Circular)
           min_Circular=Min[i][n+i-1];
        if(Max[i][n+i-1]&gt;max_Circular)
           max_Circular=Max[i][n+i-1];
    }
}