トップ > 数理計画用語集 > 動的計画法

数理計画用語集

動的計画法

読み:どうてきけいかくほう
英名:Dynamic Programming
関連多段階決定過程最適性原理

動的計画法は応用数学者 Richard E. Bellman によって初めて使われた言葉であり,最適性原理を持つ多段階決定過程に対して適用できる特別なアルゴリズムである.全般的にツリーで表現される全探索問題に対する手法で,指数的に爆発する探索ツリーを多項式時間の問題に置き換えるものなど,劇的に探索範囲を小さくするという特徴がある.基本的に計算機で解くことを前提としたアルゴリズムで,実装する場合には再帰構造を持ちメモリを潤沢に使ったものになることが多い.

[参考]
鍋島一郎著,数学ライブラリ-7動的計画法,森北出版株式会社,1968
広中平祐監修,現代数理科学事典,大阪書籍,1991