240

（動的計画法への）ボトムアップアプローチは、最初に「より小さな」サブ問題を調べ、次により小さな問題の解決策を使用してより大きなサブ問題を解決することから成ります。

トップダウンは、「自然な方法」で問題を解決し、以前にサブ問題の解決策を計算したことがあるかどうかを確認することで構成されます。

私は少し混乱しています。これら2つの違いは何ですか？

4

8 に答える 8

292

rev4：ユーザーSammaronによる非常に雄弁なコメントは、おそらく、この回答は以前はトップダウンとボトムアップを混同していたと述べています。もともとこの回答（rev3）と他の回答は「ボトムアップはメモ化」（「サブ問題を想定」）と言っていましたが、逆の場合もあります（つまり、「トップダウン」は「サブ問題を想定」と「ボトムアップ」は「サブ問題を構成する」かもしれません）。以前、メモ化は動的計画法のサブタイプとは対照的に、別の種類の動的計画法であることを読みました。購読していなくても、その視点を引用していました。適切な参考文献が文献に見つかるまで、この回答を用語にとらわれないように書き直しました。また、この回答をコミュニティWikiに変換しました。学術的な情報源を優先してください。参考文献一覧：} {文学：5 }

要約

動的計画法とは、重複する作業の再計算を回避する方法で計算を順序付けることです。主な問題（サブ問題のツリーのルート）とサブ問題（サブツリー）があります。サブ問題は通常、繰り返されて重複します。

たとえば、Fibonnaciのお気に入りの例を考えてみましょう。これは、単純な再帰呼び出しを行った場合のサブ問題の完全なツリーです。

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)、... etc ...を呼び出し、。を呼び出します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）スタックを仮想化するために一定の余分な作業を消費する（ick）、

より複雑な例

ここでは、一般的なDPの問題だけでなく、メモ化と集計を興味深い方法で区別する、特に興味深い例を示します。たとえば、一方の定式化がもう一方の定式化よりもはるかに簡単な場合や、基本的に集計が必要な最適化がある場合があります。

  • edit-distance [ 4 ]を計算するアルゴリズム。これは、2次元のテーブル入力アルゴリズムの重要な例として興味深いものです。
于 2011-05-29T00:00:00.867 に答える
92

トップダウンとボトムアップのDPは、同じ問題を解決する2つの異なる方法です。フィボナッチ数を計算するためのメモ化された（トップダウン）プログラミングソリューションと動的な（ボトムアップ）プログラミングソリューションを考えてみましょう。

fib_cache = {}

def memo_fib(n):
  global fib_cache
  if n == 0 or n == 1:
     return 1
  if n in fib_cache:
     return fib_cache[n]
  ret = memo_fib(n - 1) + memo_fib(n - 2)
  fib_cache[n] = ret
  return ret

def dp_fib(n):
   partial_answers = [1, 1]
   while len(partial_answers) <= n:
     partial_answers.append(partial_answers[-1] + partial_answers[-2])
   return partial_answers[n]

print memo_fib(5), dp_fib(5)

個人的には、メモ化の方がはるかに自然だと思います。再帰関数を取得し、機械的なプロセスでメモ化することができます（最初にキャッシュで回答を検索し、可能であればそれを返します。それ以外の場合は再帰的に計算し、戻る前に、将来の使用のために計算をキャッシュに保存します）。動的計画法では、解決策が計算される順序をエンコードする必要があります。これにより、依存する小さな問題の前に「大きな問題」が計算されなくなります。

于 2011-05-28T22:34:07.997 に答える
27

動的計画法の重要な機能は、重複するサブ問題の存在です。つまり、解決しようとしている問題はサブ問題に分割でき、それらのサブ問題の多くはサブサブ問題を共有します。それは「分割統治」のようなものですが、あなたは同じことを何度も何度もやることになります。これらの問題を教えたり説明したりするときに2003年から使用した例：フィボナッチ数を再帰的に計算できます。

def fib(n):
  if n < 2:
    return n
  return fib(n-1) + fib(n-2)

