196

分割統治アルゴリズムと動的計画法アルゴリズムの違いは何ですか？2つの用語はどのように異なりますか？違いがわかりません。

簡単な例を挙げて、2つの違いと、それらがどのような理由で類似しているように見えるかを説明してください。

4

9 に答える 9

197

分割統治

分割統治法は、問題をサブ問題に分割し、各サブ問題を再帰的に克服し、これらのソリューションを組み合わせることによって機能します。

動的計画法

動的計画法は、サブ問題が重複している問題を解決するための手法です。各サブ問題は1回だけ解決され、各サブ問題の結果は、将来の参照用にテーブル（通常は配列またはハッシュテーブルとして実装されます）に格納されます。これらのサブソリューションは、元のソリューションを取得するために使用でき、サブ問題ソリューションを保存する手法はメモ化として知られています。

あなたは考えるかもしれませんDP = recursion + re-use

違いを理解するための典型的な例は、n番目のフィボナッチ数を取得するためのこれら両方のアプローチを確認することです。MITからのこの資料を確認してください。

分割統治法 分割統治法

動的計画法アプローチ ここに画像の説明を入力してください

于 2012-11-24T05:55:16.343 に答える
29

分割統治法と動的計画法のその他の違いは次のとおりです。

分割統治：

  1. サブ問題により多くの作業を行うため、より多くの時間が消費されます。
  2. 分割統治では、サブ問題は互いに独立しています。

動的計画法:

  1. サブ問題を 1 回だけ解決し、それをテーブルに格納します。
  2. 動的計画法では、部分問題は独立していません。
于 2013-03-26T12:39:59.737 に答える
18

再帰的にプログラミングする場合、同じパラメータを使用して関数を複数回呼び出すことがありますが、これは不要です。

有名な例のフィボナッチ数：

           index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...

function F(n) {
    if (n < 3)
        return 1
    else
        return F(n-1) + F(n-2)
}

F（5）を実行してみましょう：

F(5) = F(4) + F(3)
     = {F(3)+F(2)} + {F(2)+F(1)}
     = {[F(2)+F(1)]+1} + {1+1}
     = 1+1+1+1+1

したがって、次のように呼びます。1回F（4）2回F（3）3回F（2）2回F（1）

動的計画法のアプローチ：同じパラメーターを使用して関数を複数回呼び出す場合は、結果を変数に保存して、次回に直接アクセスできるようにします。反復的な方法：

if (n==1 || n==2)
    return 1
else
    f1=1, f2=1
    for i=3 to n
         f = f1 + f2
         f1 = f2
         f2 = f

もう一度F（5）を呼び出しましょう：

fibo1 = 1
fibo2 = 1 
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5

ご覧のとおり、複数の呼び出しが必要な場合は常に、対応する変数にアクセスして、値を再計算するのではなく取得します。

ちなみに、動的計画法は、再帰的なコードを反復的なコードに変換することを意味するものではありません。再帰的なコードが必要な場合は、サブ結果を変数に保存することもできます。この場合、この手法はメモ化と呼ばれます。この例では、次のようになります。

// declare and initialize a dictionary
var dict = new Dictionary<int,int>();
for i=1 to n
    dict[i] = -1

function F(n) {
    if (n < 3)
        return 1
    else
    {
        if (dict[n] == -1)
            dict[n] = F(n-1) + F(n-2)

        return dict[n]                
    }
}

したがって、分割統治法との関係は、D＆Dアルゴリズムが再帰に依存しているということです。そして、それらのいくつかのバージョンには、この「同じパラメーターの問題を持つ複数の関数呼び出し」があります。D＆DアルゴリズムのT（n）を改善するためにDPが必要な例については、「行列の連鎖乗積」と「最長共通部分列」を検索してください。

于 2012-11-24T05:45:55.287 に答える
11

これについては、ウィキペディアやその他の学術リソースを既に読んでいると思いますので、その情報を再利用することはしません。また、私は決してコンピュータ サイエンスの専門家ではないことを強調しておく必要がありますが、これらのトピックについての私の理解について 2 セントを共有します...

動的計画法

問題を個別のサブ問題に分割します。フィボナッチ数列の再帰アルゴリズムは、最初に fib(n-1) を解くことによって fib(n) を解くため、動的計画法の一例です。元の問題を解決するために、別の問題を解決します。

分割統治

これらのアルゴリズムは通常、問題の同様の部分を解決し、最後にそれらをまとめます。マージソートは、分割統治の典型的な例です。この例とフィボナッチの例の主な違いは、マージソートでは分割が (理論的には) 任意であり、どのように分割してもマージとソートが行われることです。分割方法に関係なく、配列をマージソートするには、同じ量の作業を行う必要があります。fib(52) を解くには、fib(2) を解くよりも多くの手順が必要です。

于 2012-11-24T05:21:02.527 に答える
8

私はDivide & Conquer再帰的なアプローチとDynamic Programmingテーブルの塗りつぶしと考えています。

たとえばMerge Sort、Divide & Conquerアルゴリズムです。各ステップでは、配列を 2 つの半分に分割し、2 つの半分を再帰的に呼び出しMerge Sortてからマージします。

Knapsackナップザック全体Dynamic Programmingの部分問題に対する最適解を表すテーブルを埋めるアルゴリズムです。表の各エントリは、アイテム 1 ～ j を指定して、重量 w のバッグで運ぶことができる最大値に対応しています。

于 2012-11-24T05:21:48.863 に答える