「Dynamic programming」の意味や使い方わかりやすく解説 Weblio辞書

デジタル大辞泉

索引トップ用語の索引ランキング凡例

ダイナミック‐プログラミング【dynamic programming】

読み方：だいなみっくぷろぐらみんぐ

⇒動的計画法

ディー‐ピー【DP】

読み方：でぃーぴー

《dynamic programming》動的計画法。予算、経営の長期計画の決定などに利用する数理計画法の一手法。

OR事典

索引トップ用語の索引ランキングカテゴリー

動的計画

読み方：どうてきけいかく
【英】：dynamic programming

概要

1957年, ベルマン (R.E. Bellman) によって提案された多変数最適化問題を解くための手法. 目的関数に再帰性(可分性)と単調性があり, 制約式が逐次的であるとき, 原問題をある部分問題群に埋め込んで, 各部分問題の最適値を定義し, 相隣る問題の最適値間の関係式(再帰式)を導く. これを逐次解いて, 最後に与問題の最適解を求める方法である. 解法の効率化のためには, 決定変数, 状態変数, 評価関数などの選択・設定に個々の創意工夫を要する.

詳説

　多変数最適化問題の目的関数が再帰性(可分性)と単調性をもち, 制約条件に逐次性があるとき, 再帰式を導いて, これを１変数ずつ解いて最後に与問題の最適解を求めようとする方法を, 動的計画(dynamic programming)と呼ぶ. 原理としては $\mbox{(i)}\,$ 最適性の原理 (principle of optimality), $\mbox{(ii)}\,$ 不変埋没原理(principle of invariant imbedding), $\mbox{(iii)}\,$ 因果律の原理(principle of causality), の三つに基づく[1]. 最適性の原理には $\mbox{(1)}\,$ オリジナル版, $\mbox{(2)}\,$ シンプル版, $\mbox{ (3)}\,$ " $\mbox{Life}\,$ "版, $\mbox{(4)}\,$ 構造解析版, $\mbox{(5)}\,$ 数学版, などがある[9]. 数学的にはマックスマックス定理に遡ることができる[2][4]. 応用面では, 逐次決定過程 [3][6]の基本原理として用いられ, マルコフ決定過程の政策改良法, 最短経路問題のダイクストラ法, 巡回セールスマン問題など種々の最適化問題の解法としてアルゴリズムに組み込まれている.

　一般に, 再帰型関数 $h : [0, \infty)^{N} \to \mathbf{R}^{1}\,$ は

$h(x_{1}, x_{2}, \ldots , x_{N}) = h_{1}(x_{1};h_{2}(x_{2};\ldots , h_{N-1}(x_{N-1};h_{N}(x_{N})) \ldots ))\,$

で表わされる. このとき, 部分関数 $h_{n} : [0, \infty)^{N-n+1} \to \mathbf{R}^{1}\,$ を

$h_{n}(x_{n}, \ldots , x_{N}) := h_{n}(x_{n};\ldots , h_{N-1}(x_{N-1};h_{N}(x_{N})) \ldots )\,$

で定義する. 構成要素の１変数関数 $h_{n}(x;\cdot), h_{N}(\cdot)\,$ がすべて単調な(狭義単調な)とき, 特に単調性(狭義単調性)をもつ再帰型関数という. 単調性をもつ再帰型関数 $f,\, g$ を目的式と制約式にする主問題

$\mbox{P}(c) \quad \begin{array}{lll} \mbox{max.} & f(x_{1}, x_{2}, \ldots , x_{N}) \\ \mbox{s. t.}& g(x_{1}, x_{2}, \ldots , x_{N}) \le c, & x_{1},x_{2},\ldots ,x_{N} \ge 0, \end{array}\,$

の解(最大値関数と最大点関数)は次のように求められる：

主問題 $\mbox{P}(c)\,$ を部分問題群 ${\mathbf P} = \{\mbox{P}_{n}(c)\}:\,$

$\mbox{P}_{n}(c) \quad \begin{array}{lll} \mbox{max.} & f_{n}(x_{n}, \ldots , x_{N}) \\ \mbox{s. t.}& g_{n}(x_{n}, \ldots , x_{N}) \le c, & x_{n}, \ldots ,x_{N} \ge 0, \end{array}\,$

に埋め込み, この最大値を $u_{n}(c)\,$ とする. このとき, 制約式の狭義単調性と両式の連続性を仮定すると, 再帰式

$u_{n}(c) =\max_{x \ge 0} \, f_{n}(\,x\,; u_{n+1}(g_{nx}^{-1}(c))) \quad 1 \le n \le N-1\,$

$u_{N}(c) =f_{N}(g_{N}^{-1}(c))\,$

が成り立つ. ただし, $g^{-1}_{nx}(\cdot)\,$ は $g_{n}(x;\cdot)\,$ の逆関数. この再帰式を後向きに解いて, 最後に主問題の最大値 $u_{1}(c)\,$ が得られる. これが動的計画法である. さらに, 主問題 $\mbox{P}(c)\,$ と逆問題

$\mbox{I}(c) \quad \begin{array}{lll} \mbox{min.} & g(x_{1}, x_{2}, \ldots , x_{N}) \\ \mbox{s. t.}& f(x_{1}, x_{2}, \ldots , x_{N}) \ge c, & x_{1},x_{2},\ldots ,x_{N} \ge 0, \end{array}\,$

