貪欲法には「小さい順に選ぶのが最善」みたいなのがよくある。
しかし、それが最善である根拠は特になくて、「自明」であったり「なんとなく」であったりする。
僕もこれまで「なんとなく正しそうだから」という理由で貪欲法を使うことがあった。しかしそれでは、安心して問題を解くことはできない。
今回は、あらゆる貪欲法の証明に当てはまるパターンを見つけた気がするので書き残す。
結論からいうと、「昇順または降順に選ぶのが最善」を証明したい場合は「スワップしたときに何の損もしない」ことを示せばいい。
具体例
エレベーターには重量制限がある。エレベーターにできるだけ沢山の人を乗せたい。どのように人を選んでいくのが最適か。
これは感覚的には自明で「体重の少ない人から選んでいくのが最適」である。
しかし、それを証明するとなると難しい。
そこで、先ほど紹介したパターンを使う。
ここではわかりやすさのために、人の体重と合計を数直線上で表す。
このような図を使うことで、選ぶ順序の情報も含めることができる。
上記の図の場合、選ぶ順序は60kg→100kg→80kg→120kg→50kg→70kgである。
ここで、以下の条件を満たす2人を選ぶ。
2人をi, j、何番目に選ばれるかをC_i, C_j、体重をM_i, M_jとおいたとき、C_i < C_jかつM_i > M_jを満たす。
上の例では100kgの人と50kgの人がこの条件を満たすため、この2人を選ぶ。
そして、この2人の順序を入れ替える。
ここで、間に挟まれている80kgの人と120kgの人の位置の変化を見ると、前に移動していることがわかる。下の図のように、必ず左下向きの矢印になる。右下向きの矢印には決してならない。
つまり、先ほどの太字の条件を満たすような2人を選んだとき、その2人の順序を入れ替えても決して損にはならない。入れ替えるとエレベーターに乗せられる人の数が減ってしまった、なんてことは絶対にない。
よって、体重の少ない人から選んでいくのが最適であることが証明できた。
なぜスワップ操作で損をしないことを示すだけで貪欲法を証明できたことになるか
スワップ操作を繰り返す。
すると、最終的な順序は体重の昇順になる。
つまり、たった2つの要素だけに注目し、その2つをスワップしても何も損がないことさえ証明できれば、それで貪欲法を証明したことになる。
まとめ
貪欲法を証明するときは、「2つの要素をスワップしても何も損をしない」ことを示すだけでいい。それ以上の証明は必要ない。