お気に入りの言語を使用して、実行してみてくださいfib(50)。非常に長い時間がかかります。それ自体とほぼ同じくらいの時間fib(50)！しかし、多くの不必要な作業が行われています。とfib(50)を呼び出しますが、値が同じであっても、両方ともを呼び出すことになります。実際、は3回計算されます。からの直接呼び出し、からの直接呼び出し、および別のからの直接呼び出しによって、 ...の計算によって生成されたものです。ご覧のとおり、重複するサブ問題があります。 。fib(49)fib(48)fib(47)fib(47)fib(49)fib(48)fib(48)fib(49)

すばらしいニュース：同じ値を何度も計算する必要はありません。一度計算したら結果をキャッシュし、次回はキャッシュされた値を使用します。これが動的計画法の本質です。これは、「トップダウン」、「メモ化」、またはその他の任意の名前で呼び出すことができます。このアプローチは非常に直感的で、実装が非常に簡単です。最初に再帰的なソリューションを作成し、小さなテストでテストし、メモ化（すでに計算された値のキャッシュ）を追加して、---ビンゴ！---これで完了です。

通常、再帰なしでボトムアップで動作する同等の反復プログラムを作成することもできます。この場合、これはより自然なアプローチになります。1から50までループして、すべてのフィボナッチ数を計算します。

fib[0] = 0
fib[1] = 1
for i in range(48):
  fib[i+2] = fib[i] + fib[i+1]

興味深いシナリオでは、ボトムアップソリューションは通常理解するのがより困難です。ただし、それを理解すると、通常、アルゴリズムがどのように機能するかについて、はるかに明確な全体像を把握できます。実際には、重要な問題を解決するときは、最初にトップダウンのアプローチを作成し、小さな例でテストすることをお勧めします。次に、ボトムアップソリューションを作成し、2つを比較して、同じものが得られることを確認します。理想的には、2つのソリューションを自動的に比較します。多くのテストを生成する小さなルーチンを作成します。理想的には、すべて特定のサイズまでの小規模なテスト---そして両方のソリューションが同じ結果をもたらすことを検証します。その後、本番環境でボトムアップソリューションを使用しますが、トップボトムコードはそのままにしてコメントアウトします。これにより、他の開発者が自分が何をしているのかを理解しやすくなります。ボトムアップコードは、自分が書いたものであっても、自分が何をしているのかを正確に知っていても、まったく理解できない場合があります。

多くのアプリケーションでは、再帰呼び出しのオーバーヘッドのため、ボトムアップアプローチの方がわずかに高速です。スタックオーバーフローも特定の問題で問題になる可能性があり、これは入力データに大きく依存する可能性があることに注意してください。動的計画法を十分に理解していないと、スタックオーバーフローを引き起こすテストを記述できない場合がありますが、いつかはそれでも発生する可能性があります。

現在、問題スペースが非常に大きいため、すべてのサブ問題を解決することができないため、トップダウンアプローチが唯一の実行可能な解決策であるという問題があります。ただし、入力に必要なサブ問題のごく一部しか解決できないため、「キャッシング」は妥当な時間内に機能します。ただし、どのサブ問題を解決する必要があるかを明示的に定義するのは難しいため、ボトムを記述します。ソリューションをアップします。一方、すべてのサブ問題を解決する必要があることがわかっている場合もあります。この場合、続けてボトムアップを使用します。

私は個人的に段落最適化、別名ワードラップ最適化問題に上から下を使用します（Knuth-Plassの改行アルゴリズムを調べてください。少なくともTeXはそれを使用し、Adobe Systemsの一部のソフトウェアは同様のアプローチを使用します）。高速フーリエ変換にはボトムアップを使用します。

于 2013-10-07T01:38:37.833 に答える
25

例としてフィボナッチ数列を取り上げましょう

1,1,2,3,5,8,13,21....

first number: 1
Second number: 1
Third Number: 2

別の言い方をすれば、

Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21

最初の5つのフィボナッチ数の場合

Bottom(first) number :1
Top (fifth) number: 5

次に、例として再帰的なフィボナッチ数列アルゴリズムを見てみましょう。

public int rcursive(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        return rcursive(n - 1) + rcursive(n - 2);
    }
}

次のコマンドでこのプログラムを実行すると

rcursive(5);

アルゴリズムを詳しく調べると、5番目の数値を生成するには、3番目と4番目の数値が必要です。したがって、私の再帰は実際にはtop（5）から始まり、次に下/下の数値まで続きます。このアプローチは、実際にはトップダウンアプローチです。

