从最优二叉树问题到四边形不等式
作为 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。
修订记录
- 2020年7月31日 创建文章