貪欲法の証明パターン

ある順序で選択する貪欲法

順序の遅いものを早いもので置き換えても最大化したいスコアが減少しないことを示す

先進性を示す。任意の"時点"で最適な方法であることを、"時系列"順に示す。

最適解に仮定できる性質を課していく（2つ入れ替えても悪くならないのでこの形etc）と、貪欲になることを示す

･各操作において最適たりうる選択(その選択を含む最適解が存在するという意味)を行う

･各操作の後にはより規模の小さい問題に帰着でき、再帰的に解が求まる

･証明は基本的に背理法で、最適解が全て「貪欲による選択」を含まないと仮定して矛盾を示す

ex.)区間スケジューリング

こうすると、貪欲の証明でよく目にする「損をしない」というフレーズが出てこない。

まず下界を示す

下界に一致することを示す

よって最適解である