最適二分探索木

この章で最後に説明するのは、再帰的なバックトラッキングと分割統治法を組み合わせた例です。

二分探索木の探索が成功した場合、その実行時間は探索する頂点の祖先¹の数に比例することを思い出してください。このため探索の最悪実行時間は木の深さに等しくなります。したがって探索処理の最悪計算時間を小さくするには、木の高さは最小であるべきであり、理想は完璧にバランスの取れた木です。

しかし二分探索木が使われる多くの場合においては、重要となるのは最悪の場合の計算時間ではなくて、何度か行われる探索の平均実行時間であることが多いです。もし \(x\) が \(y\) よりも頻繁に探索されるのであれば、\(x\) を \(y\) よりも木の上の方に配置することで (たとえそれで木の深さが大きくなったとしても) 時間を節約できます。ある要素が他の要素に比べて格段に多く探索される場合、完全二分木は最適な形ではありません。深さが \(\Omega(n)\) の全くバランスの取れていない木が最適である可能性だってあります！

この状況は次の問題として定式化できます。すなわち、ソートされた鍵 (key) 配列 \(A[1..n]\) とそれに対応するアクセス頻度 (access frequency) \(f[1..n]\) が与えられ、鍵 \(A[i]\) が \(f[i]\) という頻度で探索されるときに、全体の探索時間を最小化する二分探索木を作る問題です。

解法を考える前に、この問題で最小化すべき再帰的な関数の定義を考えましょう。 頂点 \(v_{1}, v_{2}, \ldots, v_{n}\) を持つ二分探索木 \(T\) が与えられ、頂点の添え字は頂点 \(v_{i}\) が鍵 \(A[i]\) を保持するようにソートされているとします。このとき全ての頂点に対する二分探索の実行時間は、定数部分を無視すると次のように書けます: \[ \mathit{Cost}(T, f[1..n]) := \sum_{i=1}^{n} f[i] \cdot T \text{ における } v_{i} \text{ の祖先の数} \quad (*) \] \(v_{r}\) と \(T\) の根とすると、定義により \(v_{r}\) は \(T\) の全ての要素の祖先です。\(A\) がソートされていることから、\(i < r\) ならば \(v_{r}\) を除く \(v_{i}\) の祖先は全て \(T\) の左側の部分木に属します。同様に \(i>r\) ならば \(v_{r}\) を除く \(v_{i}\) の祖先は全て \(T\) の左の部分木に属します。よって、\(\mathit{Cost}\) 関数を次のように分割できます: \[ \begin{aligned} \mathit{Cost}(T, f[1..n]) := \sum_{i=1}^{n}f[i] & + \sum_{i = 1}^{r - 1} f[i] \cdot \mathit{left}(T) \text{ における } v_{i} \text{ の祖先の数} \\ & + \sum_{i = 1}^{r + 1} f[i] \cdot \mathit{right}(T) \text{ における } v_{i} \text{ の祖先の数} \end{aligned} \] 二番目と三番目の項は \(\mathit{Cost}\) の定義 \((*)\) と同じなので、この式をさらに変形して再帰方程式にできます: \[ \begin{aligned} \mathit{Cost}(T, f[1..n]) := \sum_{i=1}^{n}f[i] & + \mathit{Cost}(\mathit{left}(T), f[1..r-1]) \\ & + \mathit{Cost}(\mathit{right}(T), f[r+1..n]) \end{aligned} \] この再帰方程式に対するベースケースは、いつもと同じように、\(n = 0\) における \(\mathit{Cost} = 0\) です。空配列に対しては探索が全く行われず、時間消費が \(0\) だからです。

