共通するパターン

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

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

関連書籍 (Amazon アソシエイト)
Algorithms
世界標準MIT教科書 Python言語によるプログラミングイントロダクション 第2版:データサイエンスとアプリケーション
問題解決力を鍛える! アルゴリズムとデータ構造
アルゴリズム図鑑 絵で見てわかる26のアルゴリズム
広告