作为 Oier,四边形不等式,想必大家都很熟悉。本文就来介绍四边形不等式的来历以及应用。

最优二叉搜索树问题

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

问题的形式化定义为:

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

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

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

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

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

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

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

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

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

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

Knuth’s DP Algorithm

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

朴素算法

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

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

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

首先,

对于)而言:

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

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

优化

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

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

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

四边形不等式

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

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

简记为:交叉小于包含。

四边形不等式的命名

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

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

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

四边形不等式优化 DP

Yao 的论文指出:在 Knuth 算法中,如果满足四边形不等式,且满足区间包含单调性,即

那么也满足四边形不等式。

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

始终成立。

而 Knuth 算法的显然满足上面的条件。因此就可以使用决策单调性优化 DP。