最適二分探索木

前章で最後に考えたのは最適二分探索木の問題でした。入力は探索のためのソートされた鍵 \(A[1..n]\) と頻度 \(f[1..n]\) であり、\(f[i]\) が \(A[i]\) に対する探索の回数を表します。出力は入力の鍵に対する二分探索木であって全ての探索の合計時間を最小にするものです。

頻度を表す配列 \(f\) を固定し、\(A[i..k]\) の最適探索時間を \(\mathit{OptCost}(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} \] これから何をするのか想像がつくと思いますが、まずは和をどうにかします。

添え字の組 \(i,k\) (\(i \leq k\)) に対して、 鍵 \(A[i..k]\) に対応する頻度の合計を \(F(i, k)\) で表すことにします: \[ F(i, k) := \sum_{j=i}^{k}f[j] \] この関数は次の単純な再帰方程式を満たします: \[ F(i, k) := \begin{cases} f[i] & \text{if } i = k \\ F(i, k - 1) + f[k] & \text{それ以外} \end{cases} \] \(F(i, k)\) がとりうる全ての値は \(O(n^{2})\) 時間で計算できます。計算には、もちろん、動的計画法を使います。何度も使ってきた機械的なステップを踏めば、次のアルゴリズムとなります:

procedure \(\texttt{InitF}\)(\(f[1..n]\))

for \(i \leftarrow 1\) to \(n\) do

\(F[i,i-1] \leftarrow 0\)

for \(k \leftarrow i\) to \(n\) do

\(F[i,k] \leftarrow F[i, k - 1] + f[k]\)

このアルゴリズムは初期化処理として利用します。\(F\) を初期化しておけば、再帰方程式を次のように単純化できます: \[ \mathit{OptCost}(i, k) = \begin{cases} 0 & \text{if } i > k \\ \displaystyle F[i, k] + \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}(i, k) = \begin{cases} 0 & \text{if } i > k \\ \displaystyle F[i, k] + \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}\) 関数は二つの引数を取り、そのどちらもおおよそ \(n\) 個の異なる値を取るので、サイズが \(O(n^{2})\) のデータ構造が必要になると予想できます。また再帰方程式の本質的な部分には三つの変数 (\(i,k,r\)) があり、それぞれがおおよそ \(n\) 個の異なる値を取るので、全ての値を計算するには \(O(n^{3})\) の時間がかかると予想できます。



Amazon.co.jp アソシエイト (広告)
Audible の無料体験を始めよう
amazon music unlimited で音楽聞き放題
The Art of Computer Programming Volume 1 Fundamental Algorithms
プログラミングコンテストチャレンジブック [第2版]
世界標準MIT教科書 Python言語によるプログラミングイントロダクション
アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書