最適性の原理

OR事典

最適性の原理

読み方：さいてきせいのげんり
【英】：principle of optimality

ベルマン (R.E. Bellman) よる動的計画法の基本原理. 「最適政策は, 最初の状態および最初の決定が何であっても, 残りの決定列は最初の決定から生じた状態に関して最適政策を構成するという性質をもつ」. 「最適政策は最適部分政策だけから成る」, 「マックスマックス定理」など, いくつかの同値表現がある. 所与の問題から, この原理によって再帰式を導き, それに基づいて最適政策を求めるのが動的計画である. 最適性の原理は, 再帰性(可分性)と単調性の下で成り立つ.

「OR事典」の他の用語

動的・確率・多目的計画：	対話型解法  最短最長ルート問題  最適停止  最適性の原理  期待値最適化  木の総容量  目標計画
組合せ最適化：	最大クリーク問題  最小木問題  最短路問題  最適性の原理  木  板取り問題  混合整数計画