63

Possible Duplicate:
Dynamic programming and memoization: top-down vs bottom-up approaches

I have gone through a lot of articles on this but can't seem to make sense of it. At times recursion and dynamic programming looks the same and at others memoization & dynamic programming look alike. Can someone explain to me what's the difference?

P.S. It will also be helpful if you could point me to some code using the three approaches on the same problem. (e.g. the Fibonacci series problem, I think every article I read used recursion but referred to it as dynamic programming)

4

5 に答える 5

72

フィボナッチ数列の計算を検討してください。

純粋な再帰:

int fib(int x)
{
    if (x < 2)
        return 1;

    return fib(x-1) + fib(x-2);
}

呼び出しの指数関数的な数になります。

メモ化/DPによる再帰:

int fib(int x)
{
    static vector<int> cache(N, -1);

    int& result = cache[x];

    if (result == -1)
    {
        if (x < 2)
            result = 1;
        else
            result = fib(x-1) + fib(x-2);
    }

    return result;
}

これで、最初は線形の呼び出し数になり、その後は一定になります。

上記の方法は「レイジー」と呼ばれます。最初に求められたときに、以前の条件を計算します。

以下も DP と見なされますが、再帰はありません。

int fibresult[N];

void setup_fib()
{
    fibresult[0] = 1;
    fibresult[1] = 1;
    for (int i = 2; i < N; i++)
       fibresult[i] = fibresult[i-1] + fibresult[i-2];
}

int fib(int x) { return fibresult[x]; }

この方法は、「イーガー」、「プリキャッシング」、または「反復的」と表現される場合があります。全体的には高速ですが、部分問題を計算する必要がある順序を手動で把握する必要があります。これはフィボナッチでは簡単ですが、より複雑な DP 問題では難しくなるため、高速な場合は遅延再帰法にフォールバックします。足りる。

また、以下は再帰でも DP でもありません。

int fib(int x)
{
    int a = 1;
    int b = 1;
    for (int i = 2; i < x; i++)
    {
        a = a + b;
        swap(a,b);
    }
    return b;
}

一定の空間と線形時間を使用します。

また、完全を期すために、ネザー再帰または DP を使用するフィボナッチの閉じた形式があり、黄金比に基づく数式を使用してフィボナッチ項を一定時間で計算できることについて言及します。

http://www.dreamincode.net/forums/topic/115550-fibonacci-closed-form/

于 2012-08-26T22:18:04.910 に答える
42

再帰+メモ化は、まさに動的計画法の特定の「フレーバー」です。トップダウンアプローチに従った動的計画法です。

より正確には、再帰を具体的に使用する必要はありません。メモ化と組み合わせた分割統治ソリューションは、トップダウンの動的計画法です。（再帰は分割統治のLIFOフレーバーですが、FIFO分割統治または他の種類の分割統治を使用することもできます）。

だから、それを言うのがより正しいです

divide & conquer + memoization == top-down dynamic programming

また、非常に形式的な観点から、反復部分解を生成しない問題に対して分割統治法を実装する場合（つまり、メモ化にメリットがない場合）、この分割統治法は「動的計画法」の縮退例。

ただし、動的計画法はより一般的な概念です。動的計画法では、分割統治+メモ化とは異なるボトムアップアプローチを使用できます。

于 2012-08-26T21:54:45.007 に答える
19

インターネットで詳細な定義を見つけることができると確信しています。これが物事を単純化する私の試みです。

再帰は再び自分自身を呼び出しています。

動的計画法は、問題を元の問題に似たサブ問題に分解できる特定の構造 (最適なサブ構造) を示す問題を解決する方法です。明らかに、DP を解決するために再帰を呼び出すことができます。しかし、それは必要ではありません。再帰なしで DP を解くことができます。

メモ化は、再帰に依存する DP アルゴリズムを最適化する方法です。ポイントは、すでに解決されたサブ問題を再度解決しないことです。サブ問題の解決策のキャッシュとして表示できます。

于 2012-08-26T20:56:07.847 に答える
9

それらは異なる概念です。それらはかなり頻繁に重なりますが、異なります。

再帰は、関数が直接または間接的にそれ自体を呼び出すたびに発生します。これですべてです。

例：

a -> call a
a -> call b, b -> call c, c -> call a

動的計画法は、より大きな問題を解決するために、より小さなサブ問題の解決策を使用する場合です。通常、このようなソリューションは再帰関数の観点から考えるため、これは再帰的に実装するのが最も簡単です。ただし、時間とメモリが少なくて済むため、通常は反復実装が推奨されます。

メモ化は、再帰的なDPの実装に必要以上の時間がかかるのを防ぐために使用されます。ほとんどの場合、DPアルゴリズムは、複数の大きな問題を解決する際に同じサブ問題を使用します。再帰的な実装では、これは同じことを複数回再計算することを意味します。メモ化とは、これらのサブ問題の結果をテーブルに保存することを意味します。再帰呼び出しを入力するとき、その結果がテーブルに存在するかどうかを確認します。存在する場合はそれを返し、存在しない場合は計算してテーブルに保存してから返します。

于 2012-08-26T23:09:24.587 に答える
-5

再帰は、メモ化や動的プログラミングとはまったく関係ありません。それは完全に別の概念です。

それ以外の場合、これは重複した質問です:動的プログラミングとメモ化: ボトムアップとトップダウンのアプローチ

于 2012-08-26T20:46:02.723 に答える