共通するパターン

講義のスケジューリングに対する貪欲アルゴリズムの正しさの証明は、テープをソートするアルゴリズムの正しさの証明と同じ構造を持っています。つまり、帰納法を使った交換の議論 (exchange argument) です:

• 貪欲な解と異なる最適な解の存在を仮定する。
• 二つの解の “最初の” 違いを見つける。
• 最適な選択と貪欲な選択を交換しても解が悪くならないことを示す (良くならなくても構わない)。

この議論と帰納法を組み合わせると最適な解が貪欲な解を含むことを示すことができ、貪欲な解の性質からその二つが等しいことが言えます。スケジュールの問題のように、貪欲な解を狭義に改善する最適解が存在しないことを示すのに追加のステップが必要になることもあります。