同じ計算を複数回行わないようにするために、動的計画法の手法を使用します。以前に計算された値を保存して再利用します。この手法はメモ化と呼ばれます。動的計画法には、現在の問題を議論するために必要のないメモ化以外にもあります。

トップダウン

元のアルゴリズムを書き直して、メモ化された手法を追加しましょう。 

public int memoized(int n, int[] memo) {
    if (n <= 2) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo);
    }
    return memo[n];
}

そして、このメソッドを次のように実行します

   int n = 5;
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    memoized(n, memo);

このソリューションは、アルゴリズムがトップ値から開始し、各ステップのボトムに進んでトップ値を取得するため、依然としてトップダウンです。

一気飲み

しかし、問題は、最初のフィボナッチ数から始めて、上に向かって歩くことができるかということです。このテクニックを使って書き直してみましょう。

public int dp(int n) {
    int[] output = new int[n + 1];
    output[1] = 1;
    output[2] = 1;
    for (int i = 3; i <= n; i++) {
        output[i] = output[i - 1] + output[i - 2];
    }
    return output[n];
}

ここで、このアルゴリズムを調べると、実際には低い値から開始し、次に上に移動します。5番目のフィボナッチ数が必要な場合は、実際に1番目を計算し、次に2番目、次に3番目を計算して5番目の数を増やします。この手法は、実際にはボトムアップ手法と呼ばれます。

最後の2つは、アルゴリズムが動的計画法の要件を完全に満たすものです。しかし、1つはトップダウンで、もう1つはボトムアップです。どちらのアルゴリズムも、同様の空間と時間の複雑さを持っています。

于 2015-02-23T08:29:46.880 に答える
4

動的計画法は、メモ化と呼ばれることがよくあります。

1.メモ化はトップダウン手法（特定の問題を分解して解決を開始）であり、動的計画法はボトムアップ手法（些細なサブ問題から特定の問題に向かって解決を開始）です。

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

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

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

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

それどころか、メモ化は再帰による（多くの場合重要な）オーバーヘッドを支払う必要があります。

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

于 2013-08-20T18:20:12.263 に答える
3

トップダウンアプローチはサブ問題を何度も呼び出すために再帰を使用します
が、ボトムアップアプローチは誰も呼び出さずにシングルを使用するため、より効率的です。

于 2015-07-22T12:18:18.303 に答える
3

動的計画法の問題は、ボトムアップまたはトップダウンのアプローチを使用して解決できます。

一般に、ボトムアップアプローチは集計手法を使用しますが、トップダウンアプローチは再帰（記憶あり）手法を使用します。

ただし、以下に示すように、再帰を使用してボトムアップおよびトップダウンのアプローチをとることもできます。

Bottom-Up：基本条件から開始し、これまでに計算された値を再帰的に渡します。一般に、これらは末尾再帰です。

int n = 5;
fibBottomUp(1, 1, 2, n);

private int fibBottomUp(int i, int j, int count, int n) {
    if (count > n) return 1;
    if (count == n) return i + j;
    return fibBottomUp(j, i + j, count + 1, n);
}

トップダウン：最終条件から開始し、そのサブ問題の結果を再帰的に取得します。

int n = 5;
fibTopDown(n);

private int fibTopDown(int n) {
    if (n <= 1) return 1;
    return fibTopDown(n - 1) + fibTopDown(n - 2);
}
于 2020-01-03T01:55:25.483 に答える
1

以下は、トップダウンの距離編集問題のDPベースのソリューションです。動的計画法の世界を理解するのにも役立つことを願っています。

public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle.
         int m = word2.length();
            int n = word1.length();


     if(m == 0) // Cannot miss the corner cases !
                return n;
        if(n == 0)
            return m;
        int[][] DP = new int[n + 1][m + 1];

        for(int j =1 ; j <= m; j++) {
            DP[0][j] = j;
        }
        for(int i =1 ; i <= n; i++) {
            DP[i][0] = i;
        }

        for(int i =1 ; i <= n; i++) {
            for(int j =1 ; j <= m; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1))
                    DP[i][j] = DP[i-1][j-1];
                else
                DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this.
            }
        }

        return DP[n][m];
}

あなたはあなたの家でその再帰的な実装を考えることができます。これまでにこのような問題を解決したことがない場合は、非常に優れており、やりがいがあります。

于 2016-06-25T20:53:04.413 に答える