「動的計画」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
("動的計画" を保護しました。 [edit=sysop:move=sysop])
(相違点なし)

2007年7月20日 (金) 12:24時点における版

【どうてきけいかく (dynamic programming)】

1957年, ベルマン (R.E. Bellman) によって提案された多変数最適化問題を解くための手法. 目的関数に再帰性(可分性)と単調性があり, 制約式が逐次的であるとき, 原問題をある部分問題群に埋め込んで, 各部分問題の最適値を定義し, 相隣る問題の最適値間の関係式(再帰式)を導く. これを逐次解いて, 最後に与問題の最適解を求める方法である. 解法の効率化のためには, 決定変数, 状態変数, 評価関数などの選択・設定に個々の創意工夫を要する.