Knuth优化中的单调性

Question

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

相关信息可以通过这里访问。

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

一个是四角不等式，另一个是单调性。

我完全能理解什么是四边形不等式。但是，由于没有关于Monotoniciy的例子，我无法理解它。

单纯性：Cb < Ca (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进行优化。ie 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优化来说是足够好的)。