41

私は動的計画法の原理を理解することができず、本当にそれを望んでいます。DPは非常に強力で、次のような問題を解決できます。

数値の差から可能な限り低い合計を取得する

それで、動的計画法とは何かを説明する良い本や記事（できれば実際のコードを使った例を含む）を提案してもらえますか？まず最初に簡単な例が欲しいので、次に進みます。

4

14 に答える 14

34

動的計画法は、難しい問題を小さなサブ問題に分割することで最適化するために使用できる便利なタイプのアルゴリズムです。部分的なソリューションを保存して再利用することにより、欲張りアルゴリズムを使用する際の落とし穴を回避できます。動的計画法には、ボトムアップとトップダウンの2種類があります。

動的計画法を使用して問題を解決できるようにするには、問題はいわゆる最適部分構造の特性を備えている必要があります。これは、問題が一連のサブ問題に分割され、各サブ問題の最適な解決策が見つかった場合、結果の解決策はこれらのサブ問題の解決策を通じて実現されることを意味します。この構造を持たない問題は、動的計画法では解決できません。

トップダウン

トップダウンはメモ化としてよく知られています。毎回再計算しないように、過去の計算を保存するという考え方です。

再帰関数が与えられた場合、次のように言います。

fib(n) = 0 if n = 0
         1 if n = 1
         fib(n - 1) + fib(n - 2) if n >= 2

これは、数学的な形式から次のように簡単に再帰的に記述できます。

function fib(n)
  if(n == 0 || n == 1)
    n
  else
    fib(n-1) + fib(n-2)

さて、しばらくプログラミングをしている人や、アルゴリズムの効率について1つか2つ知っている人なら誰でも、これはひどい考えだと言うでしょう。その理由は、各ステップで、fib（i）の値を再計算する必要があるためです。ここで、iは2..n-2です。

このより効率的な例は、これらの値を格納し、トップダウンの動的計画法アルゴリズムを作成することです。

m = map(int, int)
m[0] = 0
m[1] = 1
function fib(n)
  if(m[n] does not exist)
    m[n] = fib(n-1) + fib(n-2)

これにより、fib（i）を最大1回計算します。

一気飲み

ボトムアップでは、トップダウンで使用されるのと同じメモ化手法を使用します。ただし、違いは、ボトムアップでは、再発と呼ばれる比較サブ問題を使用して、最終結果を最適化することです。

ほとんどのボトムアップ動的計画問題では、決定を最小化または最大化しようとしていることがよくあります。任意の時点で2つ（またはそれ以上）のオプションが与えられ、解決しようとしている問題にどちらが最適かを判断する必要があります。ただし、これらの決定は、以前に行った選択に基づいています。

各ポイント（各サブ問題）で最適な決定を行うことにより、全体的な結果が最適であることを確認できます。

これらの問題の最も難しい部分は、問題を解決するための漸化式を見つけることです。

たくさんのアルゴリズムの教科書にお金を払うために、あなたはn個のアイテムを持っている店を奪うことを計画しています。問題は、あなたの小さなナップザックが最大でWkgしか保持できないことです。各アイテムの重量（w [i]）と値（v [i]）を知っているので、盗品の値を最大化して、合計で最大Wの重量にします。各アイテムについて、2つの選択を行う必要があります-それを取るか、それを残す。

ここで、サブ問題が何であるかを見つける必要があります。非常に明るい泥棒であるため、最大の重みwを持つ特定のアイテムの最大値iをm [i、w]で表すことができることに気付きます。さらに、m [0、w]（最大重みwの0アイテム）およびm [i、0]（最大重み0のiアイテム）は常に0の値に等しくなります。

それで、

m[i, w] = 0 if i = 0 or w = 0

フルフェイスマスクをオンにすると、バッグにできるだけ多くの重量を入れた場合、その重量が最大重量と最大重量の差以下でない限り、新しいアイテムを検討できないことに気付きます。バッグの現在の重量。アイテムを検討する必要があるもう1つのケースは、バッグ内のアイテムの重量がそれ以下であるが、価値が高い場合です。

 m[i, w] = 0 if i = 0 or w = 0
           m[i - 1, w] if w[i] > w
           max(m[i - 1, w], m[i - 1, w - w[i]] + v[i]) if w[i] <= w

これらは、上記の漸化式です。これらの関係ができたら、アルゴリズムの作成は非常に簡単です（そして短いです！）。

v = values from item1..itemn
w = weights from item1..itemn
n = number of items
W = maximum weight of knapsack
   
m[n, n] = array(int, int)
function knapsack
  for w=0..W
    m[0, w] = 0
  for i=1 to n
    m[i, 0] = 0
    for w=1..W
      if w[i] <= w
        if v[i] + m[i-1, w - w[i]] > m[i-1, w]
           m[i, w] = v[i] + m[i-1, w - w[i]]
        else
           m[i, w] = m[i-1, w]
      else
        m[i, w] = c[i-1, w]
  
  return m[n, n]

