greedy証明典型テク

まえがき

このように、直感に頼った未証明のGreedyは危険です。

概要

状態に対してコストが定まるような状況を考える.

コストが最小になるための状態の必要十分条件を とする.

このとき, 以下のいずれかを仮定できるなら, 条件 を の必要条件に代るものとして考えることができる.

• 任意の状態から, (必要なら状態を変化させて) コストを増加させずに条件 を満たすようにできる
• 任意の を満たす状態から, (必要なら状態を変化させて) コストを変化させずに条件 を満たすようにできる

TODO

マトロイド系貪欲証明

コスト比較系貪欲証明