資料結構中最佳傾斜樹

尋找不等字母成本的最優字首碼的問題在於計算最小成本字首碼，其中編碼字母表由不等成本（長度）的字母組成，長度為α和β，其中α≤β。我們僅限於二叉樹。

程式碼由傾斜樹表示，類似於霍夫曼樹表示霍夫曼編碼問題的解。儘管兩者相似，但不等字母成本的情況比經典的霍夫曼問題困難得多；儘管文獻豐富，但對於一般的字母成本，仍然沒有已知或可用的多項式時間演算法。

但是，已知存在多項式時間演算法，α和β是整數常數。

在這種情況下計算最小成本樹的問題首先由Karp在1961年研究，他透過歸約到整數線性規劃來解決這個問題，產生一個在n和β上都是指數級的演算法。從那時起，人們對問題的各個方面做了大量工作，例如：對最優樹的成本進行界定；限制為所有權重都相等的特殊情況。

儘管付出了所有這些努力，但令人驚訝的是，基本問題是否可以多項式時間求解或屬於NP完全問題仍然未知。

Golin和Rote描述了一種O(nβ+2)時間的動態規劃演算法，該演算法以自頂向下的方式構建樹。

這已經透過實施不同的方法（單調矩陣概念，例如Monge屬性和SMAWK演算法）得到了改進。

定理1：最優傾斜樹可以在O(nβ)時間內構造。

這是對於β值較小的情況最有效的已知演算法；在實踐中，字母成本通常很小（例如，莫爾斯電碼）。

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

定理2

存在一個用於最優傾斜樹的多項式時間近似方案。

Arnab Chakraborty

更新於：2020年1月7日

184 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習