日本大百科全書(ニッポニカ) の解説
ダイナミック・プログラミング
だいなみっくぷろぐらみんぐ
dynamic programming
資源の配分問題、投資問題、スケジューリング問題、生産管理問題、在庫管理問題などは、状況の変化に応じて何度も繰り返して決定を行う、いわゆる多段決定問題として定式化される。
このような問題で、各段階で行うべき決定を逐次求める手法がダイナミック・プログラミングであり、DPと略したり、動的計画法ともよぶ。1950年代にアメリカの数学者ベルマンR. Bellmanによって創始された。このDPは次に示す「最適性の原理」とよばれる性質を基礎にしている。
すなわち「最適政策とは、初期の状態と最初の決定が何であろうとも、それ以後の決定は最初の決定によって生じた状態に関して最適政策となるように構成しなければならない」とする。
多段決定問題はに示すように、状態の集合S、決定の集合D、状態変換T、段階の利得R、さらにマルコフ性によって特徴づけられる。ダイナミック・プログラミングは多段階の決定問題に最適性の原理を適用して、各段階での利得に関する再帰関係式を逐次解くことによって最適政策が得られるのである。
［玄 光男］
