「再帰式 (動的計画法の)」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (他の1人の利用者による、間の1版が非表示) | |||
| 2行目: | 2行目: | ||
動的計画法において相隣る問題の最適値の間の最適子を含んだ関係式. これを逐次解いて, 最後に与問題の最適解を得る. 通常, 後ろ向きの再帰式をいうが, 前向きの再帰式も場合によっては成り立つ. 無限段問題では関数方程式になり, 最適方程式ともいわれる. 最短経路問題, 巡回セールスマン問題などの有限な問題では再帰式に基づくアルゴリズムが求められている. | 動的計画法において相隣る問題の最適値の間の最適子を含んだ関係式. これを逐次解いて, 最後に与問題の最適解を得る. 通常, 後ろ向きの再帰式をいうが, 前向きの再帰式も場合によっては成り立つ. 無限段問題では関数方程式になり, 最適方程式ともいわれる. 最短経路問題, 巡回セールスマン問題などの有限な問題では再帰式に基づくアルゴリズムが求められている. | ||
| + | |||
| + | [[Category:動的・確率・多目的計画|さいきしき]] | ||
2008年11月9日 (日) 17:47時点における最新版
【さいきしき (recursive formula)】
動的計画法において相隣る問題の最適値の間の最適子を含んだ関係式. これを逐次解いて, 最後に与問題の最適解を得る. 通常, 後ろ向きの再帰式をいうが, 前向きの再帰式も場合によっては成り立つ. 無限段問題では関数方程式になり, 最適方程式ともいわれる. 最短経路問題, 巡回セールスマン問題などの有限な問題では再帰式に基づくアルゴリズムが求められている.