動的プログラミング

動的計画法は、数学的な最適化手法であると同時にアルゴリズムのパラダイムでもあります。この手法は、1950 年代にリチャード ベルマンによって開発され、航空宇宙工学から経済学まで、さまざまな分野で応用されてきました。

どちらの文脈でも、これは複雑な問題を再帰的に単純なサブ問題に分割して単純化することを指します。一部の決定問題はこの方法では分解できませんが、複数の時点にまたがる決定は多くの場合再帰的に分解されます。同様に、コンピューター サイエンスでは、問題をサブ問題に分割し、サブ問題に対する最適なソリューションを再帰的に見つけることで最適に解決できる場合、その問題は最適なサブ構造を持っていると言われます。

サブ問題がより大きな問題の中に再帰的にネストされ、動的計画法が適用できる場合、より大きな問題の値とサブ問題の値の間には関係があります。^{[1]最適化の文献では、この関係は}ベルマン方程式と呼ばれています。

数学的最適化の観点から見ると、動的プログラミングは通常、意思決定を時間の経過に伴う一連の意思決定ステップに分解することで意思決定を簡素化することを指します。

これは、 1 からnまでの時間iにおけるシステムの状態を表す引数としてyを取る値関数 のシーケンスV ₁、V ₂、...、V _{n を}定義することによって行われます。

V _n ( y )の定義は、最後の時刻nにおける状態yで得られた値です。

以前の時刻i  =  n  −1,  n − 2, ..., 2, 1 における値V _{i は}、ベルマン方程式と呼ばれる再帰関係 を使用して逆方向に作業することで見つけることができます。

i  = 2, ...,  nの場合、任意の状態 y でのV i _−1は、時間i − 1での決定からのゲインと 、この決定が行われた場合にシステムの新しい状態における関数V _{iとの単純な関数 (通常は合計) を最大化することによってV} i から計算されます。

必要な状態に対してV _{i は}すでに計算されているため、上記の操作によりそれらの状態に対してV _{i −1}が生成されます。

最後に、システムの初期状態における V _{1 が最適解の値です。決定変数の最適値は、すでに実行された計算を遡ることで 1 つずつ回復できます。}

制御理論における典型的な問題は、コスト関数を最小化する連続時間間隔で許容軌道をたどる許容制御を見つけることである。${\displaystyle \mathbf {u} ^{\ast}}$${\displaystyle {\dot {\mathbf {x} }}(t)=\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)}$${\displaystyle \mathbf {x} ^{\ast}}$${\displaystyle t_{0}\leq t\leq t_{1}}$

${\displaystyle J=b\left(\mathbf {x} (t_{1}),t_{1}\right)+\int _{t_{0}}^{t_{1}}f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)\mathrm {d} t}$

この問題の解決策は、最適な軌道とコスト関数を生成する最適な制御法則またはポリシーです。コスト関数は、動的計画法の基本方程式に従います。 ${\displaystyle \mathbf {u} ^{\ast }=h(\mathbf {x} (t),t)}$${\displaystyle \mathbf {x} ^{\ast }}$ ${\displaystyle J^{\ast }}$

${\displaystyle -J_{t}^{\ast }=\min _{\mathbf {u} }\left\{f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)+J_{x}^{\ast {\mathsf {T}}}\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)\right\}}$

ハミルトン・ヤコビ・ベルマン方程式として知られる偏微分方程式 （ただし、および）である。 、、および未知の関数について を最小化することがわかり、その結果をハミルトン・ヤコビ・ベルマン方程式に代入して、境界条件 で解く偏微分方程式を得ます。^[2]実際には、正確な最適化関係への離散近似のための 数値手法が一般的に必要になります。${\displaystyle J_{x}^{\ast }={\frac {\partial J^{\ast }}{\partial \mathbf {x} }}=\left[{\frac {\partial J^{\ast }}{\partial x_{1}}}~~~~{\frac {\partial J^{\ast }}{\partial x_{2}}}~~~~\dots ~~~~{\frac {\partial J^{\ast }}{\partial x_{n}}}\right]^{\mathsf {T}}}$${\displaystyle J_{t}^{\ast }={\frac {\partial J^{\ast }}{\partial t}}}$${\displaystyle \mathbf {u} }$${\displaystyle t}$${\displaystyle \mathbf {x} }$${\displaystyle J_{x}^{\ast }}$${\displaystyle J\left(t_{1}\right)=b\left(\mathbf {x} (t_{1}),t_{1}\right)}$

あるいは、連続プロセスを離散システムで近似することもできます。これは、ハミルトン-ヤコビ-ベルマン方程式に類似した次の再帰関係につながります。

${\displaystyle J_{k}^{\ast }\left(\mathbf {x} _{n-k}\right)=\min _{\mathbf {u} _{n-k}}\left\{{\hat {f}}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)+J_{k-1}^{\ast }\left({\hat {\mathbf {g} }}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)\right)\right\}}$

等間隔の離散時間間隔の - 番目のステージで、およびはおよびの離散近似を表します。この関数方程式はベルマン方程式として知られており、最適化方程式の離散近似の正確な解を求めることができます。^[3]${\displaystyle k}$${\displaystyle n}$${\displaystyle {\hat {f}}}$${\displaystyle {\hat {\mathbf {g} }}}$${\displaystyle f}$${\displaystyle \mathbf {g} }$

経済学では、一般的に、ある動的な社会福祉関数を（最小化するのではなく）最大化することが目的です。ラムゼイの問題では、この関数は消費量と効用レベルを関連付けます。大まかに言えば、計画者は、同時消費と将来の消費（生産に使用される資本ストックへの投資による）の間のトレードオフに直面します。これは、異時点間の選択として知られています。将来の消費は、一定の割合で割引されます。資本の遷移方程式の離散近似は、次のように与えられます。 ${\displaystyle \beta \in (0,1)}$

${\displaystyle k_{t+1}={\hat {g}}\left(k_{t},c_{t}\right)=f(k_{t})-c_{t}}$