追加リソース

  1. アルゴリズムの概要
  2. プログラミングの課題
  3. アルゴリズム設計マニュアル

問題の例

幸いなことに、動的計画法は、競技プログラミングに関しては本当に重要になっています。動的計画問題の再発を実装および発見する能力をテストするいくつかの練習問題については、UVAJudgeの動的計画法を確認してください。

于 2010-12-10T18:16:56.223 に答える
10

要するに、動的計画法は、複雑な問題をより単純なステップに分解することによって、つまり問題を段階的に解決することによって解決する方法です。

  1. 動的計画法;
  2. 動的計画法入門;
  3. MITのアルゴリズム入門、講義15：動的計画法;
  4. アルゴリズム設計（本）。

このリンクが少なくとも少し役立つことを願っています。

于 2010-11-25T14:52:31.057 に答える
6

皮切りに

あなたが自分自身をテストしたいのであれば、オンライン審査員についての私の選択は

そしてもちろん

また、優れた大学のアルゴリズムコースを確認することもできます

結局のところ、問題を解決できない場合は、多くのアルゴリズム中毒者がここに存在することをSOに尋ねてください

于 2011-01-28T18:19:59.123 に答える
5

下記参照

上記の記事にはサンプルや記事の参照が多すぎます。

動的計画法を学んだ後、 UVAの問題を解決することでスキルを向上させることができます。UVAのディスカッション掲示板には、いくつかのUVA動的計画法の問題のリストがあります。

また、 Wikiにはそのための優れた簡単なサンプルがあります。

編集： それに関する本のアルゴリズムについては、次を使用できます：

また、動的計画法のメモ化も確認する必要があります。

于 2010-11-25T15:53:13.407 に答える
4

代数動的計画 法は言及する価値があると思います 。これは、DP技術の非常に刺激的なプレゼンテーションであり、バイオインフォマティクスコミュニティで広く使用されています。また、ベルマンの最適性の原理は非常にわかりやすい方法で述べられています。

従来、DPは例によって教えられていました。アルゴリズムは、中間の問題の解決策を格納するテーブルエントリ間の繰り返しの観点からキャストされ、このテーブルから、全体的な解決策がいくつかのケース分析によって構築されます。

ADPは、問題をサブ問題に分解し、ケース分析を目的の最適化の目的から完全に分離するように、DPアルゴリズムを編成します。これにより、同様の問題に対してDPアルゴリズムのさまざまな部分を再利用および組み合わせることができます。

ADPアルゴリズムには、次の3つの緩く結合された部分があります。

  • 検索スペースの構築（ツリー文法の観点から述べられています）;
  • サーチスペースの各要素をスコアリングします。
  • 関心のある検索空間の要素を選択する目的関数。

次に、このすべての部分が自動的に融合され、効果的なアルゴリズムが生成されます。

于 2010-12-09T21:10:37.827 に答える
3

このUSACOの記事は、DPの基本と、それがどのように驚異的なスピードアップをもたらすかを理解するための良い出発点です。次に、基本もカバーしているが、あまりよく書かれていないこのTopCoderの記事を見てください。CMUからのこのチュートリアルもかなり良いです。それを理解したら、参照している問題を解決するために2DDPに飛躍する必要があります。リンゴの質問（中間のラベルが付いている）まで、このTopcoderの記事を読んでください。

ビデオから物事をどれだけうまく拾うかによっては、このMITビデオ講義を見るのも役立つかもしれません。

また、DPを正常に取得できるようになるには、再帰をしっかりと把握する必要があることにも注意してください。DPは難しいです！しかし、本当の難しい部分は解決策を見ることです。DPの概念（上記で理解できるはずです）を理解し、ソリューションのスケッチを示したら（たとえば、質問に対する私の答えなど、DPソリューションは通常、非常に難しいため、適用するのはそれほど難しくありません。簡潔で、理解しやすい再帰的ソリューションの反復バージョンからそれほど遠くありません。

また、メモ化も確認する必要があります。メモ化は理解しやすいと感じる人もいますが、多くの場合、DPと同じくらい効率的です。簡単に説明すると、メモ化は再帰関数を取り、その結果をキャッシュして、将来同じ引数の結果を再計算することを保存します。

于 2010-12-04T13:11:20.910 に答える
2

動的計画法で解決できるのは一部の問題だけです

まだ誰も言及していないため、動的計画法ソリューションを適用するために必要なプロパティは次のとおりです。

  • 重複するサブ問題。 一部のサブ問題が複数回発生するように、元の問題をサブ問題に分解できる必要があります。単純な再帰に対するDPの利点は、これらのサブ問題のそれぞれが1回だけ解決され、結果が保存され、必要に応じて再利用されることです。言い換えれば、DPアルゴリズムはメモリを時間と交換します。
  • 最適な下部構造。サブ問題の最適解 のみを使用して、サブ問題の最適解を計算できる必要があります。このプロパティが保持されていることを確認するには、慎重に検討する必要があります。

