スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

最適二分探索木問題の Knuth-Yao speedup でなぜオーダーが落ちるか

ネットで検索すると iwiwi さんspaghetti_source さん(前原さん?)のすばらしい記事が見つかるけど、これだけ丁寧に書かれていても自分にはまだギャップがあったので穴埋め。
ほぼ自分用。

ふつうの O(n^3) の DP は
dp[i][j] = min{ dp[i][k] + dp[k+1][j] | k=i...j-1 }
という感じ。( +w[i][j] は省略 )
DP テーブルを図で書くと、

となって、
dp[i][j] を更新するためには
ここ (k=i)

と、ここ (k=i+1)

と、ここ

と、ここ

と、ここ (k=j-1)

を見て、最小値を取ればよい。
これを各 (i, j) の組についてやるので O(n^3) かかる。
ここまではふつう。

さっき、k=i,i+1,...,j-1 と回したときに dp[i][k] + dp[k+1][j] が最小になる k の値を K[i][j] としよう。
そのような k が複数あるときは最大のものを選ぶことにする。
つまり、dp[i][j] = dp[i][K[i][j]] + dp[K[i][j]+1][j]。

たとえば、K[i][j] がここだったとする。


dp[i][j-1] と dp[i+1][j] についても考えてみる。
それぞれ、図の範囲にある二つペアの和のうち最小のものをとってくる。
・dp[i][j-1]

・dp[i+1][j]


K[i][j-1]、K[i+1][j] がそれぞれここだったとしよう。
・K[i][j-1]

・K[i+1][j]


K[i][j-1]、K[i][j]、K[i+1][j] をあわせると次の図になる。


図では K[i][j-1] ≦ K[i][j] ≦ K[i+1][j] となっているが、これは偶然ではない。
一般に、最適二分探索木問題ではこの関係が成立することが証明できる。
このことから、dp[i][j] を求めるのに k=i,i+1,...,j を全部調べなくても K[i][j-1] ≦ k ≦ K[i+1][j] を調べれば十分だと気付く。

この性質を高速化に利用するため、DP 配列の更新方向を従来の
→→→→→
→→→→→
→→→→→
→→→→→
→→→→→
というのじゃなくて、対角線方向に進めるようにする。

たとえば、dp[i-1][j-1]、dp[i][j]、dp[i+1][j+1] という対角線を更新することを考える。


さっき書いたことから、
・dp[i-1][j-1] を求めるのには、K[i-1][j-2] ≦ k ≦ K[i][j-1] を調べれば十分
・dp[i][j] を求めるのには、K[i][j-1] ≦ k ≦ K[i+1][j] を調べれば十分
・dp[i+1][j+1] を求めるのには、K[i+1][j] ≦ k ≦ K[i+2][j+1] を調べれば十分
で、しかも K たちの大小関係は、
K[i-1][j-2] ≦ K[i][j-1] ≦ K[i+1][j] ≦ K[i+2][j+1]
となっている。
つまり、対角線 dp[i-1][j-1]、dp[i][j]、dp[i+1][j+1] を更新するために調べる k の範囲はほぼかぶらない。 ( < じゃなくて ≦ なので端だけかぶる。 )
このことから、対角線一つあたり O(n) で更新できることになり、対角線は n 本あるから全体で O(n^2) 時間が達成できる。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。