動的計画法

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
図1.最適な下部構造を使用してグラフ内の最短経路を見つける。直線は単一のエッジを示します。波線は、接続する2つの頂点間の最短経路を示します(他の経路の中で、同じ2つの頂点を共有しています)。太線はスタートからゴールまでの全体的な最短経路です。

動的計画法は、数理最適化手法であると同時にコンピュータープログラミング手法でもあります。この方法は1950年代にリチャードベルマンによって開発され、航空宇宙工学から経済学まで、多くの分野で応用されてきました

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

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

概要

数理最適化

数理最適化の観点から、動的計画法は通常、時間の経過とともに一連の決定ステップに分解することによって決定を単純化することを指します。これは、 1からnまでの時間iでのシステムの状態を表す引数としてyを取り、値関数 V 1V 2、...、Vnのシーケンスを定義することによって行われます。V ny )の定義は、最後に状態yで取得された値です以前の時間iの値Vi =  n  −1、  n  − 2、...、 2、1は、ベルマン方程式と呼ばれる漸化式を使用して、逆方向に作業することで見つけることができます。i  = 2、...、  nV i −1の場合、任意の状態yで、時間i −1での決定からのゲイン 関数Viの単関数(通常は合計)を最大化することにより、Viから計算されますこの決定がなされた場合、システムの新しい状態で。V iは必要な状態に対してすでに計算されているため、上記の操作によりViが得られますこれらの状態の場合は-1最後に、システムの初期状態でのV 1は、最適解の値です。決定変数の最適値は、すでに実行された計算を追跡することにより、1つずつ回復できます。

制御理論

制御理論では、典型的な問題は許容可能な制御を見つけることですこれがシステムの原因となります許容軌道をたどる連続した時間間隔でコスト関数を最小化する

この問題の解決策は、最適制御法またはポリシーです。 、最適な軌道を生成します コスト機能 後者は、動的計画法の基本方程式に従います。

ハミルトン-ヤコビ-ベルマン方程式として知られる微分方程式最小化することがわかりますの面では、および未知の機能次に、結果をハミルトン-ヤコビ-ベルマン方程式に代入して、境界条件で解く偏微分方程式を取得します。[2]実際には、これには一般に、正確な最適化関係への離散近似のための 数値手法が必要です。

あるいは、連続プロセスは離散システムで近似できます。これにより、ハミルトン-ヤコビ-ベルマン方程式に類似した次の漸化式が得られます。

-の第3段階等間隔の離散時間間隔、およびここでの離散近似を示しますこの関数方程式はベルマン方程式として知られており、最適化方程式の離散近似を正確に解くために解くことができます。[3]

経済学の例:最適な貯蓄に関するラムジーの問題

経済学では、目的は一般に、動的な社会福祉機能を(最小化するのではなく)最大化することです。ラムジーの問題では、この関数は消費量を効用のレベルに関連付けます。大まかに言えば、プランナーは、同時消費と将来の消費(生産に使用される資本ストックへの投資を介して)の間のトレードオフに直面します。これは、異時点間の選択として知られています。将来の消費は一定の割合で割引されます資本の遷移方程式の離散近似は、次の式で与えられます。

どこ消費です、資本であり、稲田条件を満たす生産関数です初期資本ストック が想定されます。

させて 期間tの消費であり、消費が効用をもたらすと仮定する 消費者が生きている限り。消費者がせっかちであると仮定すると、消費者は各期間で将来の効用を係数bずつ割り引くことになります。させて期間tの資本である初期資本が所定の金額であると仮定する、そしてこの期間の資本と消費が次の期間の資本を次のように決定するとします。 、ここで、Aは正の定数であり、資本が負になることはないと仮定します。次に、消費者の決定問題は次のように書くことができます。

対象すべてのために

このように書かれていると、すべての選択変数を解く必要があるため、問題は複雑に見えます。(首都は選択変数ではありません—消費者の初期資本は与えられたとおりに取られます。)

この問題を解決するための動的計画法のアプローチでは、問題を一連の小さな決定に分解します。そのために、一連の値関数を定義します 、 にとってこれは、各時間tで任意の量の資本kを持つことの値を表します。(仮定により)死後の資本を持つことによる効用はありません、

