不変埋没原理

提供: ORWiki
2007年7月20日 (金) 11:05時点におけるOrsjwiki (トーク | 投稿記録)による版 ("不変埋没原理" を保護しました。 [edit=sysop:move=sysop])
ナビゲーションに移動 検索に移動

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

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