ここで、 は消費、は資本、 は稲田条件を満たす生産関数です。初期資本ストックが想定されています。 ${\displaystyle c}$${\displaystyle k}$${\displaystyle f}$${\displaystyle k_{0}>0}$

期間tにおける消費 を とし、消費者が生きている限り消費によって効用が生じると仮定します。消費者はせっかちで、各期間において将来の効用を係数bで割り引くと仮定します。ただし 。期間tにおける資本を とします。初期資本が所定額 であり、この期間の資本と消費によって次の期間の資本が と決定されると仮定します。ただしAは正の定数、 です。資本は負にはならないものとします。この場合、消費者の意思決定問題は次のように記述できます。 ${\displaystyle c_{t}}$ ${\displaystyle u(c_{t})=\ln(c_{t})}$${\displaystyle 0<b<1}$${\displaystyle k_{t}}$${\displaystyle k_{0}>0}$${\displaystyle k_{t+1}=Ak_{t}^{a}-c_{t}}$${\displaystyle 0<a<1}$

${\displaystyle \max \sum _{t=0}^{T}b^{t}\ln(c_{t})}$すべての人に適用される${\displaystyle k_{t+1}=Ak_{t}^{a}-c_{t}\geq 0}$${\displaystyle t=0,1,2,\ldots ,T}$

このように書くと、すべての選択変数を解く必要があるため、問題は複雑に見えます。(資本は選択変数ではありません。消費者の初期資本は既知であるとみなされます。) ${\displaystyle c_{0},c_{1},c_{2},\ldots ,c_{T}}$${\displaystyle k_{0}}$

この問題を解くための動的プログラミングのアプローチでは、問題を一連の小さな決定に分割します。そのために、各時点 t で任意の金額の資本 k を持つことの価値を表す価値関数のシーケンスを定義します。死後、資本を持つ ことによる効用は (仮定により) ありません。 ${\displaystyle V_{t}(k)}$${\displaystyle t=0,1,2,\ldots ,T,T+1}$${\displaystyle V_{T+1}(k)=0}$

過去の任意の時点における任意の資本量の価値は、ベルマン方程式を用いた逆帰納法によって計算できる。この問題では、各 に対して、ベルマン方程式は ${\displaystyle t=0,1,2,\ldots ,T}$

${\displaystyle V_{t}(k_{t})\,=\,\max \left(\ln(c_{t})+bV_{t+1}(k_{t+1})\right)}$対象となる${\displaystyle k_{t+1}=Ak_{t}^{a}-c_{t}\geq 0}$

この問題は、と という2 つの決定変数だけを含むため、前に書いた問題よりもはるかに単純です。直感的に、消費者は誕生時に生涯プラン全体を選択する代わりに、一度に 1 ステップずつ進めることができます。時刻tでは、現在の資本が与えられているため、現在の消費と貯蓄を選択するだけで済みます。 ${\displaystyle c_{t}}$${\displaystyle k_{t+1}}$${\displaystyle k_{t}}$${\displaystyle c_{t}}$${\displaystyle k_{t+1}}$

この問題を実際に解くには、逆方向に作業を進めます。簡単にするために、現在の資本レベルはkと表されます。はすでにわかっているので、ベルマン方程式を使用すると を計算でき、 に達するまでこれを繰り返します。これは、生涯にわたる初期決定問題の値です。言い換えると、 がわかれば、の最大値であるを計算できます。ここで、 は選択変数で です。 ${\displaystyle V_{T+1}(k)}$${\displaystyle V_{T}(k)}$${\displaystyle V_{0}(k)}$${\displaystyle V_{T-j+1}(k)}$${\displaystyle V_{T-j}(k)}$${\displaystyle \ln(c_{T-j})+bV_{T-j+1}(Ak^{a}-c_{T-j})}$${\displaystyle c_{T-j}}$${\displaystyle Ak^{a}-c_{T-j}\geq 0}$

逆算すると、時刻における価値関数は ${\displaystyle t=T-j}$

${\displaystyle V_{T-j}(k)\,=\,a\sum _{i=0}^{j}a^{i}b^{i}\ln k+v_{T-j}}$

ここで、それぞれは定数であり、ある時点で消費する最適な量は ${\displaystyle v_{T-j}}$${\displaystyle t=T-j}$

${\displaystyle c_{T-j}(k)\,=\,{\frac {1}{\sum _{i=0}^{j}a^{i}b^{i}}}Ak^{a}}$

これを簡略化すると

${\displaystyle {\begin{aligned}c_{T}(k)&=Ak^{a}\\c_{T-1}(k)&={\frac {Ak^{a}}{1+ab}}\\c_{T-2}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}}}\\&\dots \\c_{2}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{T-2}b^{T-2}}}\\c_{1}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{T-2}b^{T-2}+a^{T-1}b^{T-1}}}\\c_{0}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{T-2}b^{T-2}+a^{T-1}b^{T-1}+a^{T}b^{T}}}\end{aligned}}}$

年齢を重ねるにつれて現在の富のより大きな部分を消費し、最終的に人生最後の期間 である期間Tに残りの富をすべて消費することが最適であることがわかります。

動的計画法を適用するために問題が備えていなければならない重要な属性が 2 つあります。最適なサブ構造と重複するサブ問題です。重複しないサブ問題に対する最適な解決策を組み合わせることで問題を解決できる場合、その戦略は「分割統治」と呼ばれます。^{[1]これが、}マージ ソートとクイック ソートが動的計画法の問題として分類されない 理由です。

