本文介绍四边形不等式的来历以及应用。

说明:表示最小化,如果有多个则取最大的那个

四边形不等式

四边形不等式(Quadrangle Inequality)是 Yao 在 1980 年于他的 论文 中定义的。

对于二元函数),称其满足四边形不等式,当且仅当

简记为:交叉小于包含。

四边形不等式的命名

四边形不等式的命名,大概是因为 Yao 在其论文中的证明。在 Yao 论文的条件中,。则当时,上述等式退化为了

如果将理解为的距离,那么上述等式就是反过来的三角不等关系(原本的三角不等关系是)。

类似地,构造一个凸四边形,其顶点顺次标为。那么四边形不等式描述的就是:对角线长度和小于等于对边长度和,相当于把原本的几何关系反过来

历史问题

四边形不等式最早似乎是在研究最优二叉搜索树问题过程中得到的。

最优二叉搜索树问题

最优二叉搜索树问题(Optimal binary search tree),也称带权平衡二叉树问题,指的是对于一些按特定分布的搜索操作,构造最小化(期望)搜索时间的二叉搜索树。

问题的形式化定义为:

给出一个升序数列,以及个概率,分别用以及表示,其中

表示,执行一个指向的搜索的概率。表示执行一个指向之间的数的搜索的概率。特别地,表示指向小于的数,表示指向大于的数。

你需要构造一棵二叉树,使得期望搜索代价最小。

狭义地说,我们定义表示一个搜索操作,其返回一个布尔值,判断是否出现在序列中。那么

  • 就表示我们执行的概率。
  • 表示我们执行,其中的概率。

以上狭义的部分希望能帮助大家理解。

另外,我们可以将二叉树的一条边的遍历理解为单位 1 的代价。

就本问题而言,有两种分支

  • 静态:指构建了二叉树后形态不能变化。
  • 动态:形态可以发生变化。

就动态的问题而言,已经有太多的解决方案,且与四边形不等式不太相关。因此我们讨论的是静态问题的解决方案。

Knuth’s DP Algorithm

Knuth 主要发现了 SOBST 问题的最优子问题的性质,从而得到了一个的 DP 算法。

朴素算法

要最小化期望搜索代价,等价于最小化所有情况的搜索代价之和。而搜索的代价与二叉树的遍历路径长度有关。可以理解为,执行的搜索代价是 BST 上它到根的路径长度乘上搜索它的概率。你可以理解为,之间有一个元素,代表所有之间的数的集合。

表示对之间(不含端点)的数建立二叉搜索树的最小代价和。

另外,设表示,搜索操作指向之间(不含端点)的概率。

首先,

对于)而言:

对于)而言,转移时枚举分割点,把两边的分为左右两棵子树:

该算法直接实现的复杂度是。但 Knuth 使用了一些优化来将 DP 的计算复杂度降至

优化

表示,也就是上述方程中的最优转移决策。那么有

Knuth 在他的 论文 中对此有详细的证明,本文不做解释。从直观的角度,这是很容易理解的。的区间相对于要偏左一些,因此最优分割点更靠左一些。对是有同样的道理。

有了这个推论,我们可以按照从小到大的顺序进行 DP 转移,对于相同的那些 DP 值,可以在的总时间内计算。因此总复杂度

四边形不等式与矩阵

我们注意到四边形不等式是关于二元函数定义的,对此我们可以用矩阵模型描述。

单调矩阵(monotone matrix):对于的矩阵,若,即第行最小值的位置在第行最小值位置的左边,则称该矩阵为单调矩阵。

完全单调矩阵(totally monotone matrix):若矩阵的所有子矩阵均为单调矩阵,则称之为完全单调矩阵。子矩阵指抽出若干行若干列交叉位置上的元素形成的矩阵。

容易证明若满足四边形不等式,则对应的矩阵以及其转置都是完全单调矩阵。

单调矩阵反映了四边形不等式在矩阵上的体现。

四边形不等式优化 DP

在需要用到四边形不等式的性质优化的问题中,四边形不等式往往表现出次模性。这里的次模性指边际效益递减(不一定变小,而是指变劣)。

形式 I

对于满足四边形不等式的代价函数,考虑以下形式的 DP:

应用二分栈算法可以在的时间内完成计算。

根据四边形不等式的性质,我们发现:对于两个决策点),如果,则随增加不可能变优。

因此对于优于只占一段时间。

于是我们可以二分出劣于的最早时刻

而且这个是单调的。证明:考虑矩阵。这个矩阵满足四边形不等式。在其中扮演一个分界点的角色。然后你可以反证法证明。它是单调的。

这样我们就只需要支持在序列末位插入/删除元素,在序列上二分。使用栈维护即可。

形式 II

Yao 的论文指出:在 Knuth 算法中,如果满足四边形不等式,那么也满足四边形不等式。

同时它也指出,如果满足四边形不等式,那么

始终成立。

因此就可以使用决策单调性优化 DP。

应用:背包问题

你有个物品,大小和权值分别为。你有一个大小为的背包,求放入背包的物品权值和的最大值。

考虑 DP。由于物品的大小较小,因此考虑分类。设表示考虑大小小于等于的所有物品和大小为的背包的最大价值和。设表示选个大小为的物品的权值和的最大值,那么显然

类似多重背包的套路,我们将转移按模的余数分类,那么可以将方程转化为类似

的形式,其中

显然这是一个满足四边形不等式的 DP 方程,可以应用二分栈算法解决。