作为 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。