共通するパターン

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

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



Amazon.co.jp アソシエイト (広告)
Audible の無料体験を始めよう
amazon music unlimited で音楽聞き放題
The Art of Computer Programming Volume 1 Fundamental Algorithms
プログラミングコンテストチャレンジブック [第2版]
世界標準MIT教科書 Python言語によるプログラミングイントロダクション
アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書