dynamic-programming チュートリアル
動的プログラミングの概要

algorithm C Language C# Language C++ Haskell Language Java Language JavaScript PHP Python Language Scala Language

備考

このセクションでは、動的プログラミングの概要と、開発者がそれを使用する理由を概説します。

また、ダイナミックプログラミングの中の大きなテーマについても言及し、関連するトピックにリンクする必要があります。動的プログラミングのドキュメンテーションは新しいものなので、それらの関連トピックの初期バージョンを作成する必要があります。

動的プログラミング入門

動的プログラミングは、問題をサブ問題に組み合わせることによって問題を解決します。これは、問題が分割された部分問題に分割され、部分問題が再帰的に解かれ、元の問題の解を見つけるために結合される、分割と征服の方法に類似している可能性があります。対照的に、サブプログラムが重複している場合、つまりサブプログラムがサブサブプログラムを共有している場合には、動的プログラミングが適用されます。このコンテキストでは、分割・征服アルゴリズムが必要以上に多くの作業を行い、共通のサブサブ問題を繰り返し解決します。ダイナミックプログラミングアルゴリズムは各サブサブ問題を1回だけ解き、その答えを表に保存するので、各サブ問題を解決するたびに解を再計算する作業が回避されます。

例を見てみましょう。イタリアの数学者Leonardo Pisano Bigollo （フィボナッチ）は、ウサギ人口の理想化された成長を考慮して数列を発見しました。シリーズは：

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

最初の2つ後のすべての数字は、前の2つの数字の合計です。今度は、関数F（n）を公式化して、n番目のフィボナッチ数を返します。つまり、

F(n) = nth Fibonacci Number

これまでのところ、我々はそれを知っていた、

F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3

我々は一般化することができます：

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

これを再帰関数として書いたければ、 F(1)とF(2)を基本ケースとする。したがって、フィボナッチ関数は次のようになります。

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

今度はF(6)を呼び出すと、 F(5)とF(4)が呼び出されます。これを図式的に表現しましょう。

画像から、 F(6)がF(5)とF(4)を呼び出すことがわかります。 F(5)はF(4)とF(3)を呼び出します。 F(5)計算した後、 F(5)によって呼び出されたすべての関数がすでに計算されていると確信できます。つまり、私たちは既にF(4)計算しています。しかし、 F(6)の右の子が示すように、再びF(4)を計算しています。私たちは本当に再計算する必要がありますか？私たちができることは、 F(4)値を計算したら、それをdpという名前の配列に格納し、必要に応じてそれを再利用するということです。 dp配列を-1 （または計算に含まれない値）で初期化します。それから、修正したF（n）が次のようになるF（6）を呼び出します。

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

以前と同じタスクを実行しましたが、単純な最適化を行いました。つまり、私たちはメモ化技術を使用しました。最初は、 dp配列のすべての値は-1になります。 F(4)が呼び出されると、空であるかどうかがチェックされます。 -1を格納すると、その値を計算してdp [4]に格納します。 -1以外の値が格納されている場合は、すでに値が計算されていることを意味します。だから、単に値を返すだけです。

メモ帳を使用したこの単純な最適化は、 動的プログラミングと呼ばれます。

ダイナミックプログラミングにいくつかの特徴がある場合、問題を解決することができます。これらは：

サブ問題：
DP問題は、1つ以上のサブ問題に分けることができる。例えば、 F(4)は、より小さなサブ問題F(3)とF(2)分割することができます。サブ問題は私たちの主な問題と同様であるため、これらは同じ手法を使用して解決できます。
重複するサブ問題：
DP問題には、重複するサブ問題がなければなりません。つまり、同じ関数が複数回呼び出される共通の部分が必要です。たとえば、 F(5)とF(6)はF(3)とF(4)が共通しています。これが配列に値を格納した理由です。

最適な部分構造：
関数g(x)を最小にするように求められたとしましょう。 g(x)値はg(y)とg(z)依存することが分かります。 g(y)とg(z)両方を最小化することによってg(x)を最小にすることができれば、問題が最適な基礎構造を持つと言うことができる。あればg(x)唯一最小化することによって最小化されるg(y)し、最小化または最大化する場合にg(z)上の任意の効果はありませんg(x) 、この問題は、最適な下部構造を持っていません。簡単に言えば、問題の最適解をその部分問題の最適解から見つけることができれば、問題は最適部分構造の性質を持つと言える。

動的プログラミングにおける状態の理解

例を挙げて説明しましょう。 n個の項目から、あなたがRの項目を選択することができますどのように多くの方法で？あなたはそれが。ひとつのアイテムを考えてみましょう。