最適なサブ構造とは、与えられた最適化問題の解が、そのサブ問題に対する最適解の組み合わせによって得られることを意味します。このような最適なサブ構造は、通常、再帰によって記述されます。たとえば、グラフG=(V,E)が与えられた場合、頂点uから頂点vへの最短経路p は最適なサブ構造を示します。つまり、この最短経路p上の任意の中間頂点wを取ります。pが本当に最短経路である場合、uからwへのサブ経路p ₁とwからvへのp ₂に分割することができ、これらが実際に対応する頂点間の最短経路になります (アルゴリズム入門で説明されている単純なカットアンドペーストの議論により)。したがって、最短経路を見つけるための解を再帰的に簡単に定式化できます。これは、ベルマン–フォード アルゴリズムまたはフロイド–ワーシャル アルゴリズムが行うことです。

サブ問題が重複するということは、サブ問題の空間が小さくなければならないことを意味します。つまり、問題を解決する再帰アルゴリズムは、新しいサブ問題を生成するのではなく、同じサブ問題を何度も解決する必要があります。たとえば、フィボナッチ数列を生成するための再帰的定式化を考えてみましょう。 F _i = F _{i −1} + F _{i −2}、基本ケースはF ₁  =  F ₂  = 1 です。すると、F ₄₃ =  F ₄₂  +  F ₄₁、F ₄₂ =  F ₄₁  +  F ₄₀となります。これで、F _{41 は}F ₄₃とF ₄₂の両方の再帰サブツリーで解決されます。サブ問題の総数は実際には少ないですが (わずか 43 個)、このような単純な再帰ソリューションを採用すると、同じ問題を何度も解決することになります。動的プログラミングではこの事実を考慮し、各サブ問題を 1 回だけ解決します。

これは2つの方法のいずれかで実現できます: ^{[引用が必要]}

• トップダウン アプローチ: これは、あらゆる問題の再帰的定式化から直接生じるものです。あらゆる問題の解決が、そのサブ問題の解決を使用して再帰的に定式化でき、そのサブ問題が重複している場合、サブ問題の解決を簡単にメモ化またはテーブルに保存できます。新しいサブ問題を解決しようとするときは、まずテーブルをチェックして、その問題がすでに解決されているかどうかを確認します。解決が記録されている場合は、それを直接使用できます。そうでない場合は、サブ問題を解決して、その解決をテーブルに追加します。
• ボトムアップアプローチ: 問題の解決策をサブ問題として再帰的に定式化したら、ボトムアップ方式で問題を再定式化することができます。まずサブ問題を解決し、その解決策を基にしてより大きなサブ問題の解決策を導き出します。これは通常、小さなサブ問題の解決策を使用して、より大きなサブ問題の解決策を反復的に生成することにより、表形式で行われます。たとえば、 F ₄₁とF _{40の値がすでにわかっている場合は、} F ₄₂の値を直接計算できます。

一部のプログラミング言語では、特定の引数セットを使用した関数呼び出しの結果を自動的にメモ化して、名前による呼び出しの評価を高速化できます（このメカニズムはcall-by-needと呼ばれます）。一部の言語では、これを移植可能にしています（例：Scheme、Common Lisp、Perl、D）。テーブル化されたPrologやJ など、一部の言語には自動メモ化が組み込まれており、これらはM.副詞によるメモ化をサポートしています。 ^[4]いずれにしても、これは参照透過な関数に対してのみ可能です。メモ化は、 Wolfram Languageなどの項書き換えベースの言語内で簡単にアクセスできる設計パターンとしても見られます。

動的計画法は、バイオインフォマティクスにおいて、配列アライメント、タンパク質の折り畳み、RNA構造の予測、タンパク質-DNA結合などのタスクに広く使用されています。タンパク質-DNA結合のための最初の動的計画法アルゴリズムは、1970年代に米国のCharles DeLisi ^[5]とソ連のGeorgii GurskiiとAlexander Zasedatelevによって独立して開発されました。^{[6]最近、これらのアルゴリズムはバイオインフォマティクスと}計算生物学、特にヌクレオソームの配置と転写因子の結合 の研究で非常に人気が高まっています。

動的計画法の観点から見ると、最短経路問題に対するダイクストラ法は、 最短経路問題の動的計画法関数方程式をリーチング法で解く逐次近似法である。^{[7] [8] [9]}

実際、ダイクストラのアルゴリズムの背後にあるロジックの説明^[10]は 、

問題 2.指定された 2 つのノードと間の全長が最小となるパスを見つけます。 ${\displaystyle P}$${\displaystyle Q}$

が からへの最小経路上のノードである場合、 を知っているということはからへの最小経路を知っていることを意味するという事実を使用します。 ${\displaystyle R}$${\displaystyle P}$${\displaystyle Q}$${\displaystyle P}$${\displaystyle R}$

これは、最短経路問題の文脈におけるベルマンの有名な最適性原理の言い換えです。

フィボナッチ数列のn番目の要素の計算に動的プログラミングを使用すると、パフォーマンスが大幅に向上します。以下は、数学的定義に直接基づいた単純な実装です。

関数fib(n)
     n <= 1の場合n
    を返すfib(n − 1) + fib(n − 2)
を返す

たとえば、 を呼び出すとfib(5)、同じ値に対して関数を何度も呼び出す呼び出しツリーが生成されることに注意してください。

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

特に、fib(2)は最初から 3 回計算されました。より大きな例では、 のさらに多くの値fib、またはサブ問題が再計算され、指数時間アルゴリズムにつながります。

ここで、すでに計算された の各値をその結果にマップする単純なマップオブジェクトmがあるとします。関数を変更して、それを使用して更新します。結果の関数は、指数時間ではなくO ( n ) 時間のみを必要とします (ただし、 O ( n ) のスペースが必要です)。 fib

var m := map (0 → 0, 1 → 1)
 function fib(n)
    キーnがマップmにない場合
        m[n] := fib(n − 1) + fib(n − 2)
    m[n]
を返す

すでに計算された値を保存するこの手法は、メモ化と呼ばれます。これは、最初に問題をサブ問題に分割し、次に値を計算して保存するトップダウンアプローチです。

