データ構造における最適な偏った木

不等文字コストに最適なプレフィックスフリーコードを見つける問題は、エンコーディングアルファベットが長さαとβの不等コスト（長さ）文字で構成され、α≤βである最小コストのプレフィックスフリーコードを計算することです。二分木に限定します。

ハフマンツリーがハフマンコーディング問題の解を表すのと同じように、コードは偏ったツリーで表されます。類似性にもかかわらず、文字のコストが等しくない場合は、古典的なハフマンの問題よりもはるかに困難です。問題に関する豊富な文献があるにもかかわらず、一般的な文字のコストについては、多項式時間アルゴリズムは知られていないか、利用できません。

ただし、利用可能な既知の多項式時間アルゴリズムがあります。αとβは整数定数です。

この場合の最小コストツリーの計算の問題は、1961年にKarpによって最初に研究され、整数線形計画法に還元して問題を解決し、nとβの両方で指数関数的なアルゴリズムを生成しました。それ以来、次のような問題のさまざまな側面について多くの作業が行われてきました。最適なツリーのコストを制限します。すべての重みが等しい場合の特殊なケースへの制限。

これらすべての努力にもかかわらず、驚くべきことに、基本的な問題が多項式時間で解けるのか、NP完全であるのかはまだ不明です。

GolinとRoteは、トップダウン方式でツリーを構築するO（nβ+ 2）時間の動的計画法アルゴリズムについて説明しています。

これは、別のアプローチ（MongeプロパティやSMAWKアルゴリズムなどの単調行列の概念）を実装することで改善されました。

定理1：最適な偏った木はO（nβ）時間で構築できます。

これは、βの値が小さい場合の最も効率的な既知のアルゴリズムです。実際には、手紙の費用は通常わずかです（モールス信号など）。

最近、効率的な近似アルゴリズムのスキームが提供されました。

定理2

最適な偏った木のための多項式時間近似スキームがあります。