数据结构中最佳倾斜树

寻找不等字母成本的最优前缀码的问题在于计算最小成本前缀码，其中编码字母表由不等成本（长度）的字母组成，长度为α和β，其中α≤β。我们仅限于二叉树。

代码由倾斜树表示，类似于霍夫曼树表示霍夫曼编码问题的解。尽管两者相似，但不等字母成本的情况比经典的霍夫曼问题困难得多；尽管文献丰富，但对于一般的字母成本，仍然没有已知或可用的多项式时间算法。

但是，已知存在多项式时间算法，α和β是整数常数。

在这种情况下计算最小成本树的问题首先由Karp在1961年研究，他通过归约到整数线性规划来解决这个问题，产生一个在n和β上都是指数级的算法。从那时起，人们对问题的各个方面做了大量工作，例如：对最优树的成本进行界定；限制为所有权重都相等的特殊情况。

尽管付出了所有这些努力，但令人惊讶的是，基本问题是否可以多项式时间求解或属于NP完全问题仍然未知。

Golin和Rote描述了一种O(nβ+2)时间的动态规划算法，该算法以自顶向下的方式构建树。

这已经通过实施不同的方法（单调矩阵概念，例如Monge属性和SMAWK算法）得到了改进。

定理1：最优倾斜树可以在O(nβ)时间内构造。

这是对于β值较小的情况最有效的已知算法；在实践中，字母成本通常很小（例如，莫尔斯电码）。

最近提供了一种有效的近似算法方案。

定理2

存在一个用于最优倾斜树的多项式时间近似方案。

更新于：2020年1月7日

184 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告