貪欲法
Greedy Algorithmとも。ある戦略に沿って評価値の高いものから処理していくアルゴリズム。
Wikipediaの解説
簡単に見えて、最適性を証明するのが困難な手法。
maspyさんの記事
によれば、
先進性を示す。任意の"時点"で最適な方法であることを、"時系列"順に示す。
最適解に仮定できる性質を課していく(2つ入れ替えても悪くならないのでこの形etc)と、貪欲になることを示す
などが一般的な証明方法らしい。