動的計画法 - Hirari

要旨#

動的計画法（DP; Dynamic Programming）は，最適部分構造と部分問題の重複性を有する離散最適化問題に対して適用可能なアルゴリズム的枠組みである．ここでは，DPの理論的基盤を明確化し，その形式的定義，代表的アルゴリズム，ならびに制御理論やマルコフ決定過程との関連性について論じる．さらに，典型的な応用例を通してその有効性と拡張可能性を示す．

はじめに#

動的計画法は，Bellman（1957）により体系化された最適化手法であり，複雑な問題を再帰的に単純な部分問題に分解することにより解決する．DPの適用は，次の2つの条件が満たされる場合に有効である．

部分構造最適性（Optimal Substructure）問題全体の最適解が，その部分問題の最適解から構成可能であること．
部分問題重複性（Overlapping Subproblems）同一の部分問題が複数回現れるため，解を保存して再利用することが有効であること．

これらの性質に基づき，DPは数理計画，アルゴリズム設計，制御理論，機械学習等，広範な分野で応用されている．

数理的定式化#

状態空間 $\mathcal{S}$ ，行動空間（制御集合） $\mathcal{U}(s)$ ，状態遷移関数 $T: \mathcal{S} \times \mathcal{U} \to \mathcal{S}$ ，コスト関数 $c: \mathcal{S} \times \mathcal{U} \to \mathbb{R}$ が与えられたとき，価値関数 $V: \mathcal{S} \to \mathbb{R}$ は以下のベルマン方程式（Bellman Equation）を満たす：

V(s) = \min_{u \in \mathcal{U}(s)} \left[ c(s, u) + V(T(s, u)) \right]

この再帰関係に基づき，DPは状態 $s$ における最適コスト（あるいは利得）を効率的に求める．

アルゴリズム構成#

DPの実装は，以下の4要素から構成される．

状態の定義：問題の進行状況を記述する最小限の情報集合
遷移関係の構築：現在の状態から次の状態への推移と，それに伴うコストまたは報酬
初期条件の設定：基本状態における価値関数（通常は0または既知の定数）
計算順序の設計
- トップダウン（再帰＋メモ化）
- ボトムアップ（逐次計算）

応用例：0–1ナップサック問題#

問題設定：重さ $w_i$ ，価値 $v_i$ を持つ $n$ 個の品物と，容量 $W$ のナップサックが与えられ，価値の合計を最大化する．

状態定義： $dp[i][w]$ ： $i$ 番目までの品物で，重さ $w$ 以下における最大価値．

遷移式：

dp[i][w] = \begin{cases} dp[i-1][w], & \text{if } w < w_i \\ \max\left( dp[i-1][w],\ dp[i-1][w - w_i] + v_i \right), & \text{otherwise} \end{cases}

この形式は，時間計算量 $O(nW)$ ，空間計算量も $O(nW)$ を要する．空間最適化により $O(W)$ に削減可能である．

拡張技法と応用領域#

DPは多くの変種および最適化手法と組み合わされる．

区間DP（Interval DP）：文字列処理や構文解析
木DP（Tree DP）：木構造上の最適化
ビットDP：部分集合をビット列で表現し，高速化

応用例としては，列編集距離，最長共通部分列（LCS），部分和問題，巡回セールスマン問題（TSP），スケジューリング，確率過程の計算などが挙げられる．

制御理論および強化学習との関連性#

動的計画法は，離散時間最適制御理論およびマルコフ決定過程（MDP）の基礎でもある．

離散時間MDPにおいて，価値関数 $V(s)$ は以下のベルマン最適方程式に従う．

V(s) = \max_{a \in \mathcal{A}} \left[ R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V(s') \right]

ここで， $\gamma$ は割引率， $R(s,a)$ は即時報酬， $P(s’ \mid s,a)$ は状態遷移確率である．この構造は，強化学習におけるQ学習，価値反復法，方策反復法などの根幹をなす．

結論#

動的計画法は，再帰的構造と漸化式に基づき，最適化問題の体系的な解法を提供する．本手法は理論的にも実用的にも強力であり，今後も状態空間の抽象化，高次元問題への対応，学習ベースとの統合など，多くの発展が期待される．