算法筆記之動态規劃（3）

最優三角剖分

與矩陣連乘的不同點

不同點就在于遞歸公式的不同，最優三角剖分的遞歸公式如下：

當i=j的時候，mi=0；

當i

圖解示例

我們以一個凸多邊形為例，其每條邊的權重如下表所示

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

（1）初始化：令mi=0，si=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[][]

是以最優權值為m1=54

（3）構造最優解。過程與矩陣快速相乘類似，都是根據s[][]對應的位置來分成子問題，是以首先是看到s1=3，是以分為了v0~ v3 和 v3~v5。

• 因為v0~v3中有結點，是以子問題1不為空，輸出該弦v0v3；同理，輸出v3v5。
• 對于子問題1進行遞歸，讀取s1=2，因為v0~v2有結點，是以輸出v0v2……
• 最後輸出的最優解為v0v3,v3v5,v0v2。

代碼實作

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; //輸出所有剖分後的三角形
}           

石子合并

遞歸公式：

設Mini代表從第i堆石子到第j堆石子合并的最小花費，Mini代表從第i堆石子到底k堆石子合并的最小花費，Mink+1代表從第k+1堆石子到第j堆石子合并的最小花費。那麼遞推式如下：

Mini=0,i=j

Mini=min{mi+mk+1+w(i,j)} i同理，設Maxi代表從第i堆石子到第j堆石子合并的最大花費，Maxi代表從第i堆石子到底k堆石子合并的最大花費，Maxk+1代表從第k+1堆石子到第j堆石子合并的最大花費。那麼遞推式如下：

Maxi=0,i=j

Maxi=max{mi+mk+1+w(i,j)} i

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(n3)

改進算法

最小值可以用四邊形不等式來優化。

複雜度為O(n2)

void get_Min(int n)
{
    for(int v=2; v<=n; v++) // 枚舉合并的堆數規模
    {
        for(int i=1; i<=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]>i?s[i][j-1]:i;
            int j1=s[i+1][j]<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<=j1; k++) //枚舉中間分隔點
                if(Min[i][k]+ Min[k+1][j]<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<=n; v++) // 枚舉合并的堆數規模
    {
        for(int i=1; i<=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]>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<=n;i++)  // 初始化
        Min[i][i]=0, Max[i][i]=0, s[i][i]=0;
    sum[0]=0;
    for(int i=1;i<=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<=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];
    }
}