この \(\mathit{Cost}(T, f)\) 関数を最小化するような二分探索木 \(T_{opt}\) を作ることが目標となります。もし何らかのマジカルな方法で \(T_{opt}\) の根が \(v_{r}\) であると知ることができたならば、\(\mathit{Cost}(T, f)\) の定義から直ちに、部分木 \(\mathit{left}(T_{opt})\) が鍵 \(A[1..r-1]\) と頻度 \(f[1..r-1]\) に対する最適二分探索木であることが分かります。同様に、 \(\mathit{right}(T_{opt})\) は鍵 \(A[r+1 .. n]\) と頻度 \(f[1..r-1]\) に対する最適二分探索木であることも分かります。つまり、最適木の根さえ正しく選択すれば、残りは再帰の妖精が作ってくれます。

もっと一般的に言えば、\(\mathit{OptCost}(i, k)\) を頻度 \(f[i..k]\) に対応する最適二分探索木の探索時間の和としたとき、この関数は以下の再帰方程式に従います: \[ \mathit{OptCost}(i, k) = \begin{cases} 0 & \text{if } i > k \\ \displaystyle \sum_{j=i}^{k}f[j] + \min\limits_{i \leq r \leq k} \left \lbrace \begin{array}{l} \mathit{OptCost}(i, r-1) \\ \ + \mathit{OptCost}(r+1, k) \end{array} \right \rbrace & \text{それ以外} \end{cases} \] ベースケースは空配列に対する探索がゼロ時間で終わることを表します。元々の問題に対する答えは \(\mathit{OptCost}(1, n)\) となります。

この再帰的な定義を使えば、\(\mathit{OptCost}(1, n)\) を計算するバックトラッキングを使った再帰的アルゴリズムが機械的に書けます。驚くことではありませんが、このアルゴリズムの実行時間は指数時間です。次の章ではこの実行時間を多項式時間に抑える方法について見るので、ここで正確な実行時間を求めることにはあまり意味がありません...

❤ 解析

...あなたが興味を持っていない限りは。面白そうなので、このバックトラッキングを使ったアルゴリズムがどれだけ遅いかを正確に計算してみましょう。実行時間は次の再帰方程式を満たします: \[ T(n) = \sum_{k=1}^{n}(T(k - 1) + T(n - k)) + O(n) \] ここで \(O(n)\) の項は探索の回数 \(\sum_{i=1}^{n} f[i]\) を求めるための時間です。ぎょっとするような方程式ですが、前に使った引き算によるテクニックをここでも使うことができます。\(O()\) 表記を明示的な定数で置き換え、式を整理して、\(T(n) - T(n-1)\) を計算して和を消し、最後にまた整理します: \[ \begin{aligned} T(n) & = 2\sum_{k=0}^{n-1} T(k) + \alpha n \\ T(n-1) & = 2\sum_{k=0}^{n-2} T(k) + \alpha (n-1) \\ T(n) - T(n-1) & = 2T(n-1) + \alpha \\ \therefore T(n) & = 3T(n-1) + \alpha \end{aligned} \] これなら何とかできそうです。再帰木を使うと \(\pmb{T(n) = O(3^{n})}\) が分かります (帰納法を使っても確認できます)。

この解析によると、この再帰的なアルゴリズムは全ての二分探索木を検査するわけではありません！なぜなら、 \(n\) 個の頂点を持つ二分探索木の数 \(N(n)\) は再帰方程式 \[ N(n) = \sum_{r=1}^{n-1}(N(r - 1) \cdot N(n - r)) \] を満たし、この解は \(N(n) = \Theta(4^{n} / \sqrt{n})\) だからです (この解は自明ではありません)。最適二分探索木を求めるアルゴリズムは、左右の部分木を独立に調べることによって大きく時間を節約しています。二分探索木に対する総当たりを行うと左右の部分木を組で考えることになり、余計に時間がかかります。これは \(N(n)\) が満たす方程式に積が含まれていることからも分かります。

1. 頂点 \(v\) の祖先 (ancestor) とは、その頂点と \(v\) の親の祖先を合わせたものです。 \(v\) の真の祖先 (proper ancestor) とは、 \(v\) の親と \(v\) の親の真の祖先を合わせたものです。^[return]