両帰式 (動的計画法における)
読み方：りょうきしき
【英】：bicursive formula
【英】：bicursive formula
【りょうきしき (bicursive formula) 】
動的計画法における単調性 (monotonicity) は目的関数の「非減少性」を意味している. これを「非減少性または非増加性のいずれか」と広義に解釈した両調性 (bitonicity) の下で, 所与の「最大化問題」を解くには, 部分最大問題群ばかりでなく部分最小問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を両帰式という. 利得関数が負値にもなる乗法型評価関数などの最適化は両帰式で解ける.
「OR事典」の他の用語
| 動的・確率・多目的計画： | 一般政策 三面鏡理論 不変埋没原理 両帰式 両的計画 事前条件付き決定過程 事後条件付き決定過程 |
- 両帰式のページへのリンク
