1

始める前に、いいえ、これはメモ化と動的プログラミングの違いやどちらが優れているかを尋ねる質問ではなく、キャッシュされたルックアップを処理する方法の小さな違いについて尋ねる単純な質問です。

DP はボトムアップのアプローチを使用しますが、メモ化はトップダウンのアプローチを使用します。したがって、DP では、キャッシュされた計算のテーブルを構築することから始め、キャッシュされた値をより大きな計算に供給して、冗長な再帰的または反復的な関数呼び出しを回避します。メモ化は多かれ少なかれ、各関数呼び出しの結果をハッシュまたは配列 (おそらく配列) にキャッシュし、関数呼び出し内で結果を提供するだけです (関数の本体内で発生するものはすべてスキップします)。

私の質問は、私がここで述べていることは正しいですか? 両方のアプローチは類似しているように見えますが、メモ化に比べて DP の方が難しく、メモリを使用する方がわずかに効率的です。メモ化を使用すると、プログラムはキャッシュされていても各関数呼び出しを起動する必要があり、これらの関数呼び出しのすべてがスタックにすばやくフィードアップできますが、DP では関数内の配列テーブルをチェックし、再帰呼び出しのみを行います。 / 見つからない場合は反復関数。

私はここで正しいですか？または、何か不足していますか？

4

2 に答える 2

1

基本的に、「メモ化」の定義を制限しすぎていると思います。これは、実際には、以前に計算された結果を再計算するのではなく、保存するためのあらゆる手法です。そのため、前の最大nまでのすべての結果を保存するフィボナッチ計算はメモ化ですが、以前に計算された部分問題を保存する DP アルゴリズムも同様です。

(ウィキペディアの記事を参照してください。)

于 2012-07-30T04:38:43.153 に答える
1

動的プログラミングとメモ化は、相互に排他的ではなく、異なるアプローチでもありません。メモ化とは、関連するすべてのコンテキスト (パラメーター、呼び出しインスタンスなど) を含む関数呼び出しの結果を単に「記憶」することです。動的プログラミングでは、メモ化を使用して、特定のサブ問題の結果を 1 回だけ計算するという目標を達成します。

ウィキペディアから：

動的計画法のアプローチでは、各部分問題を 1 回だけ解こうとするため、計算回数が削減されます。特定の部分問題の解が計算されると、それは保存または「メモ化」されます。次に同じ解が必要になったときに、単に見上げられます。このアプローチは、繰り返されるサブ問題の数が入力のサイズの関数として指数関数的に増加する場合に特に役立ちます。

于 2012-07-30T04:45:55.437 に答える