ボトムアップ方式(動的計画法)とは、まず小問題を見て、その小問題の解を使って大きな小問題を解くというものです。
トップダウンでは、問題を自然に解いていき、以前に小問題の解を計算したことがあるかどうかを確認します。
私は少し混乱しています。この2つの違いは何なのでしょうか?
rev4: ユーザーのSammaronさんによる非常に雄弁なコメントにより、おそらくこの回答が以前はトップダウンとボトムアップを混同していたことが指摘されました。もともとこの回答(rev3)や他の回答では、"bottom-up is memoization"("assume the subproblems")としていましたが、その逆(つまり、"top-down"は"assume the subproblems"、"bottom-up"は"compose the subproblems")である可能性があります。以前、メモライゼーションは動的計画法のサブタイプではなく、別の種類の動的計画法であるという記事を読んだことがあります。私はその視点に同意していないにもかかわらず、それを引用していました。私はこの回答を、文献で適切な参照が見つかるまでは用語にとらわれないように書き直しました。また、この回答をコミュニティ・ウィキに変換しました。学術的なソースを希望します。参考文献の一覧です。{Web:1,2}{Literature:5}
Recap
動的計画法とは、重複した計算のやり直しを避けるために、計算の順序を決めることです。メインの問題(サブ問題のツリーのルート)と、サブ問題(サブツリー)があります。サブプロブレムは、通常、繰り返し、重なります。 例えば、あなたが好きなフィボナチの例を考えてみましょう。これは、素朴な再帰呼び出しを行った場合の、サブプロブレムのフルツリーです。
TOP of the tree
fib(4)
fib(3)...................... + fib(2)
fib(2)......... + fib(1) fib(1)........... + fib(0)
fib(1) + fib(0) fib(1) fib(1) fib(0)
fib(1) fib(0)
BOTTOM of the tree
動的計画法には少なくとも2つの主要な手法があり、相互に排他的ではない。
fib(100)
を計算している場合、これを呼び出すだけで、fib(100)=fib(99)+fib(98)
を呼び出し、fib(99)=fib(98)+fib(97)
、...などを呼び出し、fib(2)=fib(1)+fib(0)=1+0=1
を呼び出してしまいます。そして、最終的には fib(3)=fib(2)+fib(1)
を解決しますが、fib(2)
をキャッシュしているので、再計算する必要はありません。,
fib(3),
fib(4)`... すべての値をキャッシュすることで、次の値を簡単に計算できるようになります。また、テーブルを埋めると考えることもできます(キャッシングの別の形)。メモライズのコーディングは非常に簡単で(一般的に "memoizer"アノテーションやラッパー関数を書けば自動的にメモライズをしてくれます)、最初のアプローチにすべきです。表計算の欠点は、順序を考えなければならないことです。
例えば、誰かがプリコンパイルされた fib
関数を既に書いていた場合、その関数は必然的に自分自身への再帰的な呼び出しを行います。これらの再帰的な呼び出しが(元のメモされていない関数ではなく)新しいメモされた関数を呼び出すようにしなければ、魔法のようにその関数をメモすることはできません。
トップダウンでもボトムアップでも、自然ではないかもしれませんが、再帰や反復的なテーブルフィリングで実装できることに注意してください。
メモ化では、ツリーが非常に深い場合(例:fib(10^6)
)、遅延計算をするたびにスタックに乗せる必要があり、10^6個になるので、スタックスペースが足りなくなります。
サブプロブレムにアクセスする(しようとする)順番が最適でない場合、特にサブプロブレムを計算する方法が複数ある場合は、どちらの方法も時間的に最適ではないかもしれません(通常はキャッシュで解決しますが、特殊なケースではキャッシュで解決しないことも理論的にはありえます)。メモ化は、通常、時間的複雑さを空間的複雑さに追加します(例えば、表計算では、計算を捨てる自由度が高く、Fibで表計算を使用するとO(1)の空間を使用できますが、Fibでメモ化を使用するとO(N)のスタック空間を使用します)。
ここでは、一般的なDP問題ではなく、メモ化とタブ化を区別した興味深い例を挙げます。例えば、ある定式化が他の定式化よりもはるかに簡単であったり、基本的に集計を必要とする最適化があったりするかもしれません。
トップダウンDPとボトムアップDPは、同じ問題を解決する2つの異なる方法です。 フィボナッチ数を計算するためのメモライズド(トップダウン)とダイナミック(ボトムアップ)のプログラミングソリューションを考えてみましょう。
fib_cache = {}
def memo_fib(n):
global fib_cache
if n == 0 or n == 1:
return 1
if n in fib_cache:
return fib_cache[n]
ret = memo_fib(n - 1) + memo_fib(n - 2)
fib_cache[n] = ret
return ret
def dp_fib(n):
partial_answers = [1, 1]
while len(partial_answers) <= n:
partial_answers.append(partial_answers[-1] + partial_answers[-2])
return partial_answers[n]
print memo_fib(5), dp_fib(5)
個人的にはmemoizationの方がずっと自然だと思います。 再帰関数を機械的なプロセスでメモ化することができます(最初にキャッシュで答えを探し、可能であればそれを返し、そうでなければ再帰的に計算し、返す前に計算を将来の使用のためにキャッシュに保存します)。一方、ボトムアップ動的計画法を行うには、大きな問題"が依存する小さな問題よりも先に計算されないように、解が計算される順序をコード化する必要があります。
ダイナミック・プログラミングは、よくメモライゼーションと呼ばれています
1.メモライゼーションはトップダウンの手法(与えられた問題を分解して解き始める)、動的計画法はボトムアップの手法(与えられた問題に向かって、些細な小問題から解き始める)。
2.DPは、ベースケースから始めて、上に向かって解を求めていきます。DPはボトムアップで解くため、すべてのサブ問題を解くことができる
2.DPはボトムアップで行うため、すべての部分問題を解くことができる。
3.DPは、指数時間のブルートフォース解法を多項式時間のアルゴリズムに変換する可能性を持っています。
4.DPは、反復的な方法であるため、より効率的であるかもしれません。
逆に、Memoizationは、再帰による(しばしば著しい)オーバーヘッドを支払わなければなりません。
つまり、コア(メイン)問題から始めて、それをサブ問題に分割し、それらのサブ問題を同様に解決するというものです。このアプローチでは、同じサブ問題が複数回発生する可能性があり、より多くのCPUサイクルを消費するため、時間の複雑さが増します。一方、動的計画法では、同じサブ問題を何度も解くことはありませんが、事前の結果を利用して解を最適化します。