We present a simple $O(n^4)$-time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time, but is significantly more complicated and is restricted to the variant where only successful queries are allowed. Our algorithm extends directly to solve the standard full variant of the problem, which also allows unsuccessful queries and for which no polynomial-time algorithm was previously known. The correctness proof of our algorithm relies on a new structural theorem for two-way-comparison search trees.
翻译：我们提出了一个简单的 $O( n ⁇ 4) 时间算法, 用于用双向比较来计算最佳搜索树。 由 Anderson 等人( Anderson et al.) 编写的这一问题唯一的前一个解决办法是相同的运行时间, 但更复杂得多, 仅限于只允许成功查询的变式。 我们的算法直接解决了问题的全部标准变式, 这也允许了不成功的查询, 而以前也没有知道任何多元时间算法。 我们算法的正确性证明依赖于双向比较搜索树的新的结构理论。
相关内容
微信扫码咨询专知VIP会员