最適性の原理

【さいてきせいのげんり (principle of optimality)】

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