algorithm - Knuth 优化中的单调性

Question

我正在学习什么是 Knuth 优化。

相关信息可通过here查询

Knuth 优化基本上有两个假设。

一个是四边形不等式，另一个是单调性

我完全可以理解什么是四边形不等式。但是，由于没有例子解释Monotoniciy，我无法理解。

单调性:C[b][c] < C[a][d] (a, b, c, d)

据我所知，Monotonicity 是一种线性特征，如果在它们之外的元素 (a, d) 之间有两个不同的元素 (b, c)，成本在范围 b 到 c 小于范围 a 到 d 的成本。

那么为什么这不适用于链式矩阵问题？

假设有一组矩阵{x1, x2, ..., xn}

显然，b 到 c 范围内的乘法成本小于 a 到 d 范围内的乘法成本，因为 a 到 d 范围内的元素比 b 到 c 范围内的元素多。

有人可以解释一下吗？

Answer 1

相对单调性也可以在更高的维度上。想象一个 2D 平面，您握住右下角的连接器并抬起它，这样我们就可以得到 A[i-1][j] <= A[i][j] <= A[i][j+1] .

如果这种单调性成立，那么我们说可以使用 Knuth Optinimzaton 优化问题空间。即F[i][j] = min{F[i][k]+F[k+1][j]}+C[i][j] for k=i to j-1 ,那么只遍历from k=P[i-1][j] to P[i][j+1]就可以优化了其中 P[i][j]是A[i][j]的点是最小值。

原始问题需要 O(n^3) 而由于上述单调性，现在可以在 O(n^2) 中解决

(注意:这里任何两个元素之间没有绝对单调性，这就是为什么我将其称为相对单调性，如果两个元素是这样的，一个在另一个元素的东南方向，那么东南方向的元素大于或等于另一方面，这种关系对于 Knuth 优化来说已经足够了)