以前の任意の量の資本の値は、ベルマン方程式を使用した後ろ向き帰納法によって計算できます。この問題では、それぞれについて、ベルマン方程式は

対象

この問題は、2つの決定変数しか含まないため、以前に書き留めた問題よりもはるかに単純です。直感的には、出生時に生涯計画を選択する代わりに、消費者は一度に一歩ずつ物事を進めることができます。時間tで、彼の現在の首都与えられ、彼は現在の消費量を選択するだけで済みますと節約

この問題を実際に解決するために、逆方向に作業します。簡単にするために、現在の資本レベルはkで表されます。はすでに知られているので、計算できたらベルマン方程式を使用します、など、、これは生涯にわたる初期決定問題の値です。言い換えれば、私たちが知ったら、計算できます、の最大値です、 どこ選択変数であり、

逆方向に作業すると、値が時間で機能することを示すことができます

ここでそれぞれは一定であり、その時点で消費するのに最適な量です

これは次のように簡略化できます

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

コンピュータプログラミング

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

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

重複するサブ問題は、サブ問題のスペースが小さくなければならないことを意味します。つまり、問題を解決する再帰的アルゴリズムは、新しいサブ問題を生成するのではなく、同じサブ問題を繰り返し解決する必要があります。たとえば、フィボナッチ数列を生成するための再帰的定式化について考えてみます。Fi = F i −1 + F i −2 ベースケースF 1 = F 2 =  1 です次に 、F 43F 42  +  F 41、およびF 42F 41  +  F40現在、F 41は、 F43F42の両方の再帰サブツリーで解決されてますサブ問題の総数は実際には少ないですが(そのうち43個のみ)、このような単純な再帰的ソリューションを採用すると、同じ問題を何度も解決することになります。動的計画法はこの事実を考慮し、各サブ問題を1回だけ解決します。

図2.フィボナッチ数列のサブ問題グラフ。ツリーではないという事実は、サブ問題が重複していることを示しています。

これは、次の2つの方法のいずれかで実現できます。[要出典]

  • トップダウンアプローチ:これは、問題の再帰的定式化の直接的なフォールアウトです。サブ問題の解決策を使用して問題の解決策を再帰的に定式化でき、サブ問題の解決策が重複している場合は、サブ問題の解決策を簡単にメモ化またはテーブルに保存できます。新しいサブ問題を解決しようとするときはいつでも、最初にテーブルをチェックして、それがすでに解決されているかどうかを確認します。解決策が記録されている場合は、それを直接使用できます。それ以外の場合は、サブ問題を解決して、その解決策をテーブルに追加します。
  • ボトムアップアプローチ:サブ問題の観点から問題の解決策を再帰的に定式化したら、ボトムアップ方式で問題の再定式化を試みることができます。最初にサブ問題を解決し、その解決策を使用して構築します。より大きなサブ問題の解決策に到達します。これは通常、小さなサブ問題のソリューションを使用して、ますます大きなサブ問題のソリューションを繰り返し生成することにより、表形式で実行されます。たとえば、 F41F40の値がすでにわかっている場合はF42の値を直接計算できます

一部のプログラミング言語では、名前による呼び出しの評価を高速化するために、特定の引数のセットを使用して関数呼び出しの結果を自動的にメモ化できますこのメカニズムは必要に応じた呼び出しと呼ばれます)。いくつかの言語はそれを移植可能にします(例えば、 SchemeCommon LispPerlまたはD)。テーブル化されたPrologJなど、一部の言語には自動メモ化機能 が組み込まれており、 M。副詞によるメモ化をサポートしています。[4]いずれの場合も、これは参照透過性の場合にのみ可能です関数。メモ化は、 Wolfram言語などの用語書き換えベースの言語内で簡単にアクセスできるデザインパターンとしても使用されます。

バイオインフォマティクス

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

例:コンピューターアルゴリズム

最短経路問題に対するダイクストラのアルゴリズム

動的計画法の観点から、最短経路問題に対するダイクストラのアルゴリズムは、到達法 によって最短経路問題の動的計画法関数方程式を解く逐次近似スキームです[7] [8] [9]

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

問題2.指定された2つのノード間の最小全長のパスを見つけます

私たちは、からの最小パス上のノードです、後者の知識は、からの最小パスの知識を意味します

