貪欲法
貪欲法は局所探索法と並んで近似アルゴリズムの最も基本的な考え方の一つである。
このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法である。動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考する事は無い。このため得られる解は最適解であるという保証は無いが部分問題の解法と単純なソートのみでプログラムを実装することが可能であり、多くの問題に対して多項式時間での近似アルゴリズムとなる。
問題を複数に分割する方法は特に組合せ最適化問題と相性が良い。問題によっては厳密解(最適解)を得られたりするものや最低限の精度保証(近似度)が算出可能なものもある。このため、現在でもしばしば同問題の研究に用いられている。