ボトムアップアプローチでは、まず小さい値を計算しfib、それから大きい値を構築します。この方法でも、n − 1 回繰り返すループが含まれているため O( n ) 時間を使用しますが、マップを格納するために O( n ) のスペースを必要とするトップダウンアプローチとは対照的に、必要なスペースは定数 (O(1)) だけです。

function fib(n)
     if n = 0
         return 0
     else 
        var previousFib := 0, currentFib := 1
         repeat n − 1 times  // loop is skipped if n = 1 
            var newFib := previousFib + currentFib
            前のFib := 現在のFib
            現在のFib:=新しいFib
        現在のFib
を返す

どちらの例でも、と のいずれかが評価されるたび fib(2)に を計算するのではなく、 を 1 回だけ計算し、それを使用して と の両方を計算しますfib(4)。fib(3)

n × n行列の各位置に、n が偶数で、各行と各列にちょうどn / 2個の 0 とn / 2個の 1 が含まれるように、0 または 1 の値を割り当てる問題を考えてみましょう。与えられた に対して、割り当てが何通りあるかを考えます。たとえば、n = 4の場合、5 つの可能な解があります。 ${\displaystyle n}$

${\displaystyle {\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}{\text{ and }}{\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&1&0&0\\0&0&1&1\\1&1&0&0\\0&0&1&1\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&0&0&1\\0&1&1&0\\0&1&1&0\\1&0&0&1\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&1&0&0\\1&1&0&0\\0&0&1&1\\0&0&1&1\end{bmatrix}}.}$

少なくとも 3 つのアプローチが考えられます:ブルート フォース、バックトラッキング、動的プログラミングです。

ブルートフォースは、0 と 1 の割り当てをすべてチェックし、行と列のバランスが取れているもの ( n / 2個の0 とn / 2個の 1) を数えることです。可能な割り当てと合理的な割り当てがあるため、この戦略は、おそらく までを除いて実用的ではありません。 ${\displaystyle 2^{n^{2}}}$${\displaystyle {\tbinom {n}{n/2}}^{n}}$${\displaystyle n=6}$

この問題のバックトラッキングは、行列要素の順序を選択し、1 または 0 を再帰的に配置することから成り、各行と列で割り当てられていない要素の数と 1 または 0 の数の合計が少なくともn / 2 であることを確認します。このアプローチは、ブルートフォースよりも洗練されていますが、すべてのソリューションを 1 回ずつ訪問するため、nが 6 より大きい場合は実用的ではありません。これは 、後で説明するように 、 n = 8の場合にソリューションの数はすでに 116,963,796,250 であるためです。

動的プログラミングにより、すべての解を調べなくても解の数を数えることができます。最初の行の値をバックトラックすることを想像してください。最初の行の各値に対して得られた解を正確に数えるためには、残りの行についてどのような情報が必要になるでしょうか。1 ≤ k ≤ nのk × n 個のボードを考えます。その行には0 と1 が含まれます。メモ化が適用される関数f は、 n組の整数のベクトルを許容されるボード (解) の数にマップします。各列に 1 組のペアがあり、その 2 つのコンポーネントはそれぞれ、その列にまだ配置されていない 0 と 1 の数を示します。(引数または要素の 1 つのベクトル) の値を探します。サブ問題作成のプロセスでは 、ボードの最上行の可能な割り当てのすべてを反復処理し、すべての列を調べて、最上行の割り当てにその位置に 0 が含まれているか 1 が含まれているかに応じて、その列のペアの適切な要素から 1 を減算します。結果のいずれかが負の場合、割り当ては無効であり、ソリューションのセットには寄与しません（再帰は停止します）。それ以外の場合は、k × nボードの最上行の割り当てがあり、残りの( k − 1) × nボードのソリューションの数を再帰的に計算し、最上行のすべての許容される割り当てのソリューションの数を追加して、メモされている合計を返します。基本ケースは、1 × nボードで発生する単純なサブ問題です。このボードのソリューションの数は、ベクトルがn / 2とn / 2 のペアの順列であるかどうかに応じて、0 または 1 になります。 ${\displaystyle k}$${\displaystyle n/2}$${\displaystyle n/2}$${\displaystyle f((n/2,n/2),(n/2,n/2),\ldots (n/2,n/2))}$${\displaystyle n}$${\displaystyle n}$${\displaystyle {\tbinom {n}{n/2}}}$ ${\displaystyle (0,1)}$ ${\displaystyle (1,0)}$

例えば、上に示した最初の2つのボードでは、ベクトルのシーケンスは次のようになります。

((2, 2) (2, 2) (2, 2) (2, 2)) ((2, 2) (2, 2) (2, 2) (2, 2)) k = 4
  0 1 0 1 0 0 1 1

((1, 2) (2, 1) (1, 2) (2, 1)) ((1, 2) (1, 2) (2, 1) (2, 1)) k = 3
  1 0 1 0 0 0 1 1

((1, 1) (1, 1) (1, 1) (1, 1)) ((0, 2) (0, 2) (2, 0) (2, 0)) k = 2
  0 1 0 1 1 1 0 0

((0, 1) (1, 0) (0, 1) (1, 0)) ((0, 1) (0, 1) (1, 0) (1, 0)) k = 1
  1 0 1 0 1 1 0 0

((0, 0) (0, 0) (0, 0) (0, 0)) ((0, 0) (0, 0), (0, 0) (0, 0))

解の数（OEISのシーケンスA058527）は

${\displaystyle 1,\,2,\,90,\,297200,\,116963796250,\,6736218287430460752,\ldots }$

動的プログラミング アプローチの MAPLE 実装へのリンクは、外部リンクの中にあります。

n × nのマス目を持つチェッカーボードと、マス目（行、列） に関連付けられたコストを返すコスト関数を考えてみましょう。たとえば（5 × 5 のチェッカーボードの場合）、c(i, j)(i,j)ij

したがってc(1, 3) = 5

