最优三角剖分

与矩阵连乘的不同点

不同点就在于递归公式的不同,最优三角剖分的递归公式如下:
当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[][]012345
0023156
1203486
233010137
314100125
458131203
5667530

(1)初始化:令m[i][i]=0,s[i][i]=0
(2)计算赋值如下:

m[][]12345
108224054
20174152
303542
4020
50|3
s[][]12345
101233
20233
3033
404
50

所以最优权值为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)