動的計画法
- 提唱者
- Richard Bellman
- 年
- 1957
- 種類
- Exact combinatorial optimization via recursive decomposition
- 系統
- Mathematical programming
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
動的計画法(DP)は、1957年にリチャード・ベルマンによって導入された、多段階意思決定問題を解くための厳密な最適化手法である。複雑な問題を単純で重複する部分問題に分解し、各部分問題を一度だけ解き、結果を保存して冗長な計算を回避する。最適性原理に基づき、問題が重複部分問題と最適部分構造を示す場合、DPは全体的な最適解を保証する。
手法の背後にある直感
都市を横断する最短経路を計画する際に、まず隣接する交差点のペア間の最短経路を見つけ、次にそれらの小さな解を上に組み合わせていく様子を想像してください。可能なすべての完全な経路を最初から再探索する代わりに、事前に計算されたローカルな回答を再利用します。動的計画法も同様に機能します。小さな部分問題の解をキャッシュするため、完全な回答を構築するには、繰り返し重い計算を行うのではなく、テーブル検索のみが必要になります。
歴史学
リチャード・ベルマンは1957年にRANDコーポレーションで勤務中に「動的計画法」という言葉を造語し、意図的に「プログラミング」という言葉をコンピュータコーディングではなく計画を指すために選んだ。彼が述べた最適性原理は、制御理論、オペレーションズリサーチ、そして後の強化学習の理論的基盤となった。古典的なDPアルゴリズム(ダイクストラの最短経路、ビタビアルゴリズム、Needleman-Wunschシーケンスアライナー)はすべて、ベルマンのフレームワークから直接派生している。
使うべき場面
動的計画法は、問題が重複部分問題と最適部分構造を持つ場合に適切である。これらの特性は、逐次的意思決定、資源配分、スケジューリング、文字列アラインメントタスクに共通する。状態空間が完全に列挙可能で管理可能なサイズである必要がある。状態変数が多数または連続である場合、この手法は次元の呪いに苦しむ。状態空間が扱いにくい問題には、近似DPまたは強化学習が好ましい代替手段となる。
限界と注意点
- 次元の呪いに苦しむ。メモリと時間の要件は、状態変数の数とともに指数関数的に増加する。
- 遷移構造と報酬関数に関する完全な事前知識が必要。近似なしでは未知の環境には適用できない。
- 状態空間は離散的または離散化可能でなければならない。連続高次元問題は、厳密性を犠牲にする近似スキームを必要とする。
- 正しい状態表現と漸化式の定式化には、かなりの問題固有の洞察が必要である。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 最適性原理を満たす問題に対して、厳密な全体的最適解を保証する。
- メモ化による冗長計算を排除し、状態数における多項式時間を達成する。
- 最適な価値だけでなく、明示的な最適な方策を生成し、容易な意思決定支援を可能にする。
- 制御理論、バイオインフォマティクス、経済学、オペレーションズリサーチを含む分野に広く適用可能。
応用
- ネットワークにおける最短経路およびルーティング問題(ベルマン・フォード、ダイクストラ変種)。
- 計算生物学におけるシーケンスアラインメント(Needleman-Wunsch、Smith-Watermanアルゴリズム)。
- オペレーションズリサーチにおける最適な資源配分およびナップサック型組み合わせ問題。
- 隠れマルコフモデル上のビタビアルゴリズムによる音声および手書き認識。
- 経済学および工学における最適制御および多期間ポートフォリオ最適化。
使い方
使い方
全体的な最適化問題は、漸化式として表現される。各状態sと決定段階nに対して、価値関数V_n(s)は、即時の最良報酬と結果として生じる次の状態の割引価値に等しい。このベルマン方程式は最適性原理を形式化する。最適経路の部分経路もまた最適でなければならない。
数式
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]漸化式は、反復的または再帰的に解かれる。価値反復では、V^*(s)は、近隣状態値の現在の推定値を使用して、収束するまですべての状態にわたって繰り返し更新される。各更新は、古い値を達成可能な最良の即時報酬と将来価値の合計で置き換え、最適性情報を状態空間全体に伝播させる。
数式
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)計算された値は、状態によってインデックス付けされたテーブルに保存される。終端状態にはゼロ(または既知の報酬)の基本値が与えられ、他のすべてのエントリは部分問題が解決されるにつれて埋められる。メモ化により、各状態は最大1回だけ評価され、指数関数的な再帰探索を状態数と段階数における多項式時間まで削減する。
数式
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}価値テーブルが完成したら、最適な方策π^*(s)は単純な貪欲なパスによって回復される。各状態について、即時報酬と後続状態の保存された値を最大化する行動を選択する。この1パス抽出は計算コストが低く、決定論的で全体的に最適な意思決定ルールをもたらす。
数式
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]よくある落とし穴
- 不十分に表現力のある状態表現を定義すると、不正確な漸化式と最適でない解につながる。
- トップダウンメモ化とボトムアップタブレーションを混同すると、スタックオーバーフローエラーや部分問題評価の順序誤りが発生する可能性がある。
- 最適部分構造を欠く問題(例:一般グラフの最長経路)にDPを適用すると、警告なしに不正確な結果が得られる。
- 累積報酬計算における数値精度を無視すると、浮動小数点実装において微妙な最適性エラーを引き起こす可能性がある。
よくある質問
動的計画法と分割統治法との違いは何ですか?
どちらも問題を部分問題に分解しますが、分割統治法は独立した部分問題が自然に一度だけ解かれると仮定します。動的計画法は重複部分問題を対象とします。同じ部分問題が複数のブランチに現れる場合、結果をメモ化して冗長な作業を回避します。重複部分問題がない場合、DPは単純な再帰に対する計算上の利点を提供しません。
トップダウンメモ化とボトムアップタブレーションのどちらを使用すべきですか?
トップダウンメモ化は、漸化式から直接実装しやすく、必要な部分問題のみを計算するため、スパースな状態空間に有利です。ボトムアップタブレーションは、再帰オーバーヘッドとスタック制限を回避し、密な状態空間に適しており、実際にはしばしば高速です。必要な部分問題のセットを予測するのが難しい場合はトップダウンを、すべて部分問題が必要になる場合はボトムアップを選択してください。
動的計画法と強化学習の関係は?
古典的なDPは、完全に既知のマルコフ決定プロセスモデル(遷移確率と報酬)を必要とします。強化学習は、モデルが未知の設定にDPのアイデアを拡張し、代わりにサンプリングされた経験を使用します。Q学習や方策勾配法のようなアルゴリズムは、明示的なモデルからではなく、相互作用から価値関数を学習する近似DP手順です。
関連する手法
参考文献
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
ISBN:978-0-691-07951-6コピーしました。