アイテムを選択しなかった場合は、残りのn-1アイテムからr個のアイテムを取得する必要があります。。
アイテムを選択すると、残りのn-1アイテムからr-1アイテムを取らなければなりません。。

これらの2つの合計は、私たちに総数の方法を与える。あれは：

nCr(n,r)をnとrをパラメータとする関数として考えるとnCr(n,r) 上記の関係を以下のように書くことができます：

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

これは再帰的関係です。それを終了するには、基本ケースを決定する必要があります。私達はことを知っています、そして。これらの2つを基本ケースとして使用して、次のようになります：

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

この手順をグラフィカルに見ると、再帰が複数回呼び出されることがわかります。たとえば、 n = 8 、 r = 5とすると 、次のようになります。

この繰り返し呼び出しは、配列dpを使用して回避できます。 2つのパラメータがあるので、2D配列が必要です。 dp配列を-1で初期化します。ここで、 -1は値がまだ計算されていないことを示します。私たちの手順は次のようになります：

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

決定する 2つのパラメータnとrが必要でした。これらのパラメータは状態と呼ばれます。状態の数がdp配列の次元数を決定するということを単純に推論することができます。配列のサイズは、私たちの必要に応じて変わります。私たちの動的プログラミングアルゴリズムは、次の一般的なパターンを維持します：

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

状態の決定は、動的プログラミングの最も重要な部分の1つです。これは、問題を定義し、計算を最適化するパラメータの数で構成され、問題全体を最適化できます。

DPソリューションの構築

ダイナミックプログラミング（DP）を使用していくつの問題を解決しても、あなたを驚かせることができます。しかし、人生の他のすべてのものとして、練習はあなたをより良くします。これらを念頭に置いて、DP問題の解決策を構築するプロセスを見ていきます。このトピックに関する他の例は、DPの内容とその動作方法を理解するのに役立ちます。この例では、ゼロからDPソリューションをどのように考え出すかを理解しようとします。

繰り返しVS再帰：
DP解を構築するには2つの手法があります。彼らです：

反復（for-cyclesを使用）
再帰的（再帰を使用して）

たとえば、2つの文字列s1とs2の最長共通部分列の長さを計算するアルゴリズムは次のようになります。

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

これは反復的な解決策です。このようにコード化される理由はいくつかあります。

反復は再帰より速い。
時間と空間の複雑さを判断するのは簡単です。
ソースコードは短くてクリーンです

ソースコードを見ると、どのように、なぜそれが動作するのかを簡単に理解することができますが、この解決策をどのように考え出すのかを理解することは難しいです。しかしながら、上記の2つのアプローチは、2つの異なる擬似コードに変換される。 1つは反復（ボトムアップ）を使用し、もう1つは再帰（トップダウン）アプローチを使用します。後者の方法は、メモ化技術としても知られています。しかし、2つのソリューションは多かれ少なかれ同等であり、1つは簡単に別のソリューションに変換できます。この例では、問題の再帰的解決策を思いつく方法を示します。

問題の例：
たとえば、 N （ 1,2,3、...、N ）のワインが棚の隣に置かれているとします。私のワインの価格はp [i]です。毎年ワインの価格が上昇しています。 [i]はワイン= のy * pの年*価格：このワインi番目の価格はなりますyの年に、年1であると仮定する。あなたは持っているワインを売りたいのですが、今年から1年に1本のワインを売る必要があります。また、毎年、左端または右端のワインだけを売ることができ、ワインを並べ替えることはできません。つまり、ワインは最初と同じ順序で留まる必要があります。

たとえば、棚に4つのワインがあり、その価格が（左から右に）あるとします。

+---+---+---+---+
| 1 | 4 | 2 | 3 |
+---+---+---+---+

最適な解決策は、 1 - > 4 - > 3 - > 2の順序でワインを販売することです。

貪欲なアプローチ：
しばらくブレインストーミングした後、可能な限り遅れて高価なワインを販売するソリューションを考え出すことがあります。あなたの貪欲な戦略は次のようになります：

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

この戦略では、2つのワインの価格が同じ場合に何をすべきかは言及されていませんが、戦略は正しいと感じます。しかし残念ながら、そうではありません。ワインの価格が：

+---+---+---+---+---+
| 2 | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

貪欲な戦略は、 1 - > 2 - > 5 - > 4 - > 3の順でそれらを販売し、

しかし、 1 - > 5 - > 4 - > 2 - > 3の順番でワインを販売すれば、

この例では、問題が最初の視野に見えるほど簡単ではないことを納得させるべきです。しかし、それは動的プログラミングを使用して解決することができます。

