貪欲法について小学生にも分かる様に説明する

プログラム初心者「プログラミングの力を付けるには、アルゴリズムを学んだ方が良いと言われ、探索手法を学び始めたけど、サッパリだ。。貪欲法ってイカツイ名前が付いているけど、小学生にもわかる様に説明してほしい。」

今日は、「ざっくり理解するアルゴリズム」の「貪欲法」です。あくまでも、コンセプトを理解して貰う事を目的としているので、簡略化して説明します。

貪欲法を一言で言うと

貪欲法をざっくり言うと、次の一手を選ぶ際に、ゴールに最も近そうな所（お得な所）を選びます。

例えば、あなたは、東京から大阪に行きたいとします。(直線距離：510km)

次の経由地として以下の3つから選べるとしたら、あなたはどれを選びますか？

この様な場合、最も大阪への残距離が短い「静岡」を選ぶ人が多いと思います。

これを繰り返す事で、大阪への到達を目指すのが貪欲法です。とても簡単でしょ？

目的地が決まったら、中間ゴールを探し出し、ゴールに近そうなものを選び出すのを繰り返す。

人生でも、目的地に近い中間目標を見つけ、コツコツとクリアする人が多いと思いますが、その方法そのものが貪欲法です。

では、そんなあなたに質問です。

Q.貪欲法では最短コストで辿り着く？

折角ならば、人生も最短コストで辿り着きたいですよね。

では、ゴールに最も近そうな所を常に選んでいけば、最短でゴールまで辿り着けるでしょうか？

ちょっと考えてみてくださいね。答えは、

辿り付きません。

例えば、

1km+100km(最初の残距離:100km)

で辿るルートと、

90km+90km(最初の残距離：90km)

で辿るルートの2つがある場合、あくまでも2つ目の90km+90kmのルートを選択します。これは、最初の全体距離101kmと比べて180kmと長いですよね。

Q.貪欲法では最短手数で辿り着く？

辿り着きません。

例えば、2手で残距離が100km,0kmとなる場合と、3手で残距離が40km、30km、0kmとなった場合、後者を選びます。

なので、手数が最小となるわけではありません。

貪欲法の弱点

貪欲法は、あくまでもこれからのコストしか考えないので、今までのコストを考えていません。

なので、最短距離を求められる訳ではありません。

h(n)をゴールまでの推定距離だとすると、貪欲法は、f(n)が最小になるものを探していました。

f(n) = h(n)

ここに、今までのコストg(n)を足してあげると、より良い探索が出来る様になります。

つまり、

f(n) = g(n) + h(n)

とする事で、より強力なアルゴリズムとする事が出来ます。

この改良されたアルゴリズムはA*(A-Star)法と言われるものです。