近似アルゴリズム

一次式で表される制約条件のもとで、一次式の目的関数の最大値または最小値を求める数学的最適化手法。シンプレックス法が代表的な解法であり、生産計画、輸送計画、資源配分の最適化問題に広く用いられる。

最適化問題を部分問題に分割し、各部分問題の最適解を記憶して再利用することで全体の最適解を効率的に求める手法。ナップサック問題や最短経路問題などに適用され、メモ化再帰やボトムアップ方式で実装される。