例：全ペア最短経路

DPアルゴリズムの典型的な例として、 Floyd-Warshallアルゴリズムを使用して、グラフ内の頂点のすべてのペア間の最短経路の長さを見つける問題を考えてみます。

n1から。までの番号が付けられた頂点があるとしnます。頂点とd(a, b)の間の最短経路の長さである関数を計算することに関心がありますが、関数の他の値からこれを効率的に計算する方法を見つけることは困難です。abd()

3番目のパラメータを導入して、との間の最短経路の長さをc定義し、1からその間の範囲の頂点のみを訪問します。（これらすべての頂点にアクセスする必要はありません。）これを追加するのは無意味な制約のように見えますが、次の関係になっていることに注意してください。d(a, b, c)abc

d(a, b, c) = min(d(a, b, c-1), d(a, c, c-1) + d(c, b, c-1))

上記の2つの引数min()は、考えられる2つのケースを示しています。頂点1のみaを使用してから次のいずれかに到達するための最短の方法：bc

  1. 回避（この場合、最初の頂点cのみを使用する最短経路と同じです）、またはc-1
  2. 経由しcます。この場合、このパスはからへの最短パスであり、その後にからへの最短パスが続く必要があります。両方aのcパスは、1からその間の範囲の頂点のみを訪問するように制約されます。このケース（経由）が短い場合、これらの2つのパスは同じ頂点のいずれにもアクセスできないことがわかっています。これは、パスがあった場合、それらの間のすべての頂点（を含む）をスキップする方が短いため、ケース1は代わりに選択しました。cbc-1cc

この定式化は、最適な部分構造特性を満たします。より大きな問題の最適な解を見つけるには、サブ問題の最適な解を知る必要があるだけです。（すべての問題にこの重要な特性があるわけではありません。たとえば、頂点のすべてのペア間の最長のパスを見つけたい場合、からの最長のパスがからの最長のパスによっても訪問される頂点を訪問aする可能性があるため、このアプローチは失敗します。）ccb

上記の関数関係、およびとの間のエッジの長さに等しい境界条件（d(a, b, 0)またはそのようなエッジが存在しない場合は無限大）がわかれば、から始まり、までのすべての値を計算できます。 は、の間の最短距離であり、その間の任意の頂点にアクセスできます。これは、私たちが探している答えです。abd(a, b, c)c=1c=nd(a, b, n)ab

于 2010-12-11T20:40:24.360 に答える
1

http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html

于 2010-11-25T14:42:06.603 に答える
1

ほとんどすべての入門アルゴリズムの本には、動的計画法に関する章があります。私がお勧めします：

于 2010-12-04T12:53:34.757 に答える
1

アルゴリズムについて学びたい場合は、MITが非常に優れた講義のビデオを利用できることを発見しました。

たとえば、6.046J / 18.410Jアルゴリズム入門（SMA 5503）はかなり良い賭けのようです。

このコースでは、他の多くの有用なアルゴリズム手法の中でも、動的計画法について説明します。使用した本はまた、私の個人的な意見では、非常に優れており、アルゴリズムについて真剣に学ぶ人にとっては購入する価値があります。

さらに、コースには課題のリストなどが付属しているので、実際に理論を実践することもできます。

関連する質問：

于 2011-01-28T15:13:08.913 に答える
0

問題を解決するために動的計画法を試してみると、その背後にある概念を理解するようになると思います。Google codejamでは、参加者に「Welcome to CodeJam」というプログラムが提供されると、動的計画法が優れた方法で使用されていることが明らかになりました。

于 2011-01-28T15:32:33.727 に答える
0

通信数学修士課程の一環として、私は本http://www.amazon.co.uk/Introduction-Programming-International-mathematics-computer/dp/0080250645/ref=sr_1_4?ie=UTF8&qid=1290713580&srに基づいてコースを受講しました。 = 8-4プログラミングの角度というよりは数学的な角度ですが、時間と労力を惜しまないのであれば、非常に徹底的な紹介です。本。

Sedgewickによる本「Algorithms」の初期バージョンもあります。そこには動的計画法に関する非常に読みやすい短い章があります。彼は今、途方もない種類の高価な本を売っているようです。アマゾンを見ると、 http： //www.amazon.co.uk/gp/product/toc/0201361205/ref=dp_toc？ie = UTF8＆n= 266239に同じ名前の章があるようです。

于 2010-11-25T19:46:12.277 に答える
0

StevenLaValleによるPlanningAlgorithmsには、動的計画法に関するセクションがあります。

http://planning.cs.uiuc.edu/

たとえば、セクション2.3.1を参照してください。

于 2010-11-25T19:52:42.917 に答える
0

MITオープンコースウェア6.00コンピュータサイエンスとプログラミング入門

于 2011-01-28T15:13:28.623 に答える