動的計画法

数学的最適化の観点から言えば、動的計画法とは通常、意思決定を時間経過に伴う一連の意思決定ステップに分解することで、意思決定を単純化することを指す。

これは、時刻iからnまでのシステムの状態を表す引数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}が得られます。

最後に、システムの初期状態におけるV1_は最適解の値である。決定変数の最適値は、既に実行された計算を遡って追跡することで、一つずつ復元することができる。

制御理論における典型的な問題は、許容可能な制御を見つけることである。$\displaystyle \mathbf {u} ^{\ast }}$これによりシステム${\displaystyle {\dot {\mathbf {x} }}(t)=\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)}$許容可能な軌道をたどる$\displaystyle \mathbf {x} ^{\ast }}$連続した時間間隔で$t₀ ≤ t ≤ t₁$コスト関数を最小化する

${\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\}}$

ハミルトン・ヤコビ・ベルマン方程式として知られる偏微分方程式では、$${\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)}$^{[ 2 ]}実際には、これは一般的に、正確な最適化関係に対する何らかの離散近似のための数値的手法を必要とする。

あるいは、連続過程を離散システムで近似すると、ハミルトン・ヤコビ・ベルマン方程式に類似した以下の漸化式が得られる。

${\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\}}$

で${\displaystyle k}$第 1 段階${\displaystyle n}$等間隔の離散時間間隔、そして${\displaystyle {\hat {f}}}$そして${\displaystyle {\hat {\mathbf {g} }}}$離散近似を表す${\displaystyle f}$そして${\displaystyle \mathbf {g} }$この関数方程式はベルマン方程式として知られており、最適化方程式の離散近似の厳密解を求めるために解くことができる。^{[ 3 ]}

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

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

重複する部分問題とは、部分問題の空間が小さくなければならないことを意味します。つまり、問題を解決する再帰アルゴリズムは、新しい部分問題を生成するのではなく、同じ部分問題を繰り返し解決する必要があります。たとえば、フィボナッチ数列を生成する再帰式F _i = F _{i − 1} + F _{i − 2}を考えてみましょう。基本ケースはF ₁  = F ₂ = 1 です。すると、F ₄₃ = F ₄₂ + F ₄₁、F ₄₂ = F ₄₁ + F ₄₀となります。ここで、F _41はF ₄₃とF ₄₂の両方の再帰部分木で解決されています。部分問題の総数は実際には少ない（わずか 43 個）にもかかわらず、このような素朴な再帰的解法を採用すると、同じ問題を繰り返し解決することになります。動的計画法はこの事実を考慮し、各部分問題を一度だけ解きます。         

これは、次の2つの方法のいずれかで実現できます。^{[ 4 ]}

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

一部のプログラミング言語では、特定の引数セットを持つ関数呼び出しの結果を自動的にメモ化して、名前による呼び出しの評価を高速化できます（このメカニズムは、必要に応じて呼び出しと呼ばれます）。一部の言語では、移植性を確保してこれが可能です（例：Scheme、Common Lisp、Perl、D）。一部の言語では、自動メモ化が組み込まれており、テーブル形式のPrologやJでは、 M.副詞によるメモ化をサポートしています。 ^{[ 5 ]}いずれの場合も、これは参照透過関数でのみ可能です。メモ化は、 Wolfram Languageなどの項書き換えベースの言語内で、容易にアクセスできる設計パターンとしても見られます。

動的計画法は、配列アライメント、タンパク質フォールディング、RNA構造予測、タンパク質-DNA結合などのタスクでバイオインフォマティクスで広く使用されています。タンパク質-DNA結合のための最初の動的計画法アルゴリズムは、1970年代に米国でチャールズ・デリシ^{[ 6 ]} 、ソビエト連邦でゲオルギー・グルスキーとアレクサンダー・ザセダテレフによってそれぞれ独立に開発されました^{[ 7 ]}。最近では、これらのアルゴリズムはバイオインフォマティクスと計算生物学で非常に人気が高まっており、特にヌクレオソームの位置決めと転写因子結合の研究で使用されています。

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

実際、ダイクストラによるアルゴリズムの背後にある論理の説明は、^{[ 11 ]}すなわち、

問題2．与えられた2つのノード間の経路のうち、全長が最小となる経路を求めよ。${\displaystyle P}$そして${\displaystyle Q}$。

私たちは、もし${\displaystyle R}$は、から最短経路上のノードです。${\displaystyle P}$に${\displaystyle Q}$後者の知識は、からの最小経路の知識を意味する${\displaystyle P}$に${\displaystyle R}$。

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

フィボナッチ数列のn番目の項を計算する際に動的計画法を用いると、その性能が大幅に向上します。以下に、数学的な定義に直接基づいた単純な実装例を示します。

function fib(n) if n <= 1 return n return 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))

特に、は3回最初から計算されました。より大規模な例では、または部分問題fib(2)の値の多くを再計算するため、アルゴリズムは指数関数的な時間を要することになります。fib

ここで、既に計算された各値をその結果にマッピングする単純なマップオブジェクトmがあると仮定しfib、それを使用して更新するように関数を変更します。結果として得られる関数は、指数時間ではなくO ( n ) の時間しか必要としません（ただし、O( n ) の空間が必要です）。

var m := map (0 → 0, 1 → 1) function fib(n) if key n is not in map 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 // n = 1 の場合はループをスキップしますvar newFib := previousFib + currentFib previousFib := currentFib currentFib := newFib 現在のFibを返す

