「両帰式 (動的計画法における)」の版間の差分
ナビゲーションに移動
検索に移動
細 ("両帰式 (動的計画法における)" を保護しました。 [edit=sysop:move=sysop]) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
動的計画法における単調性 (monotonicity) は目的関数の「非減少性」を意味している. これを「非減少性または非増加性のいずれか」と広義に解釈した両調性 (bitonicity) の下で, 所与の「最大化問題」を解くには, 部分最大問題群ばかりでなく部分最小問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を両帰式という. 利得関数が負値にもなる乗法型評価関数などの最適化は両帰式で解ける. | 動的計画法における単調性 (monotonicity) は目的関数の「非減少性」を意味している. これを「非減少性または非増加性のいずれか」と広義に解釈した両調性 (bitonicity) の下で, 所与の「最大化問題」を解くには, 部分最大問題群ばかりでなく部分最小問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を両帰式という. 利得関数が負値にもなる乗法型評価関数などの最適化は両帰式で解ける. | ||
| + | |||
| + | [[Category:動的・確率・多目的計画|りょうきしき]] | ||
2008年11月14日 (金) 09:40時点における最新版
【りょうきしき (bicursive formula) 】
動的計画法における単調性 (monotonicity) は目的関数の「非減少性」を意味している. これを「非減少性または非増加性のいずれか」と広義に解釈した両調性 (bitonicity) の下で, 所与の「最大化問題」を解くには, 部分最大問題群ばかりでなく部分最小問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を両帰式という. 利得関数が負値にもなる乗法型評価関数などの最適化は両帰式で解ける.