2019-02-21  226 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。

代码实现

石子合并

递归公式:

设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

代码实现

时间复杂度为O(n3)

改进算法

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

给我留言

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: