Dynamic programming — 動的計画法

動的計画法（DP; 英語: dynamic programming）は、複雑な最適化問題を、元の問題をより単純な部分問題の列に分割することによって解く手法である。この手法は多段階の意思決定プロセスに適用され、問題全体の最適解がその部分問題の最適解から構築できる場合に用いられる。

この用語は、1950年代にアメリカの数学者リチャード・ベルマンによって導入された。この文脈における「プログラミング」という言葉は、コンピュータコードを書くことではなく、「計画」や「最適な行動計画の作成」を意味する。

主要な特性と定理

ある問題に動的計画法が適用可能かどうかは、その問題が2つの基本的な特性を持つかどうかによって決まる。

ベルマンの最適性の原理

この手法の中心的な概念はベルマンの最適性の原理（英語: Bellman's principle of optimality）である。この原理は、「最初の状態と最初の決定がどのようなものであっても、その後の決定は、最初の決定の結果として生じた状態に関して、最適な戦略を構成しなければならない」と述べている。

言い換えれば、最適経路のどの部分も、それ自体が最適でなければならない。この特性により、全体の問題をより単純な部分問題の列に分割し、再帰的に解くことが可能になる。

部分問題の重複

ある問題が部分問題の重複（英語: overlapping subproblems）という特性を持つのは、その問題を再帰的に解く過程で、同じ部分問題が何度も出現する場合である。DPは、すでに出現した部分問題の解を保存する（この手法はメモ化またはテーブル化と呼ばれる）ことで、再計算を回避する。これにより、単純な再帰的な全探索に比べて効率が大幅に向上する。

ベルマン方程式

最適性の原理から、この手法の基本的な漸化式であるベルマン方程式が導かれる。この方程式は、現在の状態の「価値」（最適な利得またはコスト）を、後続の状態の価値と関連付ける。決定論的な多段階プロセスで、目的関数が加法的な場合、一般形は次のようになる。

$V_{k-1}(x)=\underset{y\in U(x)}{\max }\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

ここで：

• $k$ — ステップの番号（$m$から1まで）;
• $x$ — ステップ$k-1$におけるシステムの状態;
• $y$ — ステップ$k$で行われる制御決定;
• ${\phi }_k(x,y)$ — k番目のステップでの利得（またはコスト）;
• $f_k(x,y)$ — システムの新しい状態を定義する関数;
• $V_k(s)$ — 状態$s$でステップ$k$から始まる部分問題に対する目的関数の最適値。

この方程式は通常、「後ろから」最後のステップから最初のステップへと順次解かれる。

適用例

• グラフにおける最短経路問題: この問題は最適な部分構造を持つ。なぜなら、最短経路のどの部分もそれ自体が最短経路だからである。ベルマン-フォード法やフロイド-ワーシャル法は、この問題を解くためのDPの古典的な適用例である。
• ナップサック問題: 容量が限られたナップサックに、価値と重さが異なる品物を最適に詰める問題。DPを用いると、品物を順に考慮し、各ステップで残りの容量のすべての可能な値に対して最大の価値を計算することで、この問題を解くことができる。
• 資源配分問題: 限られた資源（例えば、投資）を複数のプロジェクトに配分し、全体の効果を最大化する問題。

限界

この手法の主な限界は次元の呪い（英語: curse of dimensionality）である。これは、システムの状態を記述する変数の数が増加するにつれて、状態の数が指数関数的に増加し、結果として計算の複雑さも増大することを指すためにベルマンが導入した用語である。これにより、非常に高次元の問題に対して厳密なDPを実用的に適用することが制限される。