両的計画
【英】:bynamic programming
概要
いわゆる動的計画法を2元連立的に考えた逐次最適化法. 単調性「非減少性」に代わって両調性「非減少性または非増加性のいずれか」の下では, 部分最大化問題群と部分最小化問題群の両群を考えて, 両群の相隣る問題間の関係を両帰式としてを導く. これを逐次解いて, 最後に与問題の最適解を求める方法である.負値乗法型, 負値乗加法型などの評価系が両的計画で解ける. 確率系ではマルコフ両決定過程ともいう.
詳説
動的計画法は単調性 monotonicity と再帰性 recursiveness (可分性 separability) の下で適用される. この単調性は目的関数の「非減少性」を意味しているが, これを両調性 bitonicity「非減少性または非増加性のいずれか」まで拡大解釈すると, より広い逐次決定過程が考えられる. これを両的計画と呼ぶ. 特に, 確率システム上ではマルコフ両決定過程[3]という. これは確率的動的計画法を単にマルコフ決定過程ということに準じている.
両的計画法によって最大化問題を解く場合, 与問題に対する部分最大化問題群ばかりでなく部分最小化問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を両帰式という. 負値乗法型評価系[1], 負値乗加法型評価系 [2] の最適化問題や最短最長ルート問題などは両帰式で解ける.
このとき, 確定系上の負値乗加法評価系の最大化または最小化は
で表わされる. ただし . このとき, 第
段の状態
から始まる部分問題
|
![]() |
![]() |
を満たす. ここに~ は
なる
である.
![]() |
![]() |
[1] R. Bellman, Dynamic Programming, Princeton Univ. Press, 1957.
[2] S. Iwamoto, "From Dynamic Programming to Bynamic programming," Journal of Mathematical Analysis and Applications, 177 (1993), 56-74.
[3] S. Iwamoto, "On Bidecision Processes," Journal of Mathematical Analysis and Applications, 187 (1994), 676-699.
[4] T. Fujita and K. Tsurusaki, "Stochastic Optimization of Multiplicative Functions with Negative Value," Journal of the Operations Research Society of Japan, 41 (1998), 351-373.
動的・確率・多目的計画: | 三面鏡理論 不変埋没原理 両帰式 両的計画 事前条件付き決定過程 事後条件付き決定過程 再帰式 |
- 両的計画のページへのリンク