ダイナミック・プログラミング(読み)だいなみっくぷろぐらみんぐ(英語表記)dynamic programming

日本大百科全書(ニッポニカ) の解説

ダイナミック・プログラミング
だいなみっくぷろぐらみんぐ
dynamic programming

資源の配分問題、投資問題、スケジューリング問題、生産管理問題、在庫管理問題などは、状況の変化に応じて何度も繰り返して決定を行う、いわゆる多段決定問題として定式化される。

 このような問題で、各段階で行うべき決定を逐次求める手法がダイナミック・プログラミングであり、DPと略したり、動的計画法ともよぶ。1950年代にアメリカの数学者ベルマンR. Bellmanによって創始された。このDPは次に示す「最適性の原理」とよばれる性質を基礎にしている。

 すなわち「最適政策とは、初期の状態と最初の決定が何であろうとも、それ以後の決定は最初の決定によって生じた状態に関して最適政策となるように構成しなければならない」とする。

 多段決定問題はに示すように、状態の集合S、決定の集合D、状態変換T、段階の利得R、さらにマルコフ性によって特徴づけられる。ダイナミック・プログラミングは多段階の決定問題に最適性の原理を適用して、各段階での利得に関する再帰関係式を逐次解くことによって最適政策が得られるのである。

[玄 光男]


出典 小学館 日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について 情報 | 凡例

ブリタニカ国際大百科事典 小項目事典 の解説

ダイナミック・プログラミング

動的計画法」のページをご覧ください。

出典 ブリタニカ国際大百科事典 小項目事典ブリタニカ国際大百科事典 小項目事典について 情報

今日のキーワード

青天の霹靂

《陸游「九月四日鶏未鳴起作」から。晴れ渡った空に突然起こる雷の意》急に起きる変動・大事件。また、突然うけた衝撃。[補説]「晴天の霹靂」と書くのは誤り。[類語]突発的・発作的・反射的・突然・ひょっこり・...

青天の霹靂の用語解説を読む

コトバンク for iPhone

コトバンク for Android