は、最短経路問題のコンテキストでのベルマンの有名な最適性の原則の言い換えです

フィボナッチ数列

フィボナッチ数列のn番目のメンバーの計算に動的計画法を使用すると、パフォーマンスが大幅に向上します。これは、数学的な定義に直接基づいた単純な実装です。

関数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))

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

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

var m:= map(0→0、1→1)
関数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  // n = 1の場合、ループはスキップされます
            var newFib:= previousFib + currentFib
            previousFib:= currentFib
            currentFib:= newFib
        currentFibを
返す

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

上記の方法は実際にかかります2つの整数を加算するため、nが大きい場合の時間それぞれが取るビット時間。n番目のフィボナッチ数はビット。)また、ビネットの式として知られているフィボナッチ数列の閉じた形があり、そこから-第3項はおよそで計算できます時間。これは、上記の動的計画法よりも効率的です。ただし、単純な繰り返しにより、行列形式が直接得られます。高速行列指数によるアルゴリズム

バランスの取れた0–1行列の一種

各行と各列に正確にn / 2個のゼロとn / 2個のゼロが含まれるように、 n × n行列の位置にゼロまたは1の値を割り当ててnを偶数にする問題を考えてみます。与えられたものに対していくつの異なる割り当てがあるかを尋ねますたとえば、n = 4の場合、5つの可能な解決策は次のとおりです。

少なくとも3つの可能なアプローチがあります:ブルートフォースバックトラック、および動的計画法。

ブルートフォースは、0と1のすべての割り当てをチェックし、行と列のバランスが取れているもの(n / 2の0とn / 2の1)をカウントすることで構成されます。あるので可能な割り当てと賢明な割り当て、この戦略は多分最大までを除いて実用的ではありません

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

動的計画法により、すべてのソリューションにアクセスしなくても、ソリューションの数を数えることができます。最初の行のバックトラック値を想像してみてください。最初の行の値ごとに得られた解を正確にカウントできるようにするために、残りの行についてどのような情報が必要でしょうか。1≤k≤nあるk × nボードを検討します行に含まれるゼロともの。メモ化が適用される関数fは、 n組の整数のベクトルを許容されるボード(解)の数にマップします。各列に1つのペアがあり、その2つのコンポーネントは、それぞれ、その列にまだ配置されていない0と1の数を示します。私たちはの価値を追求します((引数またはの1つのベクトル要素)。サブ問題の作成プロセスには、すべての問題を反復処理することが含まれます。 ボードの一番上の行の可能な割り当て、およびすべての列を調べ、一番上の行の割り当てにその位置に0または1が含まれていたかどうかに応じて、その列のペアの適切な要素から1を減算します。結果のいずれかが負の場合、割り当ては無効であり、一連のソリューションに寄与しません(再帰が停止します)。それ以外の場合は、k × nボードの一番上の行に割り当てがあり、残りの(k − 1)× nボードの解の数を再帰的に計算し、一番上の行のすべての許容可能な割り当ての解の数を加算して、記憶されている合計。基本的なケースは、次の場合に発生する些細なサブ問題です。nボード。このボードの解の数は、ベクトルがn / 2の順列であるかどうかに応じて、0または1のいずれかになります。 およびn / 2 ペアかどうか。

たとえば、上記の最初の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)は 次のとおりです。

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

チェッカーボード

n × n個の正方形と、正方形(行、列)に関連付けられたコストを返すコスト関数を備えたチェッカーボードについて考えてみます。たとえば(5×5のチェッカーボード上)、 c(i, j)(i,j)ij

5 6 7 4 7 8
4 7 6 1 1 4
3 3 5 7 8 2
2 6 7 0
1 * 5 *
1 2 3 4 5

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

最初のランク(つまり、行)の任意の正方形から開始できるチェッカーがあり、最後のランクに到達するための最短経路(訪問した各ランクの最小コストの合計)を知りたいとします。チェッカーが斜め左前方、斜め右前方、または真っ直ぐ前方にしか移動できないと仮定します。つまり、上のチェッカーは、、または(1,3)移動できます。 (2,2)(2,3)(2,4)

5
4
3
2 バツ バツ バツ
1 o
1 2 3 4 5

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

qij )=正方形( ij )に到達するための最小コスト