どちらの例でも、 を一度だけ計算しfib(2)、それを使って と の両方を計算しますfib(4)。fib(3)どちらかが評価されるたびに を計算する必要はありません。

n × n行列の各行と各列にちょうど n/2 個のゼロと n/2 個のイチが含まれるように、n × n行列の各位置にゼロまたはイチの値を割り当てる問題を考えます。n が与えられた場合、異なる割り当てがいくつあるかを考えます。たとえば、n = 4の場合、5 つの可能な解があります。

${\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つのアプローチが考えられる。総当たり法、バックトラッキング法、そして動的計画法である。

総当たり攻撃は、ゼロとイチのすべての割り当てをチェックし、行と列がバランスしているもの（ゼロがn /2 個、イチがn /2個）を数えることから成ります。${\displaystyle 2^{n^{2}}}$可能な割り当てと${\displaystyle {\tbinom {n}{n/2}}^{n}}$適切な割り当てでは、この戦略は任意の大きな値には実用的ではありません。${\displaystyle n}$。

この問題のバックトラッキングは、行列要素の順序を選択し、1または0を再帰的に配置しながら、各行と各列で未割り当ての要素数と1または0の数の合計が両方とも少なくともn /2であることを確認することから成ります。総当たりよりも洗練されたアプローチですが、このアプローチではすべての解を一度ずつ訪れるため、nが6より大きい場合は実用的ではありません。解の数はすでに6以上あるためです。n  = 8 の場合、 116 963 796 250 となります。

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

例えば、上に示した最初の 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）は

1、2、90、297 200、116 963 796 250、6 736 218 287 430 460 752、...

動的計画法のアプローチを実装した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 ) = 正方形 ( i , j )に到達するための最小コスト。

ランク からnランク まで降下しながら1、各ランクにおけるすべての正方形についてこの関数の値を計算します。各ランクで最小値を持つ正方形を選択することで、ランクnとランクの間の最短経路が得られます1。

この関数はq(i, j)、その下にある３つのマス（到達できるマスはこれら３つだけなので）のいずれかに到達するための最小コストに、を加えたものに等しい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)nc(i, j)min()

function minCost(i, j) if j < 1 or j > n return infinity else if i = 1 return c(i, j) else return min ( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)

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

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

関数computeShortestPathArrays() をxから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() computeShortestPathArrays() minIndex := 1 min := q[n, 1] iが2からn までの場合、 q[n, i] < minであれば minIndex := i min := q[n, i] printPath(n, minIndex)

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

遺伝学では、配列アライメントは動的計画法が不可欠な重要なアプリケーションです。^{[ 12 ]} 通常、この問題は、要素の置換、挿入、または削除を行う編集操作を使用して、ある配列を別の配列に変換することです。各操作には関連するコストがあり、目標は総コストが最も低い編集のシーケンスを見つけることです。

この問題は再帰として自然に表現でき、シーケンス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)のコストは、関連する操作のコストを隣接するセルのコストに加算し、最適なものを選択することによって計算できます。

さまざまなバリエーションが存在する。スミス・ウォーターマンアルゴリズムとニードルマン・ウンシュアルゴリズムを参照のこと。

ハノイの塔（またはハノイの塔）は、数学的なゲームまたはパズルです。3本の棒と、大きさの異なる複数の円盤で構成されており、円盤はどの棒にもスライドさせることができます。パズルは、円盤を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)  := n個の円盤を棒hから棒tに移動させる問題の解。

n=1 の場合、問題は自明であり、S(1,h,t) = 「円盤を棒 h から棒 t に移動させる」（円盤は 1 つしか残っていない）となります。

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

有名なパズルは、建物から卵を落として、どの高さから割れ始めるかを調べるものです。以下は、N=2 個の卵と H=36 階の建物に関する説明です。^{[ 14 ]}

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 )にある場合、最悪のシナリオの下でクリティカルフロアの値を特定するために必要な最小試行回数。

^{すると、 [ 15 ]}が示される。

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の値を系統的に増やすことで、この方程式を反復的に解くのは簡単である。    

行列連鎖乗算は、動的計画法の有用性を示すよく知られた例です。例えば、工学アプリケーションでは、行列の連鎖を乗算する必要があることがよくあります。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 番目の方法の方が高速なので、この括弧の配置を使用して行列を乗算するべきです。

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

この時点で、いくつかの選択肢がありますが、その一つは、問題を重複する問題に分割し、括弧の最適な配置を計算する動的計画法アルゴリズムを設計することです。動的計画法による解法を以下に示します。

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

その式は次のとおりです。

i = jの場合、m[i,j] = 0 i < j の場合、m[i,j] = k のすべての可能な値に対する最小値(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}}$⁠ :

function OptimalMatrixChainParenthesis(chain) n = length(chain) i = 1, n の場合 m[i,i] = 0 // 行列1つを乗算するのに計算は不要です。 len = 2, n の場合、 i = 1, n - len + 1の場合 j = i + len -1 m[i,j] = 無限大 // 最初の計算は 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 _{4を乗算する場合、} m [1, 3] = 100、s [1, 3] = 2であることが判明した場合、行列 1 から 3 への括弧の最適な配置は⁠となります。${\displaystyle (A_{1}\times A_{2})\times A_{3}}$そして、それらの行列を乗算するには、100回のスカラー計算が必要になります。

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

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

function PrintOptimalParenthesis(s, i, j) if i = j 「A」i を印刷 それ以外 print "(" PrintOptimalParenthesis(s, i, s[i, j]) PrintOptimalParenthesis(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 "エラー、互換性のない次元です。"