解析动态规划问题（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。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
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
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
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)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
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]; } } |
