322

メモ化と動的計画法の違いは何ですか? 動的計画法はメモ化のサブセットだと思います。そうですか？

4

11 に答える 11

465

Programming.Guide の関連記事:動的プログラミング vs メモ化 vs 作表

メモ化と動的計画法の違いは何ですか?

メモ化とは、以前に計算された結果をキャッシュし、同じ計算が再び必要になったときにキャッシュされた結果を返す最適化手法を表す用語です。

動的計画法は、再帰的な性質の問題を反復的に解く手法であり、部分問題の計算が重複する場合に適用できます。

動的計画法は通常、集計を使用して実装されますが、メモ化を使用して実装することもできます。ご覧のとおり、どちらも他方の「サブセット」ではありません。

合理的なフォローアップの質問は、次のとおりです。集計 (典型的な動的計画法) とメモ化の違いは何ですか?

作表を使用して動的計画法の問題を解く場合、「ボトムアップ」で問題を解決します。つまり、最初に関連するすべてのサブ問題を解決し、通常はn次元のテーブルを埋めます。表の結果に基づいて、「トップ」/元の問題の解が計算されます。

メモ化を使用して問題を解決する場合は、既に解決済みのサブ問題のマップを維持することによってそれを行います。「トップ」の問題を最初に解決するという意味で、 「トップダウン」で行います (これは通常、下位の問題を解決するために下に再帰します)。

ここからの良いスライド(リンクは現在死んでいますが、スライドはまだ良いです):

  • すべての部分問題を少なくとも 1 回は解決する必要がある場合、通常、ボトムアップの動的計画法アルゴリズムはトップダウンのメモ化アルゴリズムよりも一定の係数で性能が優れています。
    • 再帰のオーバーヘッドがなく、テーブルを維持するためのオーバーヘッドが少ない
    • 動的プログラミング アルゴリズムのテーブル アクセスの規則的なパターンを利用して、時間またはスペースの要件をさらに削減できる問題がいくつかあります。
  • 部分問題空間内のいくつかの部分問題がまったく解決する必要がない場合、メモ化された解決策には、明らかに必要な部分問題のみを解決するという利点があります。

その他のリソース:

于 2011-05-31T08:42:11.210 に答える
18

動的プログラミングはしばしばメモ化と呼ばれます!

  1. メモ化はトップダウン手法 (与えられた問題を分解して解き始める) であり、動的計画法はボトムアップ手法 (些細な部分問題から解き始め、与えられた問題に向かって解決する) です。

  2. DP は、基本ケースから開始して解決策を見つけ、上に向かって進みます。DP はボトムアップで行うため、すべてのサブ問題を解決します。

    必要なサブ問題のみを解決するメモ化とは異なり

  3. DP には、指数時間のブルート フォース ソリューションを多項式時間アルゴリズムに変換する可能性があります。

  4. DP は反復的なため、はるかに効率的である可能性があります。

    逆に、Memoization は、再帰による (しばしば重要な) オーバーヘッドを支払わなければなりません。

もっと簡単に言うと、Memoization はトップダウン アプローチを使用して問題を解決します。つまり、コア (メイン) 問題から始めて、サブ問題に分割し、これらのサブ問題を同様に解決します。このアプローチでは、同じサブ問題が複数回発生し、より多くの CPU サイクルを消費する可能性があるため、時間の複雑さが増します。一方、動的プログラミングでは、同じサブ問題が複数回解決されることはありませんが、前の結果がソリューションの最適化に使用されます。

于 2013-08-20T18:12:12.807 に答える
10

ウィキペディアから：

メモ化

コンピューティングでは、メモ化は、関数呼び出しで以前に処理された入力の結果の計算を繰り返さないようにすることで、主にコンピューター プログラムを高速化するために使用される最適化手法です。

動的計画法

数学とコンピューター サイエンスでは、動的計画法は、複雑な問題をより単純な部分問題に分解することで解決する方法です。

問題をより小さな/単純な部分問題に分割する場合、同じ部分問題に何度も遭遇することがよくあります。そのため、メモ化を使用して以前の計算の結果を保存し、それらを繰り返す必要がないようにします。

動的プログラミングでは、メモ化を使用することが理にかなっている状況に遭遇することがよくありますが、必ずしも他の手法を使用しなくても、どちらの手法も使用できます。

于 2011-05-31T08:38:26.470 に答える