最初の列（つまり、行）のどのマスからでも開始できるチェッカーがあり、最後の列に到達するための最短経路（各訪問列での最小コストの合計）を知りたいとします。チェッカーは斜め左前方、斜め右前方、またはまっすぐ前方にのみ移動できると仮定します。つまり、 のチェッカーは、、 、または(1,3)に移動できます。 (2,2)(2,3)(2,4)

この問題は最適な部分構造を示しています。つまり、問題全体の解は部分問題の解に依存しています。関数をq(i, j)次のように 定義します。

q ( i , j ) = square ( i , j )に到達するための最小コスト。

rank から開始しnて rank まで降順で進み1、各 rank のすべての正方形についてこの関数の値を計算します。各 rank で最小値を保持する正方形を選択すると、 ranknと rank の間の最短経路が得られます1。

この関数はq(i, j)、その下にある 3 つのマス目 (この関数に到達できるのはこれらのマス目だけなので) のいずれかに到達するための最小コストに を加えたものに等しくなりますc(i, j)。たとえば、次のようになります。

${\displaystyle q(A)=\min(q(B),q(C),q(D))+c(A)\,}$

q(i, j)さて、もう少し一般的な言葉で 定義してみましょう。

${\displaystyle q(i,j)={\begin{cases}\infty &j<1{\text{ or }}j>n\\c(i,j)&i=1\\\min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)&{\text{otherwise.}}\end{cases}}}$

この方程式の最初の行は、1最小境界とn最大境界でインデックス付けされた正方形としてモデル化されたボードを扱っています。2 行目は、最初のランクで何が起こるかを指定し、基本ケースを提供します。3 行目は再帰で、重要な部分です。これは、A,B,C,D例の項を表します。この定義から、 の簡単な再帰コードを導き出すことができますq(i, j)。次の疑似コードでは、nはボードのサイズ、c(i, j)はコスト関数、 はmin()いくつかの値の最小値を返します。

関数minCost(i, j)
     、 j < 1またはj > n
        の場合infinity
    を返し、そうでない場合はi = 1
        の場合c(i, j)
    を返し、そうでない場合はmin ( minCost(i-1, j-1)、minCost(i-1, j)、minCost(i-1, j+1) ) + c(i, j) を返します。

         

この関数は、実際のパスではなく、パス コストのみを計算します。実際のパスについては、以下で説明します。これは、フィボナッチ数列の例と同様に、重複するサブ問題q[i, j]属性を示すため、非常に低速です。つまり、同じパス コストを何度も再計算します。ただし、パス コストを関数を使用するのではなく、2 次元配列に格納すると、ボトムアップ方式ではるかに高速に計算できます。これにより再計算が回避され、配列に必要なすべての値q[i, j]が事前に 1 回だけ計算されます。事前に計算された の値は、(i,j)必要なときにいつでも参照されます。

また、実際の最短経路が何であるかを知る必要もあります。これを行うには、別の配列p[i, j]、つまり先行配列を使用します。この配列は、任意の正方形 への経路を記録しますs。 の先行配列は、の事前計算された経路コストのsインデックス ( 内) に対するオフセットとしてモデル化されます。完全な経路を再構築するには、 の先行配列、次にその正方形 の先行配列、さらにその正方形 の先行配列というように、開始正方形に到達するまで再帰的に検索します。次の疑似コードを検討してください。 q[i, j]ss

関数computeShortestPathArrays()
    はxが1からnまでである。
        q[1, x] := c(1, x)
    yは1からnまで
        q[y, 0] := 無限大
        q[y, n + 1] := 無限大
    yは2からn、
         xは1からn​
            m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
            q[y, x] := m + c(y, x)
            m = q[y-1, x-1]の場合
                p[y, x] := -1
            それ以外の場合、 m = q[y-1, x]
                p[y, x] := 0
            それ以外
                p[y, x] := 1

残りは、最小値を見つけてそれを印刷するだけの簡単な作業です。

関数computeShortestPath()
    最短パス配列を計算する()
    最小インデックス:= 1
    最小値 := q[n, 1]
    iが2からn
        までの場合、 q[n, i] < min
            最小インデックス:= i
            最小値 := q[n, i]
    printPath(n, 最小インデックス)

関数printPath(y, x)
     print (x)
     print ("<-")
     if y = 2
         print (x + p[y, x])
     else
        printPath(y-1, x + p[y, x])

遺伝学において、配列アライメントは動的計画法が不可欠な重要な応用分野である。^[11] 典型的には、要素を置換、挿入、または削除する編集操作を使用して、ある配列を別の配列に変換することが問題となる。各操作には関連するコストがあり、目標は総コストが最も低い編集の配列を見つけることである。

この問題は、再帰として自然に表現することができ、シーケンス A は次のいずれかの方法でシーケンス B に最適に編集されます。

1. Bの最初の文字を挿入し、AとBの末尾の最適な配置を実行する
2. Aの最初の文字を削除し、AとBの末尾の最適な配置を実行する
3. A の最初の文字を B の最初の文字に置き換え、A と B の末尾の最適な配置を実行します。

部分的なアラインメントはマトリックスに表形式で表すことができます。セル (i,j) には、A[1..i] から B[1..j] への最適なアラインメントのコストが含まれます。セル (i,j) のコストは、関連する操作のコストをその隣接セルのコストに追加し、最適なものを選択することで計算できます。

さまざまなバリエーションが存在します。Smith –Waterman アルゴリズムとNeedleman–Wunsch アルゴリズムを参照してください。

ハノイの塔は数学的なゲームまたはパズルです。3 本の棒と、どの棒にもスライドできるさまざまなサイズのディスクで構成されています。パズルは、ディスクを 1 本の棒の上にサイズの昇順できちんと積み重ね、一番小さいディスクを一番上に置き、円錐形を作るところから始まります。

パズルの目的は、次のルールに従ってスタック全体を別のロッドに移動することです。

• 一度に移動できるディスクは 1 つだけです。
• 各動作は、ロッドの 1 つから上部のディスクを取り出し、それを別のロッドにスライドさせることで構成されます。このロッドには、すでにそのロッドに存在している可能性のある他のディスクが置かれます。
• 小さいディスクの上にディスクを置くことはできません。

