再帰式 (動的計画法の)

【さいきしき (recursive formula)】

動的計画法において相隣る問題の最適値の間の最適子を含んだ関係式. これを逐次解いて, 最後に与問題の最適解を得る. 通常, 後ろ向きの再帰式をいうが, 前向きの再帰式も場合によっては成り立つ. 無限段問題では関数方程式になり, 最適方程式ともいわれる. 最短経路問題, 巡回セールスマン問題などの有限な問題では再帰式に基づくアルゴリズムが求められている.