[解決済み】ボトムアップとトップダウンの違いは何ですか？

質問

その ボトムアップ 動的計画法の）アプローチは、まず「より小さな問題」に注目し、「より小さな問題」の解決策を利用して「より大きな問題」を解くというものです。

その トップダウン は、自然な方法で問題を解き、以前に部分問題の解を計算したことがあるかどうかを確認することです。

少し混乱しています。この2つの違いは何でしょうか？

どのように解決するのですか？

rev4：ユーザーのSammaronさんからの非常に雄弁なコメントにより、おそらく以前はこの回答がトップダウンとボトムアップを混同していたことが指摘されました。もともとこの回答（rev3）や他の回答では、"ボトムアップはmemoization" （"assume the subproblems"）とされていますが、逆かもしれません（つまり、"トップダウン" は "assume the subproblems" 、"ボトムアップ" は "compose the subproblems" かもしれない）。以前、メモ化は動的計画法の亜種ではなく、別の種類の動的計画法であるという話を読んだことがあります。私はその見解に賛同しているわけではないのですが、引用させていただきました。この回答は、適切な文献が見つかるまでは、用語にこだわらないように書き直しました。また、この回答はコミュニティWikiに変換しました。学術的なソースを希望します。参考文献の一覧です。{Web: 1 , 2 } {文学 5 }

振り返り

動的計画法とは、重複した再計算を避けるために、計算の順番を決めることです。主問題（部分問題の木のルート）と部分問題（サブツリー）があります。 サブ問題は通常、繰り返され、重なり合う .

例えば、皆さんの大好きなフィボナシの例で考えてみましょう。これは、素朴な再帰呼び出しを行った場合の、サブ問題の全ツリーです。

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) というのは、キャッシュしているからです。
  • これは、木の頂点から始まり、葉やサブツリーからルートに向かってサブ問題を評価するものです。

• 表埋め - ダイナミックプログラミングを表埋めアルゴリズムと考えることもできます（通常は多次元ですが、ごくまれにこの「表」が非ユークリッド幾何学になることがあります*）。これはメモ書きのようなものだが、より能動的であり、1つのステップが追加されている。計算を行う正確な順序を前もって決めておかなければならない。このことは、その順序が固定的でなければならないことを意味するのではなく、メモ化よりもはるかに柔軟性があることを意味する。

  • の例です。 フィボナッチを行う場合、この順番で数字を計算することになるかもしれません。 fib(2) , fib(3) , fib(4) ... すべての値をキャッシュすることで、次の値をより簡単に計算することができます。また、これはテーブルを埋めることだと考えることもできます（キャッシュの別の形態）。
  • 個人的には「集計」という言葉はあまり聞きませんが、とてもまっとうな言葉です。これを"ダイナミックプログラミング"と考える人もいます。
  • アルゴリズムを実行する前に、プログラマはツリー全体を考慮し、次にルートに向かって特定の順序でサブ問題を評価するアルゴリズムを書き、一般的にテーブルを埋める。
  • *脚注：「表」は、それ自体、格子状の接続性を持つ長方形の表ではないこともあります。むしろ、木や、問題領域に特有の構造（例えば、地図上の飛行距離内の都市）、あるいは、格子状ではあるが上下左右の接続構造を持たないトレリス図など、より複雑な構造を持つ場合もある。例えば、user3290797は、動的計画法（ダイナミックプログラミング）による 木における最大独立集合 これは、木の空白を埋めることに相当する。

(最も一般的な、ダイナミックプログラミングのパラダイムでは、プログラマはツリー全体を考慮すると言ってよいでしょう。 では は、あなたが望む特性（通常は時間-複雑性と空間-複雑性の組み合わせ）を最適化できる部分問題を評価する戦略を実装するアルゴリズムを書きます。この戦略は，ある特定の部分問題から出発し，その評価結果に基づいて自分自身を適応させることができる．一般的な意味での動的計画法では，これらの部分問題をキャッシュし，より一般的には部分問題の再利用を避けようとするかもしれませんが，微妙な違いとして，様々なデータ構造におけるグラフの場合があります．このようなデータ構造は、その中核が配列やテーブルであることが非常に多いのです。小問題の解は、不要になったら捨てることができるのです)。