動的計画法の解法は関数方程式を解くことからなる。

S(n,h,t) = S(n-1,h, not(h,t)) ; S(1,h,t) ; S(n-1,not(h,t),t)

ここで、nは移動するディスクの数、hはホームロッド、tはターゲットロッド、not(h,t)は3番目のロッド（hでもtでもない）、「;」は連結を表し、

S(n, h, t) := 棒 h から棒 t に移動する n 個のディスクからなる問題の解。

n=1 の場合、問題は簡単です。つまり、S(1,h,t) = 「ディスクをロッド h からロッド t に移動する」(残っているディスクは 1 つだけです)。

この解法に必要な移動回数は2 ⁿ  − 1回である。目的が移動回数を最大化すること（循環なし）である場合、動的計画法の関数方程式は 少し複雑になり、3 ⁿ  − 1回の移動が必要となる。^[12]

以下は、 N=2個の卵とH=36階建ての建物が関係するこの有名なパズルの例の説明です。 ^[13]

36 階建てのビルのどの階から卵を落としても安全で、どの階から卵を落とすと着地時に割れてしまうかを知りたいとします (米国英語の用語では 1 階が地上レベルです)。いくつかの仮定を立てます。

• 落下しても生き残った卵は再び使用することができます。
• 割れた卵は捨てなければなりません。
• 落下の影響はすべての卵に同じです。
• 卵を落とすと割れるのであれば、もっと高い窓から落としても割れるはずです。
• 卵が落下しても生き残るのであれば、より短い落下であれば生き残るはずです。
• 1階の窓が卵を割る可能性も否定できないし、36階の窓から卵が落ちても生き残れる可能性も否定できない。

卵が 1 個しかなく、正しい結果を確実に得たい場合、実験は 1 つの方法でしか実行できません。1 階の窓から卵を落とし、卵が壊れなければ 2 階の窓から落とします。卵が割れるまで上に向かって落とし続けます。最悪の場合、この方法では 36 回落とす必要があるかもしれません。卵が 2 個あるとします。すべての場合に確実に機能する卵の落下回数の最小値はいくつですか。

このパズルの動的計画法関数方程式を導くために、動的計画法モデルの状態をペアs = (n,k)とし、ここで

n = 利用可能なテスト卵の数、n = 0、1、2、3、...、N  − 1。

k = まだテストされていない（連続する）フロアの数、k = 0、1、2、...、H  − 1。

たとえば、s = (2,6) は、2 つのテスト卵が利用可能であり、6 つの (連続した) フロアがまだテストされていないことを示します。プロセスの初期状態はs = ( N , H ) です。ここで、N は実験の開始時に利用可能なテスト卵の数を示します。プロセスは、テスト卵がなくなる ( n = 0) か、k = 0 のいずれか早い方で終了します。終了が状態s = (0, k ) で発生し、k  > 0 の場合、テストは失敗します。

さて、

W ( n , k ) = プロセスが状態s = ( n , k )にある場合の最悪のシナリオで臨界フロアの値を特定するために必要な最小試行回数。

すると、^[14]

W ( n , k ) = 1 + min{max( W ( n − 1, x − 1), W ( n , k − x )): x = 1, 2, ..., k }

ここで、n  > 0の場合にはW ( n ,0) = 0 となり、 kの場合には W (1, k ) = k となります。nと kの値を系統的に増やすことで、この方程式を反復的に解くのは簡単です。

上記の解法はDP 解法では 時間がかかることに注意してください。これは、上記の再帰の最適値をバイナリ検索することで 時間に短縮できます。これは、が で増加し、がで減少するため、 の局所的最小値は大域的最小値になるからです。また、各セルの最適値を DP テーブルに保存し、前のセルの値を参照することで、各セルの最適値を定数時間で見つけることができ、時間に短縮されます。ただし、問題の異なるパラメーター化を伴う、さらに高速な解法があります。 ${\displaystyle O(nk^{2})}$${\displaystyle O(nk\log k)}$${\displaystyle x}$${\displaystyle W(n-1,x-1)}$${\displaystyle x}$${\displaystyle W(n,k-x)}$${\displaystyle x}$${\displaystyle \max(W(n-1,x-1),W(n,k-x))}$${\displaystyle x}$${\displaystyle x}$${\displaystyle O(nk)}$

を、卵を 番目の階から落とすと割れる階の総数とします(上記の例は、 を取るのと同じです)。 ${\displaystyle k}$${\displaystyle k}$${\displaystyle k=37}$

卵を割るためには、卵を落とさなければならない最低階を と します。${\displaystyle m}$

トライとエッグを使用して区別できるの値の最大数を とします。 ${\displaystyle f(t,n)}$${\displaystyle m}$${\displaystyle t}$${\displaystyle n}$

次に、すべてに対して。 ${\displaystyle f(t,0)=f(0,n)=1}$${\displaystyle t,n\geq 0}$

最適戦略で最初の卵が落とされる階を とします 。${\displaystyle a}$

最初の卵が割れた場合、はからになり、最大で試行回数と卵を使用して区別できます。 ${\displaystyle m}$${\displaystyle 1}$${\displaystyle a}$${\displaystyle t-1}$${\displaystyle n-1}$

最初の卵が割れなかった場合は、からになり、try とegg を使用して区別できます。 ${\displaystyle m}$${\displaystyle a+1}$${\displaystyle k}$${\displaystyle t-1}$${\displaystyle n}$

したがって、。 ${\displaystyle f(t,n)=f(t-1,n-1)+f(t-1,n)}$

すると、問題はとなる最小値を見つけることと等しくなります。 ${\displaystyle x}$${\displaystyle f(x,n)\geq k}$

そうするには、の増加順に計算することになりますが、時間がかかります。 ${\displaystyle \{f(t,i):0\leq i\leq n\}}$${\displaystyle t}$${\displaystyle O(nx)}$

