2009/11/22

欲張りな理論

どーも、僕です。

日々何気なく行っていることが、実はとてつもなく難しいことを行っていると、どれだけの人が気付いているでしょうか?何気ない行動を1ステップづつ説明しようとすると、実は結構難しいのです。今日の話は欲張りな理論、欲張りアルゴリズムについてです。

定義をgoogle先生などに聞くと、「反復アルゴリズムにおいて、各ステップごとに最大化(最小化)を試みるもの」と帰ってきます。なんだかさっぱりよく分かりませんね。なので、身近なことを例にとってみましょう。お買い物をした際のおつり、これなんかはベストな例ではないでしょうか。お釣りをもらうとき、どんなことを店員さんに期待しますか?そのお釣りを他に利用したいという目的がある場合は除き、お財布がじゃらじゃらにならないように、お釣りになる小銭の数をできるだけ小さくして欲しいと思いますよね?もし67円のおつりに67枚の1円玉を渡されたら、憤りを感じ店員をぶっ飛ばしてやりたくなることでしょう。このできるだけ少ない小銭にするという行為こそ、欲張りアルゴリズムが必要なのです!

この欲張りアルゴリズムでは、以下の3ステップからなります。

1:選択(そのステップで最大化を目指すもの)-この例ではどのコインを選ぶかです。
2:実現可能かの判断-1の判断が果たして可能なのか?を確認します。例では今まで選択してきた合計がお釣りの金額を超えていないか?になります。
3:答えの確認-選択してきたコインの合計が目的のお釣りと一致しているかを確認します。

上記の3ステップを答えに到達するまで1→2→3→1と繰り返します。

僕達はお釣りを渡すとき、こんなに面倒なことをせずにパッと計算できてしまうのですが、コンピュータなどに計算させようと思うとこの面倒なステップが不可欠となります。

文字だけだと分かりづらいので、図にしてみましょう!ここでは67円のお釣りをお客さんに渡すことを想定しましょう。

常にその場その場の状況で最大化をめざすので、まずは500円玉を選択します(500円玉がないことは自明じゃん!っていうのは無しです。あくまでも上記の3ステップ通りに進めます)。しかしステップ2において500>67となるので、500円玉は却下となります。ステップ1へ戻ります。

500玉が却下されたので、次に大きいコイン100円を選択します。しかしステップ2にて100>67となるので100円玉も却下です。

100円玉が却下されたので、次は50円玉です。50円玉を選択し、目標額67円と比較します。50≦67でオッケーです。そしてステップ3にて50≠67なのでまたステップ1へもどります。

もう一つ50円玉を選びます。合計が100>67となり、この選択は却下されます。ので次の選択肢は10円玉です。

10円玉を選んで、比較60≦67でステップ2はオッケー。60≠67でまたステップ1へもどります。

さらに10円玉を追加です。70>67となるので、この選択は却下です。次の選択は5円玉。ステップ1へ戻ります。

5円玉を選択して比較です。65≦67なのでオッケー。65≠67なので、ステップ1へ戻ります。

さらに5円玉を追加です。70>67となりこの選択は却下です。ステップ1へ戻ります。

次の選択は1円玉です。66≦67でオッケー。66≠67なのでステップ1へ戻ります。

更に1円玉の追加です。67≦67でステップ2はオッケー。ステップ3にて67=67となり、このループは終わり回答となります。

お釣り67円の最小枚数は50円+10円+5円+1円+1円の5枚となります。

このように、何気ないお釣りの計算を論理立てて説明しようと思うと、このような欲張りアルゴリズムが活躍します。
ただしこの欲張りアルゴリズムは万能ではなく、例えば12円玉があると仮定して、16円のお釣りをこの理論を使って最小枚数にしようと試みると、最適解をだせず、破綻します。この理論での解は12円玉+1円+1円+1円+1円の5枚となりますが、最適解は10円+5円+1円の三枚になります。万能ではないのですね!日本国内のお釣りでは破綻しませんが、他のことに利用する時は注意が必要ですね。

近頃のレジは勝手にお釣りを出すものを多く見かけますが、きっとこの理論が中に入っているに違いない!

0 件のコメント:

 
検索エンジン