アリ本の解説、私のように頭が弱い人には足りないことがあります。そこで、私がうんうん唸りつつ考察した、小学生でもわかりそうな解説を記そうと思います。
…少なくとも東大未満でも学生なら理解できるレベルではあります。たぶん
今回は2-2の「区間スケジューリング問題」の証明を解説します。
区間スケジューリング問題の証明
コラムに証明あるのですが、これが頭が良くないとサッパリわからないです。私は分かりませんでした。
まあ、書いてあることは簡潔ですが要点を押さえてあって流石ってかんじです。
前置きはさておき、証明してみたいと思います。
証明する命題
証明する命題は「『選べる仕事の中で、終了時間が早いものを選ぶことを繰り返す。』ことが最適なアルゴリズムである」です。これが正しいことを示します。
証明本文
アリ本のコラムにはこうあります。
他の任意の選び方に対し、このアルゴリズムの選び方は、開始時間が早いものから同じ個数のところで、終了時間が遅くない。
よくわかりません。が、要点は抑えてあります。これに従い証明したいと思います。
帰納法なので、「n個目の仕事を選ぶとき、もっとも終了時間が早いものを選ぶ選び方が、最適である」これを示したいと思います。
i) n=1
まず、一つ目の仕事を選ぶ場合です。これは仮定から、もっとも終了時間が早いです。これがもっとも多く選べていることは明らかです。
なぜなら、他の選び方をしたら1つより多く選べるとします。すると、「もっとも終了時間が早い仕事」の前に終了している仕事が存在することになります。これは仮定に反しています。よって示されました。
↑図にすると明らかですね。
ii) n=kで成り立つと仮定し、n=k+1のとき
n=kまでで最多となる選び方までは決まっています。その状況からまた1つ選ぶわけです。
実はn=1のときとおなじ議論で証明できます。n=kまで決まっています。ここからさらに1つ選ぶには、k個目の終了時間より開始時間がおそくなければなりません。そのような要素のみとり出し、そこから1つ選ぶのですから、n=1となんら変わりません。
↓
証明終了
i)、ii)より帰納法をもちいて証明されました。
終わりに
…うーん、書いてて思いましたが、わかりづらかったですかね…わたしはこれで納得できましたが、いかがでしょうか