したがって、 の場合を個別に処理すると、アルゴリズムに時間がかかります。 ${\displaystyle n=1}$${\displaystyle O(n{\sqrt {k}})}$

しかし、再帰関係は実際には解くことができ、 が得られます。 これは、すべての に対する恒等式を使用して、時間内に計算できます。${\displaystyle f(t,n)=\sum _{i=0}^{n}{\binom {t}{i}}}$${\displaystyle O(n)}$${\displaystyle {\binom {t}{i+1}}={\binom {t}{i}}{\frac {t-i}{i+1}}}$${\displaystyle i\geq 0}$

すべての に対してなので、 を二分探索してを見つけることができ、アルゴリズムが得られます。^[15]${\displaystyle f(t,n)\leq f(t+1,n)}$${\displaystyle t\geq 0}$${\displaystyle t}$${\displaystyle x}$${\displaystyle O(n\log k)}$

行列チェーンの乗算は、動的プログラミングの有用性を示すよく知られた例です。たとえば、エンジニアリング アプリケーションでは、行列チェーンの乗算が必要になることがよくあります。100×100 などの大きな次元の行列が見つかることは珍しくありません。したがって、私たちのタスクは行列の乗算です。行列${\displaystyle A_{1},A_{2},....A_{n}}$の乗算は可換ではありませんが、結合的です。また、一度に乗算できる行列は 2 つだけです。したがって、この行列チェーンの乗算はさまざまな方法で行うことができます。たとえば、次のようになります。

((A ₁ × A ₂ ) × A ₃ ) × ...A _n

A ₁ ×(((A ₂ ×A ₃ )× ... ) × A _n )

(A ₁ × A ₂ ) × (A ₃ × ...A _n )

などなど。この行列の連鎖を乗算する方法は数多くあります。どの方法も最終結果は同じですが、どの行列を乗算するかによって計算にかかる時間が異なります。行列 A の次元が m×n で、行列 B の次元が n×q の場合、行列 C=A×B の次元は m×q となり、m*n*q 回のスカラー乗算が必要になります (説明のために単純化した行列乗算アルゴリズムを使用しています)。

たとえば、行列 A、B、C を掛け合わせます。それぞれの次元が m×n、n×p、p×s であるとします。行列 A×B×C のサイズは m×s となり、次の 2 つの方法で計算できます。

1. Ax(B×C) この順序の行列乗算では、nps + mns のスカラー乗算が必要になります。
2. (A×B)×C この順序の行列乗算では、mnp + mps スカラー計算が必要になります。

m = 10、n = 100、p = 10、s = 1000 と仮定します。したがって、チェーンを乗算する最初の方法では、1,000,000 + 1,000,000 回の計算が必要になります。2 番目の方法では、10,000 + 100,000 回の計算のみが必要です。明らかに、2 番目の方法の方が高速なので、その括弧の配置を使用して行列を乗算する必要があります。

したがって、括弧の順序が重要であり、最適な括弧の順序を見つけることが私たちの課題であるという結論に達しました。

この時点では、いくつかの選択肢があります。そのうちの 1 つは、問題を重複する問題に分割し、括弧の最適な配置を計算する動的プログラミング アルゴリズムを設計することです。動的プログラミング ソリューションを以下に示します。

行列 i から行列 j までの行列のチェーンを乗算するために必要なスカラー乗算の最小回数を m[i,j] と呼びます (つまり、A _i × .... × A _j、つまり i<=j)。チェーンを i <= k < j となるような行列 k で分割し、どの組み合わせで m[i,j] が最小になるかを調べます。

式は次のとおりです。

       i = jの場合、m[i,j]= 0、
        i < jの場合、kのすべての可能な値にわたってm[i,j]= min (m[i,k]+m[k+1,j] + )${\displaystyle p_{i-1}*p_{k}*p_{j}}$ 

ここでkの範囲はiからj −1までです 。

• ⁠ ⁠ は${\displaystyle p_{i-1}}$行列 i の行次元であり、
• ⁠ ⁠ は${\displaystyle p_{k}}$行列kの列次元であり、
• ⁠ ⁠ は${\displaystyle p_{j}}$行列 j の列次元です。

この式は以下のようにコード化できます。入力パラメータ「chain」は行列のチェーン、つまり⁠ ⁠${\displaystyle A_{1},A_{2},...A_{n}}$です。

関数OptimalMatrixChainParenthesis(チェーン)
    n = 長さ(チェーン)
    i = 1, nの場合
        m[i,i] = 0     // 1つの行列を掛け合わせるのに計算は必要ないので、
    len = 2、n、
         i = 1、n - len + 1
            j = i + 長さ -1
            m[i,j] = infinity       // 最初の計算が更新されるように、
             k = i, j-1 の
                場合q = m[i, k] + m[k+1, j] + ${\displaystyle p_{i-1}*p_{k}*p_{j}}$
                if q < m[i, j]      // 新しい括弧の順序は、以前のものよりも優れています
                    m[i, j] = q     // 更新
                    s[i, j] = k     // どの k で分割するか、つまり括弧をどこに置くかを記録します

これまで、行列iから行列jへのチェーンを乗算するための計算の最小回数であるすべての可能なm [ i , j ]の値を計算し、対応する「分割ポイント」s [ i , j ]を記録しました。たとえば、チェーンA ₁ ×A ₂ ×A ₃ ×A ₄を乗算していて、m [1, 3] = 100でs [1, 3] = 2 であることが判明した場合、行列 1 から 3 の括弧の最適な配置は⁠ ⁠であり、これらの行列を乗算するには 100 回のスカラー計算が必要になることを意味します。 ${\displaystyle (A_{1}\times A_{2})\times A_{3}}$

このアルゴリズムは、i と j のすべての可能な値のエントリを含む「テーブル」m [, ] とs [, ] を生成します。チェーン全体の最終的なソリューションは m[1, n] であり、対応する分割は s[1, n] です。ソリューションの解明は、上から開始して基本ケース、つまり単一行列の乗算に到達するまで、再帰的に行われます。

