共通するパターン

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

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

広告