5

アルゴリズムが動的計画法によって解決されるための 2 つの基準は、次のとおりです。

  1. サブ問題は独立している必要があります。
  2. サブ問題はオーバーラップする必要があります。

オーバーラップの意味が理解できたと思います。これは基本的に、サブ問題に同じサブサブ問題があることを意味します。したがって、サブサブ問題を何度も解決する代わりに、一度解決し、それをハッシュテーブルまたは配列に入れて、必要なネスト時間で検索できます。しかし、ポイント1、つまり部分問題の独立性はここで何を意味するのでしょうか? それらにいくつかの共通のサブサブ問題がある場合、どうすればそれらを独立していると呼ぶことができますか? つまり、この段階では直感に反するように聞こえるということです。

編集：この基準は、実際には有名な本に記載されています：動的プログラミングの章のCLRSによるアルゴリズムの紹介。

4

6 に答える 6

1

DP が重複する独立したサブ問題を含む問題に適用されることをどこで読んでいるのか教えてください。あなたが与えたのと同じ直感的な理由で、それは正しくないと思います.問題が重なると、それらは独立していません.

私は通常、分割統治スタイルのアルゴリズムの基準として与えられた独立した部分問題を見ますが、動的計画法ファミリーの基準として与えられた重複部分問題と最適な部分構造を見ます。(直観的に、最適な部分構造とは、より大きな問題の最良の解が、部分問題の最良の解から構成されることを意味します。典型的な例は、グラフ問題の最短経路です: A から B への最短経路が通過することがわかっている場合C の場合、C を通過する A から B への最短経路の一部が、たまたま A から C への最短経路であることもわかります。)

更新:ああ、わかりました-はい、彼らは独立について言及していると思います. しかし、私はあなたと同じ重点を置いてそれを読んでいません。つまり、彼らは、最適な下部構造のより大きく、より重要な概念のコンテキストで、または理解する方法として、独立性について言及しています。

独立性とは具体的には、2 つの問題が重なったとしても、それらが相互作用しないという意味で「独立している」ということです。一方の解決策は、他方の解決策に実際には依存しません。彼らは実際に私が行ったのと同じ例、最短経路を使用しています。最短経路問題のサブ問題は、独立したより小さな最短経路問題です。A から B への最短経路が C を通過する場合、A から C への最短経路は、C からB.対照的に、最長経路の問題は、サブ問題の独立性を共有しません。

CLRS が独立性を主張するのは間違っているとは思いませんが、CLRS が使用している言語は少しあいまいだと思います。

于 2012-09-05T16:34:51.480 に答える
0

重複と独立は一種の衝突する意味を持っているので、これらの基準はひどく表現されていると思います。

とにかく、あなたが持っている必要があるDPアプローチを効果的に使用できるようにするために

  1. より単純な問題の観点から再帰的に定義できる問題
  2. 残りの部分の解決策が現在のポイントに到達した方法に依存しない部分的な解決策の概念

例：最初の行から始まり、次の行に各ステップがあり、同じ列または隣接する列にあるマトリックス内を移動するときの最大合計パスを計算する場合は、現在の合計を「状態」として使用できます。 、現在の行と現在の列。これは、ソリューションでは、現在の位置に到達するために使用されたパスが何であったかは問題ではないためです。

1  4 [3] 2  1  4  9
2  1 [3] 1  2  3  1
9 [8] 3  0  1  2  9
0 [0] 2  4  1  6  3
1  2 [6] 3  0  4  1

上記のスキーマでは、このパスの合計は3 + 3 + 8 + 0+6です。合計を最大化するために、特定のポイントから通過するパスの最大値を、そこに到達するための最大値、およびそこからマトリックスの最後に到達するための最大値として取得できることがわかります。したがって、解は独立したサブ問題に分割でき、行列の特定のポイントから最後までの最大合計の結果をキャッシュできます（ポイントに到達した方法とは関係ありません）。

def maxsum(x, y):
    if (x, y) in cache:
        return cache[(x, y)]

    if y == height - 1:
        return matrix[y][x]

    if x == 0:
        left = -1
    else:
        left = matrix[y][x] + maxsum(x-1, y+1)

    center = matrix[y][x] + maxsum(x, y+1)

    if x == width-1:
        right = -1
    else:
        right = matrix[y][x] + maxsum(x+1, y+1)

    result = cache[(x, y)] = max(left, center, right)
    return result

ルールに3つ以下の「9」を追加すると、座標だけを状態として使用することはできません。これは、次のサブ問題（最後に行く）が前の問題（つまり、「9」の数）の影響を受けるためです。 「あなたはすでに中間の位置に着いている間に集めました）。

動的計画法のアプローチを引き続き使用できますが、たとえば、収集された「9」の数を現在の状態表現に追加することにより、状態空間を大きくすることができます。

def maxsum(x, y, number_of_nines):
    if (x, y, number_of_nines) in cache:
        return cache[(x, y, number_of_nines)]
    ...
于 2012-09-06T06:39:41.687 に答える