不変埋没原理

【ふへんまいぼつげんり (principle of invariant imbedding)】

動的計画法の基本原理の1つ. ある問題を解こうとするとき, この問題を含む部分問題からなる群(族)を考える. これを「埋め込み」という. ただし, それぞれの問題の「構造」は不変である. このとき, 問題の大きさは小さいものから大きいものまであり, 「1番大きい」問題が与問題である. 相隣る問題間の関係式を導き, これを解くことによって, 与問題の「解」を求める. 埋め込み方に工夫を要する.