7

動的プログラミングに関するメモを読んでいたところ、次のコメントに遭遇しました。

サブ問題が独立していない場合、つまりサブ問題がサブサブ問題を共有している場合、分割統治アルゴリズムは共通のサブサブ問題を繰り返し解決します。したがって、必要以上の作業を行います

これは何を意味するのでしょうか ？上記の点を明確にするために例を挙げていただけますか?

4

1 に答える 1

14

著者は、多くの分割統治アルゴリズムには互いに重複する部分問題があるという事実に言及しています。たとえば、次の非常に単純なフィボナッチの実装を考えてみましょう。

int Fibonacci(int n) {
    if (n <= 1) return n;

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(4) を計算するために行われた呼び出しを追跡すると、次のようになります。

  • Fibonacci(4) は Fibonacci(3) と Fibonacci(2) を呼び出します
  • Fibonacci(3) は Fibonacci(2) と Fibonacci(1) を呼び出します
  • Fibonacci(2) は Fibonacci(1) と Fibonacci(0) を呼び出します
  • Fibonacci(2) (もう一方) は Fibonacci(1) と Fibonacci(0) を呼び出します
  • Fibonacci(1) は終了します。
  • Fibonacci(1) は終了します。
  • Fibonacci(1) は終了します。
  • フィボナッチ(0)は終了します。
  • フィボナッチ(0)は終了します。

つまり、合計 9 回の関数呼び出しが行われますが、固有の呼び出しは 5 回だけです (0 から 4 までのフィボナッチ数)。このアルゴリズムは、毎回ゼロから再計算するのではなく、部分問題全体で再帰呼び出しを共有すれば、はるかに効率的になる可能性があります。これは、動的計画法の背後にある重要なアイデアの 1 つです。

F n (n 番目のフィボナッチ数)を計算するために、上記のコードは合計 2F n+1 - 1 回の再帰呼び出しを行います。フィボナッチ数は指数関数的に急速に増加するため、これには指数関数的に多くの作業が必要です。しかし、多くの再帰呼び出しが同一であるという事実を利用して、これを劇的に単純化することができます。Fibonacci(4) から始めて下に進むのではなく、Fibonacci(0) から始めて上に進みましょう。具体的には、長さ 5 のテーブル (FTable と呼びましょう) を作成し、次のように入力します。

  • Fテーブル[0] = 0
  • Fテーブル[1] = 1

ここで、FTable[2] を計算したいとします。これには、FTable[0] と FTable[1] を知る必要がありますが、それらはテーブルにあるため、既にわかっています。したがって、設定できます

  • F テーブル [2] = 1

同様のロジックを使用して、FTable[2] と FTable[1] から FTable[3] を計算できます。

  • Fテーブル[3] = 2

FTable[2] と FTable[3] からの FTable[4]:

  • Fテーブル[4] = 3

逆の順序で再帰呼び出しを構築するだけで、多くの重複する再帰呼び出しを回避する方法に注目してください! これにより、時間 O(n) でフィボナッチ数が計算されるようになり、以前より指数関数的に高速になりました。より高度な数学を使用すると、これよりもさらに優れたことができますが、これは、動的計画法が実行不可能な問題を突然実行可能にする理由を示しています。

お役に立てれば！

于 2012-01-24T04:27:03.333 に答える