ランクから始まり、ランクnに向かって降順1で、連続する各ランクのすべての正方形についてこの関数の値を計算します。各ランクで最小値を保持する正方形を選択すると、ランクnとランクの間の最短経路が得られ1ます。

この関数q(i, j)は、その下にある3つの正方形のいずれかに到達するための最小コスト(それらが到達できる唯一の正方形であるため)にプラスを加えたものに等しくなりますc(i, j)例えば:

5
4 A
3 B C D
2
1
1 2 3 4 5

q(i, j)ここで、もう少し一般的な用語で 定義しましょう。

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

関数minCost(i、j)
     if j <1またはj> n
        は無限大
    を返しますelseif 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)

         

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

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

1からnまでxの関数computeShortestPathArrays()
    
        q [1、x]:= c(1、x)
    1からnまでyの場合
        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]
    q [n、i] <minの場合、i場合2からn
        
            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])

配列アラインメント

遺伝学では配列アラインメントは動的計画法が不可欠な重要なアプリケーションです。[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アルゴリズムを参照してください。

ハノイの塔パズル

ハノイの塔のモデルセット(8枚のディスク付き)
T(4,3)のハノイの塔パズルのアニメーションソリューション

ハノイの塔またはハノイは、数理ゲームまたはパズルです。これは、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つしか残っていません)。

このソリューションに必要な移動数は2n  − 1です。目的が(循環なしで)移動数を最大化することである場合、動的計画法の関数方程式 は少し複雑になり、3 n  −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 =(NH)です。ここで、Nは、実験の開始時に利用可能なテスト卵の数を示します。テストエッグがなくなると(n = 0)、またはk = 0になると、プロセスは終了します。状態s =(0、k)およびk > 0で終了が発生した場合 、テストは失敗しました。

さあ、

Wnk )=プロセスが状態s =(nk )にある場合、最悪のシナリオでクリティカルフロアの値を特定するために必要な最小試行回数

次に、[14]

Wnk)= 1 + min {max(Wn − 1、x − 1)、Wnkx)):x = 1、2、...、k }

すべてのn  > 0に対してW(n、0)= 0でありすべてkに対して1k)= kです。nと kの値を体系的に増やすことにより、この方程式を繰り返し解くのは簡単です。

別のパラメータ化を使用したより高速なDPソリューション

上記の解決策はDPソリューションとの時間。これは次のように改善できます最適な二分探索による時間上記の再発では、で増加していますその間で減少しています、したがって、極小値はグローバル最小値です。また、最適なものを保存することによりDPテーブルの各セルについて、前のセルの値を参照すると、最適各セルは一定時間で見つけることができ、それを改善します時間。ただし、問題の異なるパラメーター化を含むさらに高速なソリューションがあります。

させて から落としたときに卵が割れるような床の総数3階(上記の例は)。

させて 卵を壊すために落とさなければならない最小の床である。

させて の値の最大数になりますを使用して区別できるしようと卵。

それですべてのために

させて 最適な戦略で最初の卵を落とす床になります。

最初の卵が壊れた場合、からせいぜい使用して区別できるしようと卵。

最初の卵が壊れなかった場合、からと区別できるしようと卵。

したがって、

その場合、問題は最小値を見つけることと同じですそのような

そうするために、私たちは計算することができます昇順時間。

したがって、個別に次の場合を処理する場合、アルゴリズムは時間。

しかし、漸化式は実際には解くことができ、、で計算できますアイデンティティを使用する時間すべてのために

以来すべてのために、二分探索ができます見つけるには、与えるアルゴリズム。[15]

行列の連鎖乗積

行列の連鎖乗積は、動的計画法の有用性を示すよく知られた例です。たとえば、エンジニアリングアプリケーションでは、多くの場合、行列の連鎖を乗算する必要があります。たとえば100×100などの大きな次元の行列を見つけることは驚くべきことではありません。したがって、私たちのタスクは行列を乗算することです行列の乗算は可換ではありませんが、結合法則です。一度に乗算できる行列は2つだけです。したがって、この行列の連鎖をさまざまな方法で乗算できます。たとえば、次のようになります。

