パターン: 賢い再帰
簡潔に言ってしまえば、動的計画法とは無駄のない再帰です。
たしかに動的計画法を使ったアルゴリズムは、途中で解く小問題の答えを配列や表などのデータ構造に保存します。しかしアルゴリズムを学ぶ生徒 (そして教師と教科書) は、この表を強調しすぎるという間違いを犯しています。表なら誰でも知っていて簡単に理解できるからそうするのでしょうが、こうするとはるかに重要な (そしてはるかに難しい) 問題である、正しい再帰方程式を見つける部分が軽視されてしまいます。正しい再帰方程式をメモ化している限り表が絶対に必須というわけではありませんが、もし再帰方程式が間違っていたら、アルゴリズムは絶対に正しく動きません。
動的計画法は表を埋めることではない！
賢く再帰を行うことだ！
動的計画法を使ったアルゴリズムを開発するときは、次に示す二つの独立したステップを踏むとよいでしょう:
-
問題を再帰的に定式化する: 全体の問題に対する再帰的な定式化あるいはアルゴリズムを、より小さい小問題を使って書く。ここが難しい部分である。細かく書くと、二つの部分に分かれる:
-
仕様: 再帰的に解きたい問題を ――どうやって問題を解くかではなく、問題が何であるかを―― 正確で分かりやすい英語で表現する。この仕様が無くては、答えを判定することはどうやっても不可能である。
-
答え: 全体の問題に対する再帰的な定式化とアルゴリズムを、全く同じ問題に対するより小さいインスタンスを使って明確に示す。
-
-
再帰方程式を解く手続きをゼロから組み立てる: 再帰方程式のベースケースから始まって最終的な答えを計算するアルゴリズムを書く。途中で生じる小問題は正しい順番で解く。この段階は次の小さな、比較的機械的なステップに分けられる。
-
小問題を特定する: 最初の入力を受け取ってから、アルゴリズムはどんな再帰呼び出しを行うか？ 例えば \(\textsc{RecFibo}\) が再帰的に呼ばれるとき、引数は常に \(0\) から \(n\) までの整数だった。
-
メモ化のためのデータ構造を選択する: (a) で特定した全ての小問題の答えを格納するためのデータ構造を見つける。通常は多次元の配列だが、そうでない場合もある。
-
依存を特定する: ベースケースを除けば、全ての小問題は他の小問題の答えに依存している ――具体的にどれか？ データ構造の絵を描き、一般的な要素が依存している要素へ矢印を描く。そしてその絵を定式化する。
-
正しい評価順序を見つける: 全ての小問題を一列に並び替えて、任意の小問題について、それが依存している問題が前に来るようにする。ベースケースを最初に考え、次にベースケースだけに依存する問題、といった風に順番に最後の問題まで考えていくのが良い。一つ前のステップで特定した依存関係が小問題の間の半順序を定義すると考えれば、このステップで求めるのはその順序の線形拡大である。
-
消費空間および実行時間を解析する: メモ化されたアルゴリズムの消費空間量は、異なる小問題の数によって決まる。全体の実行時間を求めるには、より深い再帰呼び出しが全てメモ化されていると仮定した上での、全ての小問題の実行時間の和を求める。このステップは (a) の直後に行うことができる。
-
アルゴリズムを書く: 小問題をどの順番でどう解くかが分かったので、書く！データ構造が配列ならば、再帰方程式を何回かネストされた for ループで包み、再帰呼び出しを配列のルックアップに変えれば済むことが多い。
-
もちろん、全てのステップには正しさの証明が必要です。再帰方程式が間違っていたり、答えを間違った順序で組み立てていたりすると、アルゴリズムは正しく動きません！