286

動的計画法とは

再帰やメモ化などとどう違うのですか?

ウィキペディアの記事を読みましたが、まだよくわかりません。

4

10 に答える 10

219

動的計画法とは、過去の知識を使用して、将来の問題をより簡単に解決できるようにすることです。

良い例は、n=1,000,002 のフィボナッチ数列を解くことです。

これは非常に長いプロセスになりますが、n=1,000,000 と n=1,000,001 の結果を示したらどうでしょうか? 突然、問題がより扱いやすくなりました。

動的計画法は、文字列編集問題などの文字列の問題でよく使用されます。問題のサブセットを解決し、その情報を使用して、より困難な元の問題を解決します。

動的計画法では、通常、結果をある種のテーブルに格納します。問題に対する答えが必要な場合は、表を参照して、それが何であるかを既に知っているかどうかを確認します。そうでない場合は、テーブル内のデータを使用して、答えへの足がかりを自分自身に与えます。

Cormen Algorithms の本には、動的計画法に関する素晴らしい章があります。そして、Google ブックスでは無料です。ここで確認してください。

于 2009-06-30T19:12:37.430 に答える
39

メモ化とは、関数呼び出しの以前の結果を保存するときです（実際の関数は、同じ入力が与えられると、常に同じものを返します）。結果が保存される前は、アルゴリズムの複雑さには違いはありません。

再帰は、通常は小さいデータセットを使用して、関数がそれ自体を呼び出す方法です。ほとんどの再帰関数は同様の反復関数に変換できるため、これによってアルゴリズムの複雑さにも違いはありません。

動的計画法は、解決しやすいサブ問題を解決し、そこから答えを構築するプロセスです。ほとんどのDPアルゴリズムは、貪欲アルゴリズム（存在する場合）と指数アルゴリズム（すべての可能性を列挙して最適なアルゴリズムを見つける）の間の実行時間になります。

  • DPアルゴリズムは再帰的に実装できますが、必ずしもそうする必要はありません。
  • 各サブ問題は一度しか解決されない（または「解決」関数が呼び出される）ため、メモ化によってDPアルゴリズムを高速化することはできません。
于 2009-06-30T19:51:55.510 に答える
24

これは、実行時間を短縮するアルゴリズムの最適化です。

欲張りアルゴリズムは通常ナイーブと呼ばれますが、同じデータセットに対して複数回実行される可能性があるため、動的計画法は、最終的なソリューションの構築を支援するために保存する必要のある部分的な結果をより深く理解することで、この落とし穴を回避します。

簡単な例は、ソリューションに寄与するノードのみを介してツリーまたはグラフをトラバースするか、同じノードを何度もトラバースすることを回避できるように、これまでに見つけたソリューションをテーブルに配置することです。

これは、UVAのオンラインジャッジからの動的計画法に適した問題の例です：EditStepsLadder。

この問題の分析の重要な部分について、プログラミングの課題という本から抜粋して簡単に説明します。ぜひチェックしてみてください。

その問題をよく見てください。2つの文字列がどれだけ離れているかを示すコスト関数を定義すると、3つの自然なタイプの変化を2つ考慮する必要があります。

置換-「ショット」を「スポット」に変更するなど、単一の文字をパターン「s」からテキスト「t」の別の文字に変更します。

挿入-「ago」を「agog」に変更するなど、テキスト「t」と一致するようにパターン「s」に単一の文字を挿入します。

削除-パターン「s」から1文字を削除して、「hour」を「our」に変更するなど、テキスト「t」と一致させるようにします。

この各操作のコストを1ステップに設定する場合、2つの文字列間の編集距離を定義します。では、どのように計算しますか？

文字列の最後の文字が一致、置換、挿入、または削除される必要があるという観察結果を使用して、再帰的アルゴリズムを定義できます。最後の編集操作で文字を切り落とすと、ペア操作が残り、小さな文字列のペアが残ります。iとjを、それぞれ関連する接頭辞とtの最後の文字とします。最後の操作の後に3組の短い文字列があり、一致/置換、挿入、または削除の後の文字列に対応します。小さい文字列の3つのペアを編集するコストがわかっている場合は、どのオプションが最適なソリューションにつながるかを判断し、それに応じてそのオプションを選択できます。再帰という素晴らしいことを通して、このコストを学ぶことができます。

#define MATCH 0 /* enumerated type symbol for match */
#define INSERT 1 /* enumerated type symbol for insert */
#define DELETE 2 /* enumerated type symbol for delete */


int string_compare(char *s, char *t, int i, int j)

{

    int k; /* counter */
    int opt[3]; /* cost of the three options */
    int lowest_cost; /* lowest cost */
    if (i == 0) return(j * indel(’ ’));
    if (j == 0) return(i * indel(’ ’));
    opt[MATCH] = string_compare(s,t,i-1,j-1) +
      match(s[i],t[j]);
    opt[INSERT] = string_compare(s,t,i,j-1) +
      indel(t[j]);
    opt[DELETE] = string_compare(s,t,i-1,j) +
      indel(s[i]);
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
    if (opt[k] < lowest_cost) lowest_cost = opt[k];
    return( lowest_cost );

}

このアルゴリズムは正しいですが、非常に遅いです。

私たちのコンピューターで実行すると、2つの11文字の文字列を比較するのに数秒かかり、計算が消えて、これ以上何にも到達しなくなります。