[前回、この回答ではトップダウンとボトムアップの用語について述べましたが、明らかにメモ化とタブレーションという2つの主要なアプローチがあり、これらの用語と（完全ではないものの）双対をなしている可能性があります。多くの人が使う一般的な用語はまだ「動的計画法」であり、「動的計画法」の特定のサブタイプを指して「メモ化」と言う人もいます。最終的には、用語よりもむしろ区別を理解することが重要です]。

長所と短所

コーディングのしやすさ

メモライゼーションは非常に簡単にコーディングでき（一般的に*アノテーションやラッパー関数を書けば、自動的にメモライゼーションを行ってくれます）、最初のアプローチとなるべきものです。集計の欠点は、順序を考え出す必要があることです。

*(これは、あなたが自分で関数を書いている場合、および/または、不純な/非機能的なプログラミング言語でコーディングしている場合にのみ、実際には簡単です... 例えば、誰かが既にプリコンパイルされた fib 関数は、必然的に自分自身への再帰的な呼び出しを行います。そして、それらの再帰的な呼び出しが、（メモされていない元の関数ではなく）メモされた新しい関数を呼び出すようにしなければ、関数を魔法のようにメモすることはできません)。

再帰性

なお、トップダウンとボトムアップのいずれも、再帰処理や反復的な表埋め込みで実装することができるが、自然ではないかもしれない。

実用的な懸念事項

メモ化では、ツリーが非常に深い場合（例えば fib(10^6) というのも、遅延させた計算をそれぞれスタックに置く必要があり、その数は10^6個になるからです。

最適化

どちらのアプローチも、サブ問題を訪れる（または訪れようとする）順番が最適でない場合、特にサブ問題を計算する方法が複数ある場合、時間最適化されないことがあります（通常はキャッシュで解決しますが、エキゾチックなケースではキャッシュが解決しない可能性も理論的にはあります）。メモ化は通常、空間的複雑さに時間的複雑さを加えます（例えば、Fibで集計を使用するとO(1)の空間を使用できますが、Fibでメモ化を使用するとO(N)のスタック空間を使用するなど、集計では計算を捨てる自由度が高くなります）。

高度な最適化

また、極めて複雑な問題を扱う場合は、タブレーションを行うしかないかもしれません（あるいは、少なくともメモライゼーションを望む方向に舵を切るためにより積極的な役割を果たす）。また、最適化が絶対的に重要で、最適化しなければならない状況であれば、集計によって、メモライゼーションではまともにできないような最適化を行うことができます。私の考えでは、通常のソフトウェアエンジニアリングでは、この2つのケースは決して起こらないので、何か（スタックスペースなど）集計が必要でない限り、私はメモ化（"答えをキャッシュする関数"）を使うだけです...。技術的には、スタックブローアウトを避けるために、1）スタックサイズの上限を増やす、2）スタックを仮想化するために一定倍以上の余分な作業をする、3）継続パッシングスタイルでプログラムし、事実上スタックを仮想化する（この複雑さはわかりませんが、基本的には、サイズNのスタックから遅延呼び出しチェーンを事実上取り出し、それをN個の連続的に入れ子になったthunk関数に入れることになります）などがあります。 しかし、テールコール最適化のない言語では、スタックブローアウトを避けるためにトランポリンが必要になることがあります）。

より複雑な例

ここでは、一般的なDP問題ではなく、メモ化と集計を区別した興味深い例を列挙します。例えば、一方の定式化が他方よりずっと簡単であったり、基本的に集計を必要とする最適化があったりします。

• 編集距離を計算するアルゴリズム[ 4 2次元の表埋めアルゴリズムの非自明な例として興味深い] 。