バックトラッキング：
バックトラックソリューションを見つける問題のためのメモ化ソリューションを考え出すのは便利です。バックトラックソリューションは、問題のすべての有効な回答を評価し、最良の回答を選択します。ほとんどの問題については、そのような解決策を考えるのは簡単です。バックトラックソリューションへのアプローチには、次の3つの戦略があります。

再帰を使って答えを計算する関数でなければなりません。
それはreturn文で答えを返すべきです。
すべての非ローカル変数は読み取り専用として使用する必要があります。つまり、関数はローカル変数とその引数のみを変更できます。

私たちの問題の例として、左端または右端のワインを販売し、再帰的に答えを計算してより良いワインを返そうとします。バックトラックソリューションは次のようになります。

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

profitDetermination(1, 0, n-1)を使用してこのプロシージャを呼び出すと、 nはワインの総数です。答えを返します。

このソリューションは、単にワインを販売する可能なすべての組み合わせを試行します。最初にn個のワインがある場合は、可能性。正しい答えが得られたとしても、アルゴリズムの時間的複雑さは指数関数的に増加します。

正しく書かれたバックトラック機能は、常に明確な質問に対する答えを表す必要があります。この例では、 profitDeterminationプロシージャは、配列pに格納された価格のワインを販売することで得られる利益のうち、現在の年が年であり、売れ残りワインの間隔が[begin 、終わり]、包括的？バックトラック機能のためにそのような質問を作成して、正しいことを理解し、それが何をするのかを正確に理解するようにしてください。

決定する状態：
StateはDPソリューションで使用されるパラメータの数です。このステップでは、関数に渡す引数のどちらが冗長であるか、つまり他の引数から構築するか、まったく必要ないかについて考える必要があります。そのような引数がある場合、それらを関数に渡す必要はありません。関数内で引数を計算します。

上記の例の関数profitDeterminationでは、引数のyearは冗長です。すでに販売しているワインの数に1を加えたものに相当します。ワインの最初の数から、販売していないワインの数に1を足したものを加えたものを使用して決定することができます。ワインの総数nをグローバル変数として保存すると、関数を次のように書き換えることができます。

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

また、有効な入力から得られる可能性のあるパラメータの範囲について考える必要があります。この例では、各パラメータは、 beginとend 0からN-1までの値を含むことができます。有効な入力では、 begin <= end + 1も期待しbegin <= end + 1 。私たちの関数を呼び出すことができるO(n²)異なる引数があります。

メモ化：
私たちは今ほとんど終わりました。時間の複雑さを伴うバックトラックソリューションを変換するには時間の複雑さを伴うメモ解決に、我々は多大な努力を必要としない少しトリックを使用します。

上記のように、私たちの関数を呼び出すことができるさまざまなパラメータ。言い換えれば、私たちが実際に計算できる別のもの。だからどこが時間の複雑さから来て、何を計算するのですか？

その答えは、指数関数的な時間の複雑さは繰り返された再帰によってもたらされ、そのために同じ値が繰り返し計算されます。 n = 20のワインの任意の配列に対して上記のコードを実行し、引数begin = 10とend = 10に対して関数が何回呼び出されたかを計算すると、番号92378が得られます。それは何度も同じ答えを計算する時間の無駄です。これを改善するためにできることは、それらを計算した後に値を格納することです。関数がすでに計算された値を求めるたびに、再帰全体を再実行する必要はありません。私たちは配列dp [N] [N]を持ち、 -1 （または計算には含まれない任意の値）で初期化します。ここで、 -1は値がまだ計算されていないことを示します。配列のサイズはbeginとendの最大値によって決定されます。これは配列の開始値と終了値の対応する値を格納するためです。私たちの手順は次のようになります：

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

これが当社の必要とされるDPソリューションです。私たちの非常に簡単なトリックで、ソリューションは実行されますそこには時間があります私たちの関数を呼び出すことができるさまざまなパラメータと、それらの関数のそれぞれについて、この関数は複雑。

サマリー：
DPを使用して解決できる問題を特定できる場合は、次の手順を使用してDPソリューションを構築します。

バックトラック関数を作成して、正しい答えを提供します。
重複する引数を削除します。
可能な関数パラメータの値の最大範囲を見積もり、最小化します。
1つの関数呼び出しの時間の複雑さを最適化してください。
値を2回計算する必要がないように値を格納します。

DPソリューションの複雑さは、 可能な値の範囲で あり、各呼び出しの時間複雑さで 関数を呼び出すことができます 。

Modified text is an extract of the original Stack Overflow Documentation

ライセンスを受けた CC BY-SA 3.0

所属していない Stack Overflow