わかりやすく 貪欲法 とは

今の最善を取る

おつりを870ウォン渡すとしましょう。貪欲のやり方は簡単です。今出せるいちばん大きいコインから取るのです。
500ウォンを一枚、100ウォンを三枚、50ウォンを一枚、10ウォンを二枚。
毎回いちばん大きいものを取っただけなのに、すぐに終わりました。

大きいコインから押して取ります。（870ウォン → 500 · 100 · 100 · 100 · 50 · 10 · 10）

これが貪欲アルゴリズムです。この先どうなるかを遠くまで考えず、ただ今この瞬間にいちばんよいものを選ぶだけです。
計算が軽いので、決めるのも速いのです。

全体は見ない

貪欲の本当の特徴は、全体の地図を広げて見ないことです。
分かれ道ごとに、今よさそうに見えるほうへ一歩踏み出すだけです。遠くを見通さないので、迷いが少なく速く進めます。
そのかわり、一度選んだものを振り返ることはありません。

分かれ道ごとに大きいほうの数を押して、一歩ずつ進みます。全体の地図は見えず、目の前の二つからしか選べません。

全体を見ないことは、長所でもあり弱点でもあります。速いのは長所です。
でも遠くが見えないので、今よさそうに見えた道が、あとで行き止まりになるかもしれません。
それでも問題によっては、この速いやり方が不思議なほどぴったり合います。

うまくいくとき

一つの会議室に、会議をできるだけ多く入れたいとしましょう。時間が重なってはいけません。
貪欲のこつは、いちばん早く終わる会議から入れることです。部屋が早く空くほど、あとにたくさん入るからです。
この欲張りは、不思議なことに本当の最善の答えを出します。

いちばん早く終わる会議から押して入れます。重なる会議は自動で外れ、貪欲が最大の4つを埋めます。

なぜこれが正解なのでしょうか。いちばん早く終わる会議を選ぶと、部屋がいちばん早く空きます。
空き時間がいちばん多く残るので、そこにほかの会議をいちばん多く入れられます。だから一歩ずつ欲張っても、結局は全体が最善になるのです。
こういう問題では、貪欲が答えです。

外れる反例

今度はコインが変わっています。1ウォン、3ウォン、4ウォンしかなく、6ウォンのおつりを渡さなければなりません。
貪欲に大きいものから出すと、4ウォン一枚に1ウォン二枚で、コインは三枚です。でも3ウォン二枚なら、二枚で済みます。
目の前の最善が、全体の最善を逃したのです。

二つの方法を押して比べます。貪欲（4·1·1 → コイン3枚）と、もっとよい道（3·3 → コイン2枚）。貪欲がわなにはまりました。

貪欲が外れたのは、4ウォンをさっと取った瞬間、残りの2ウォンを1ウォン二枚でしか埋められなくなったからです。
今の大きな一歩が、あとを台なしにしたのです。だからふつうのコインなら当たり、このようにずれたコインでは外れます。
貪欲が通用するかどうかは、問題ごとに確かめなければなりません。

まとめ

貪欲アルゴリズムを一行で言うと、「その時その時で今いちばんよさそうなものを選ぶ」です。全体を見ないので、速くて簡単です。
おつりや会議室のように、問題によってはこれがぴったりの正解です。でも変なコインやこんがらがった道では、目の前の最善がわなになります。
だから貪欲は速くてよく当たりますが、本当に正しいかどうかは問題ごとに確かめる必要があります。

要点の四つを順に押してまとめます。今の最善 → 全体は見ない → よく当たる → ときどき外れる。

前に見た動的計画法が、小さな答えを残らず集める慎重なやり方だとすれば、貪欲はその反対側にある、いちばん単純な欲張りです。今よいものを選んで前へ進みます。
速くて軽いので魅力的ですが、その単純さのせいで、ときどきわなにはまります。
いつ通用して、いつ通用しないのか、その感覚がつかめたら、次のレッスンではもう一つの工夫を見ます。いっそサイコロを振って選ぶ方法です。