((A1 × A2 ×A 3)×... A n
A 1 ×(((A2 × A3 ×...)×A n
(A1 × A2 ×(A3 × ... 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]と呼びましょう(つまり、Ai ×....× Aj 、つまりi <= j)i <= k <jとなるように、ある行列kでチェーンを分割し、どの組み合わせが最小のm [i、j]を生成するかを見つけようとします。

式は次のとおりです。

       i = jの場合、m [i、j] = 0
        i <jの場合、m [i、j] = kのすべての可能な値に対して最小(m [i、k] + m [k + 1、j] +)。 

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

  • 行列iの行の次元です。
  • 行列kの列の次元です。
  • 行列jの列の次元です。

この式は、次のようにコーディングできます。ここで、入力パラメーター「chain」は行列のチェーンです。

関数OptimalMatrixChainParenthesis(チェーン)
    n =長さ(チェーン)
    i = 1の場合、n
        m [i、i] = 0     //
     len = 2の場合
        は1つの行列を乗算するのに計算が必要ないため、 i = 1の場合はn、n --len + 1
            j = i + len -1
            m [i、j] = infinity       //
             k = i、j-1
                の最初の計算が更新されるようにq = m [i、k] + m [k + 1、j] +
                if q <m [i、j]      //括弧の新しい順序は私たちが持っていたものよりも優れています
                    m [i、j] = q     //更新
                    s [i、j] = k     //分割するkを記録します。つまり、括弧を配置する場所

これまで、可能なすべてのm [ ij ]の値を計算しました。これは、行列iから行列jへのチェーンを乗算するための最小計算数であり、対応する「分割点」s [ ij ]を記録しました。たとえば、チェーンA1×A2×A3×A4を乗算している場合m [ 1、3 ] = 100およびs [ 1、3 ] = 2あることがわかります。これは、行列1から3の括弧はこれらの行列を乗算するには、100個のスカラー計算が必要になります。

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

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

関数PrintOptimalParenthesis(s、i、j)
     if i = j
        「A」iを印刷
    それ以外
        印刷 "("
        PrintOptimalParenthesis(s、i、s [i、j])
        PrintOptimalParenthesis(s、s [i、j] + 1、j)
        印刷 ")"

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

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

   function  MatrixChainMultiply chain  from  1  to  n        //最終的な行列を返します。つまりA1×A2×...× 
      OptimalMatrixChainParenthesis chain  from  1  to  n    //これはs [を生成します。] そしてM[ 。] "tables" 
      OptimalMatrixMultiplication s  1からnまでのチェーン //実際に乗算     

   function  OptimalMatrixMultiplication s  i  j ) //    i < jの場合、AiからAjまでの行列のチェーンを最適な方法で乗算した結果を返します//
      チェーンを分割し続け、左側と右側の行列を乗算します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の行列
      elseprint "  
         error、i <= j must hold" 

    function  MatrixMultiply A  B     //
      A =B for i = 1 A for j = 1 B C [ i j ] = 0の場合、 2つの行列を乗算する関数 k = 1の場合A C [   
             
                
                  
                   
                   i  j ]  =  C [ i  j ]  +  A [ i  k ] * B [ k  j ]  
               return  C  
      else  
          print  "エラー、互換性のない寸法"。

歴史

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

ベルマンは、彼の自伝「ハリケーンの目:自伝: 」で動的計画法という用語の背後にある理由を説明しています。

私は(1950年の)秋の四半期をRANDで過ごしました私の最初の仕事は、多段階の意思決定プロセスの名前を見つけることでした。興味深い質問は、「動的計画法という名前はどこから来たのですか?」です。1950年代は、数学の研究にとって良い年ではありませんでした。ワシントンにはウィルソンという非常に興味深い紳士がいましたこれは動的であり、多段階であり、時間とともに変化するという考えを理解したかったのです。一石二鳥しようと思った。古典的な物理的な意味で、絶対的に正確な意味、つまり動的な意味を持つ単語を取り上げましょう。また、形容詞として非常に興味深い性質を持っており、それは蔑称的な意味でダイナミックという言葉を使用することは不可能です。蔑称的な意味を与える可能性のある組み合わせを考えてみてください。それは不可能だ。したがって、動的計画法は良い名前だと思いました。それは国会議員でさえ反対できないものでした。それで、私はそれを私の活動の傘として使用しました。つまり、古典的な物理的な意味での動的です。また、形容詞として非常に興味深い性質を持っており、それは蔑称的な意味でダイナミックという言葉を使用することは不可能です。蔑称的な意味を与える可能性のある組み合わせを考えてみてください。それは不可能だ。したがって、動的計画法は良い名前だと思いました。それは国会議員でさえ反対できないものでした。それで、私はそれを私の活動の傘として使用しました。

— リチャード・ベルマン、ハリケーンの目:自伝(1984年、159ページ)

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

用語の起源についての上記の説明は欠けています。ラッセルとノーヴィグが本の中で書いているように、上記の話を参照して、「ウィルソンが1953年に国防長官になる前に、この用語を使用した彼の最初の論文(ベルマン、1952)が登場したため、これは厳密には真実ではありません。」[18]また、ハロルド・J・クシュナーの演説には、ベルマンを思い出すコメントがあります。クシュナーがベルマンについて語るときの引用:「一方、私が彼に同じ質問をしたとき、彼はダイナミックを追加することによってダンツィーグの線形計画法を上演しようとしていると答えました。おそらく両方の動機が真実でした。」

動的計画法を使用するアルゴリズム

も参照してください

参考文献

  1. ^ a b コルメン、TH; Leiserson、CE; リベスト、RL; Stein、C。(2001)、Introduction to Algorithms(2nd ed。)、MIT Press&McGraw–Hill ISBN0-262-03293-7 pp。344。
  2. ^ カミエン、MI ; シュワルツ、NL(1991)。動的最適化:経済学と管理における変分法と最適制御(第2版)。ニューヨーク:エルゼビア。p。261. ISBN 978-0-444-01609-6
  3. ^ カーク、ドナルドE.(1970)。最適制御理論:はじめに。ニュージャージー州エングルウッドクリフ:プレンティスホール。pp。94–95。ISBN 978-0-13-638098-6
  4. ^ 「M。メモ」J語彙Jソフトウェア2011年10月28日取得
  5. ^ DeLisi、Biopolymers、1974年、第13巻、第7号、1511〜1512ページ、1974年7月
  6. ^ GurskiĭGV、Zasedatelev AS、Biofizika、1978年9月-10月; 23(5):932-46
  7. ^ Sniedovich、M。(2006)、「ダイクストラのアルゴリズムの再検討:動的計画法の接続」(PDF)Journal of Control and Cyber​​netics35(3):599–620。 インタラクティブな計算モジュールを備えたオンライン版の論文。
  8. ^ Denardo、EV(2003)、動的計画法:モデルとアプリケーション、ニューヨーク州ミネオラ:Dover PublicationsISBN 978-0-486-42810-9
  9. ^ Sniedovich、M。(2010)、動的プログラミング:基礎と原則テイラー&フランシスISBN 978-0-8247-4099-3
  10. ^ Dijkstra 1959、p。270
  11. ^ a b c Eddy、SR(2004)。「動的計画法とは」。ネイチャーバイオテクノロジー22(7):909–910。土井10.1038 / nbt0704-909PMID15229554_ S2CID5352062_  
  12. ^ Moshe Sniedovich(2002)、「OR / MSゲーム:2。ハノイの塔問題」、教育に関するINFORMSトランザクション3(1):34–51、doi10.1287 /ited.3.1.45
  13. ^ Konhauser JDE、Velleman、D。、およびWagon、S。(1996)。自転車はどちらに行きましたか?Dolciani Mathematical Expositions – No18 。アメリカ数学協会
  14. ^ Sniedovich、Moshe(2003)。「OR / MSゲーム:4。ブラウンシュヴァイクと香港での卵の落下の喜び」教育に関するINFORMSトランザクション4:48–64。土井10.1287 /ited.4.1.48
  15. ^ Dean Connable Wills、順列の組み合わせ論とアルゴリズムおよび幾何学の間の接続
  16. ^ スチュアートドレイファス。「動的プログラミングの誕生に関するリチャード・ベルマン」
  17. ^ Nocedal、J。; ライト、SJ(2006)。数値最適化スプリンガー。p。 9ISBN 9780387303031
  18. ^ ラッセル、S。; Norvig、P。(2009)人工知能:現代的なアプローチ(第3版)。プレンティスホール。ISBN 978-0-13-207148-2

さらに読む

外部リンク