なぜアルゴリズムがとても遅いのですか？値を何度も何度も再計算するため、指数関数的な時間がかかります。文字列内のすべての位置で、再帰は3つの方法で分岐します。つまり、再帰は少なくとも3 ^ nの割合で増加します。実際、ほとんどの呼び出しは2つのインデックスの両方ではなく、一方のみを削減するため、さらに高速になります。

では、どうすればアルゴリズムを実用的にすることができるでしょうか？重要な観察は、これらの再帰呼び出しのほとんどは、以前に計算されたものを計算しているということです。どうやって知るの？ええと、|s|しかありえません ・| t | 再帰呼び出しのパラメーターとして機能する別個の（i、j）ペアが非常に多いため、一意の再帰呼び出しが可能です。

これらの（i、j）ペアのそれぞれの値をテーブルに格納することで、それらの再計算を回避し、必要に応じて検索することができます。

この表は2次元行列mであり、各| s |・| t | セルには、このサブ問題の最適なソリューションのコストと、この場所に到達した方法を説明する親ポインターが含まれています。

typedef struct {
int cost; /* cost of reaching this cell */
int parent; /* parent cell */
} cell;

cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */

動的計画法バージョンには、再帰バージョンとの3つの違いがあります。

まず、再帰呼び出しの代わりにテーブルルックアップを使用して中間値を取得します。

**次に、**各セルの親フィールドを更新します。これにより、後で編集シーケンスを再構築できます。

** 3番目、** 3番目は、cell()m [| s |] [| t |] .costを返すだけでなく、より一般的な目標関数を使用して計測されます。これにより、このルーチンをより幅広いクラスの問題に適用できるようになります。

ここで、最適な部分的な結果を収集するために必要なものの非常に特殊な分析は、ソリューションを「動的」なものにするものです。

これは、同じ問題に対する代替の完全な解決策です。実行方法は異なりますが、「動的」なものでもあります。UVAのオンライン審査員に提出して、ソリューションがどれほど効率的かを確認することをお勧めします。このような重い問題がいかに効率的に取り組まれたかは驚くべきことです。

于 2009-06-30T19:21:14.013 に答える
15

動的計画法の重要なビットは、「重複部分問題」と「最適な部分構造」です。問題のこれらの特性は、最適解がそのサブ問題に対する最適解から構成されることを意味します。たとえば、最短経路問題は最適な部分構造を示します。A から C への最短パスは、A からノード B への最短パスであり、その後にそのノード B から C への最短パスが続きます。

より詳細には、最短経路の問題を解決するには、次のことを行います。

  • 開始ノードからそれに接触するすべてのノードまでの距離を見つけます（たとえば、AからBおよびCまで）
  • それらのノードからそれらに接触しているノードまでの距離を見つけます (B から D および E まで、および C から E および F まで)
  • これで、A から E への最短経路がわかります。これは、訪れたノード x (B または C) の Ax と xE の最短の合計です。
  • 最終的な宛先ノードに到達するまで、このプロセスを繰り返します

私たちはボトムアップで作業しているため、サブ問題を使用するときが来たら、それらをメモ化することで、サブ問題の解決策をすでに持っています。

動的計画法の問題には、重複する部分問題と最適な部分構造の両方が必要です。フィボナッチ数列の生成は、動的計画法の問題ではありません。重複する部分問題があるためメモ化を利用しますが、最適な部分構造はありません (最適化問題が含まれていないため)。

于 2009-06-30T19:42:41.240 に答える
8

動的計画法

意味

動的計画法 (DP) は、サブ問題が重複する問題を解決するための一般的なアルゴリズム設計手法です。この手法は、1950年代にアメリカの数学者「リチャード・ベルマン」によって発明されました。

重要なアイデア

重要なアイデアは、再計算を避けるために、重複する小さなサブ問題の答えを保存することです。

動的計画法プロパティ

  • インスタンスは、小さいインスタンスのソリューションを使用して解決されます。
  • 小規模なインスタンスのソリューションは複数回必要になる可能性があるため、結果をテーブルに保存します。
  • したがって、それぞれの小さいインスタンスは 1 回だけ解決されます。
  • 時間を節約するために追加のスペースが使用されます。
于 2015-09-06T03:44:54.507 に答える
6

私はまた、動的計画法 (特定の種類の問題に対する強力なアルゴリズム) も初めて使用します。

簡単に言えば、動的プログラミングは、以前の知識を使用した再帰的アプローチと考えてください。

ここで最も重要なのは以前の知識です。すでに持っているサブ問題の解決策を追跡してください。

ウィキペディアの dp の最も基本的な例を考えてみましょう

フィボナッチ数列を見つける

function fib(n)   // naive implementation
    if n <=1 return n
    return fib(n − 1) + fib(n − 2)

関数呼び出しを n = 5 と分解してみましょう

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

特に、 fib(2) はゼロから 3 回計算されました。より大きな例では、fib またはサブ問題のより多くの値が再計算され、指数時間アルゴリズムにつながります。

それでは、マップなどのデータ構造に既に見つけた値を格納して試してみましょう。

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

ここでは、副問題の解をマップに保存します (まだ持っていない場合)。すでに計算した値を保存するこの手法は、メモ化と呼ばれます。

最後に、問題の場合、まず状態を見つけようとします (可能な副問題と、前の副問題の解決策をさらに別の問題に使用できるように、より良い再帰アプローチを考えてみてください)。

于 2015-06-01T19:24:13.300 に答える