動的計画法

サイエンス

動的計画法

どうてきけいかくほう

1957年,Bellmanによって提案された多変数最適化問題を解くための手法.

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

(「OR用語辞典」より)

*リスト::数学関連