したがって、次のステップは、実際にチェーンを分割すること、つまり括弧を（最適に）属する場所に配置することです。この目的のために、次のアルゴリズムを使用できます。

関数PrintOptimalParenthesis(s, i, j)
    の場合i = j
        「A」を印刷します
    それ以外
        印刷 "("
        最適な括弧を印刷します(s, i, s[i, j])
        最適な括弧を印刷します(s, s[i, j] + 1, j)
        印刷 ")"

もちろん、このアルゴリズムは実際の乗算には役立ちません。このアルゴリズムは、結果がどのようになるかを確認するためのユーザーフレンドリーな方法にすぎません。

適切な分割を使用して実際に行列を乗算するには、次のアルゴリズムが必要です。

   function MatrixChainMultiply ( chain from 1 to n ) // 最終行列、つまり A1×A2×... ×An を返します。OptimalMatrixChainParenthesis ( chain from 1 to n ) // これにより、s[ . ] と m[ . ] の「テーブル」が生成されます。OptimalMatrixMultiplication ( s 、chain from 1 to n ) //実際には乗算します。            
             
             

   function OptimalMatrixMultiplication ( s , i , j ) // Ai から Aj までの行列のチェーンを最適な方法で乗算した結果を返します。if i < j //チェーンを分割し、左側と右側の行列を乗算し続けます。LeftSide = OptimalMatrixMultiplication ( s , i , s [ i , j ]) RightSide = OptimalMatrixMultiplication ( s , s [ i , j ] + 1 , j ) return MatrixMultiply ( LeftSide , RightSide ) else if i = j return Ai // 位置 i の行列else print "エラー、i <= j である必要があります"      
         
         
              
                
            
          
             
       
          

    function MatrixMultiply ( A , B ) // 2 つの行列を乗算する関数if columns ( A ) = rows ( B ) for i = 1 , rows ( A ) for j = 1 , columns ( B ) C [ i , j ] = 0 for k = 1 , columns ( A ) C [ i , j ] = C [ i , j ] + A [ i , k ] * B [ k , j ] return C else print "エラー、互換性のない次元です。"      
          
             
                
                  
                   
                            
                 
       
           

動的計画法という用語は、1940年代にリチャード・ベルマンによって、次々に最善の決定を見つけなければならない問題を解決するプロセスを説明するために最初に使用されました。1953年までに、彼はこれを現代的な意味に洗練し、特に小さな決定問題を大きな決定の中に入れ子にすることを指し示しました^[16] 。 その後、この分野はIEEEによってシステム分析とエンジニアリングのトピックとして認められました。ベルマンの貢献は、最適化問題を再帰形式で言い換えた動的計画法の中心的な結果であるベルマン方程式の名前で記憶されています。

ベルマンは、自伝『ハリケーンの目：自伝』の 中で、動的プログラミングという用語の背景にある理由を次のように説明しています。

私は 1950 年の秋学期をRANDで過ごしました。私の最初の仕事は、多段階の意思決定プロセスに名前をつけることでした。興味深い質問は、「ダイナミック プログラミングという名前はどこから来たのか」です。1950 年代は数学研究にとって良い年ではありませんでした。ワシントンにウィルソンという非常に興味深い紳士がいました。彼は国防長官でしたが、実際に「研究」という言葉に対して病的な恐怖と嫌悪感を抱いていました。私はこの言葉を軽々しく使っているのではなく、正確に使っています。彼の目の前で人々が「研究」という言葉を使うと、彼は顔が赤くなり、怒り狂い、暴力を振るいました。当時、彼が数学という言葉に対してどう感じていたかは想像がつくでしょう。RAND 社は空軍に雇用されており、空軍は基本的にウィルソンを上司としていました。したがって、私は、自分が RAND 社で実際に数学を研究しているという事実からウィルソンと空軍を守るために何かをしなければならないと感じました。どのような肩書き、どのような名前を選べばよいのでしょうか。そもそも私は計画、意思決定、思考に興味があったのです。しかし、計画という言葉は、さまざまな理由から適切な言葉ではありません。そこで私は「プログラミング」という言葉を使うことにしました。これは動的であり、多段階的であり、時間によって変化するという考えを伝えたかったのです。一石二鳥だと思いました。古典的な物理的な意味で、絶対的に正確な意味を持つ言葉、つまり「動的」という言葉を取り上げましょう。また、形容詞として非常に興味深い特性があり、「動的」という言葉を軽蔑的な意味で使用することは不可能です。軽蔑的な意味を与える可能性のある組み合わせを考えてみてください。不可能です。したがって、動的プログラミングは良い名前だと思いました。それは、議員でさえ反対できないものでした。そこで、私は自分の活動の傘としてそれを使用したのです。

— リチャード・ベルマン『ハリケーンの目：自伝』（1984年、159ページ）

ベルマンは、問題の時間的に変化する側面を捉えるために、また、響きが印象的であることから、ダイナミックという言葉を選びました。[ 11 ^]プログラミングという言葉は、軍事訓練や兵站のスケジュールという意味で、最適なプログラムを見つけるための手法の使用を指していました。この用法は、線形計画法や数理計画法（数理最適化の同義語）という語句での使用法と同じです。^[17]

この用語の起源に関する上記の説明は不正確かもしれない。ラッセルとノーヴィグによれば、上記の話は「厳密には真実ではない。なぜなら、この用語を使用した最初の論文（ベルマン、1952年）は、ウィルソンが1953年に国防長官になる前に発表されたからである」^[18]。また、ハロルド・J・クシュナーはスピーチで「一方で、私がベルマンに同じ質問をしたとき、彼は、動的計画法を追加することでダンツィヒの線形計画法を凌駕しようとしていると答えた。おそらく、両方の動機が真実だったのだろう」と述べた^[19]。