の解(最小値関数と最小点関数)の間には互いに逆関数の関係にある(逆定理 [5]). これは線形計画における双対定理に類似して, 動的計画の双対定理と考えられる[11].

　また, 狭義単調性をもつ再帰型関数 $h\,$ が終端値 $k\,$ をもつときは

$h(x_{1}, \ldots , x_{N}, k) = h_{1}(x_{1};\ldots , h_{N-1}(x_{N-1};h_{N}(x_{N};k)) \ldots )\,$

で表わされる. これに対して反転関数(逐次パラメトリック逆関数) $h^{-1} : \mathbf{R}^{N+1} \to \mathbf{R}^{1}\,$ を

$h^{-1}(x_{N}, \ldots , x_{2}, x_{1}, c) :\;=\; h^{-1}_{N}(x_{N};\ldots , h^{-1}_{2}(x_{2};h^{-1}_{1}(x_{1};c)) \ldots )\,$

で定義する. このとき, 目的式 $f\,$ , 制約式 $g\,$ (ただし $g_{N}(x_{N};l) := g_{N}(x_{N}) + l )\,$ をもつ主問題の反転問題を

$\mbox{R}(c) \quad \begin{array}{lll} \mbox{min.} & f^{-1}(x_{N}, \ldots , x_{1}, u_{1}^{-1}(c)) \\ \mbox{s. t.}& g^{-1}(x_{N}, \ldots , x_{1}, c) = 0, & x_{N},\ldots ,x_{1} \ge 0, \end{array}\,$

で考えると, 反転問題の最小値は主問題の終端値となる (反転定理 [7]).

　さらに, 準線形化, 最大変換(共役変換)による双対理論を組み込んだ三面鏡理論 [8]が制御過程上で展開されている. 逆問題, 反転問題, 双対問題は基本的に動的計画法で解くことができるが, それぞれの問題の最適解は直接解くことなく, 対応する定理によって得られる[7].

　再帰性, 単調性がない場合の最適化としては, 非可分性との関連で結合性などの下で事前条件付き決定過程, 事後条件付き決定過程[10]がファジィ動的計画, 非加法型再帰的効用関数の経済学などで研究されている. これらの問題はマルコフ政策のクラスで再帰式が導かれる.

参考文献

[1] R. Bellman, Dynamic Programming, Princeton Univ. Press, 1957.

[2] G. H. Hardy, J. E. littlewood and G. Pólya, Inequalities, 2nd ed., Cambridge Univ. Press, 1952.

[3] 茨木俊秀,『組合せ最適化の理論』, 電子通信学会, 1979.

[4] 伊理正夫ほか, 座談会「最大問題最小問題をめぐって」,『数学セミナー』, 7月号 (1966), 40-48.

[5] S. Iwamoto, "Inverse Theorems in Dynamic Programming I, II, III," Journal of Mathematical Analysis and Applications, 58 (1977), 113-134, 249-279, 439-448.

[6] 岩本誠一,「逐次決定過程としての動的計画論I,II」,『オペレーションズ・リサーチ』, 22 (1977), 427-434, 496-501.

[7] 岩本誠一,『動的計画論』, 九州大学出版会(経済工学シリーズ), 1987.

[8] S. Iwamoto, "A three mirror problem on dynamic programming," in Proceedings of the Third Bellman Continuum Workshop, 363-382, 1989.

[9] 岩本誠一,「動的計画の最近の進歩」, 第２回ＲＡＭＰシンポジウム論文集, 129-140, 1990.

[10] S. Iwamoto, "Conditional decision processes with recursive reward function,"Journal of Mathematical Analysis and Applications, 230 (1999), 193-210.

[11] 近藤次郎,『最適化法』, コロナ社, 1984.

「OR事典」の他の用語

動的・確率・多目的計画：	再帰式分布問題列挙法動的計画単一評価系原始政策反転定理
確率と確率過程：	初到達時間到着過程割引き動的計画吸収的マルコフ連鎖在庫モデル多次元分布
組合せ最適化：	分枝限定法劣勾配法動的木動的計画多面体理論多項式時間アルゴリズム巡回セールスマン問題

Weblio日本語例文用例辞書

索引トップ用語の索引ランキング

「Dynamic programming」の例文・使い方・用例・文例

Boston Dynamicsのロボット「RHex」は、いろんな地形を走れるすごいやつです。

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。

>> 「Dynamic programming」を含む用語の索引
Dynamic programmingのページへのリンク


	(C)Shogakukan Inc. 株式会社小学館
	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

Dynamic programmingとは？わかりやすく解説

ダイナミック‐プログラミング【dynamic programming】

ディー‐ピー【DP】

動的計画

概要

詳説

「Dynamic programming」の例文・使い方・用例・文例

「Dynamic programming」の関連用語

Dynamic programmingとは？ わかりやすく解説

ダイナミック‐プログラミング【dynamic programming】

ディー‐ピー【DP】

動的計画

概要

詳説

「Dynamic programming」の例文・使い方・用例・文例

「Dynamic programming」の関連用語

Dynamic programmingとは？わかりやすく解説