乱択アルゴリズムの強さ

乱択アルゴリズムとは

乱択アルゴリズムは、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的としている。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を「期待実行時間; expected runtime」と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。

乱択アルゴリズムとは乱数を利用したアルゴリズムで、一般的に決定的アルゴリズムよりも平均的にみて高速であることが知られています。

ただ、このままではなんとも理解しづらいのでwikipediaにも載っている例で解説していきましょう。

配列検索問題

目の前に100個のダンボールがあり、50個にりんご、50個にみかんが入っているとします。みかんとりんごのダンボールは外見からは全く見分けがつかず、実際にあけてみるまで中身を知ることはできません。

ダンボールは一列に並んでいるのですが(実際には積み重ねるのが普通なので真横にズラッと並んでいるのは不自然だが、ここではそれは考えない)、手っ取り早くりんごの箱を見つけるにはどうすれば良いかという問題です。

ここで大事なのは “りんごとみかんの箱が同数ある” とわかっていることです。

先頭から順番にあける

最もシンプルかつわかりやすいアルゴリズムはこれでしょう。

「前から順番にあけていく」と考える人が多いのではないでしょうか?

このアルゴリズムは一見すると現実的に見えますが、りんごの箱が後ろに偏っている場合に時間がかかってしまうことがわかります。

つまり、箱の並び方によっては非効率な方法となってしまうわけです。

最良手数1
平均手数1.98
最悪手数50

後ろから順番にあける

前からあけるあけ方が箱の並び方によって効率が悪いと知ると、とりあえず後ろからあけてみたくなりますがこれは結局やっていることが同じです。

何故なら前からあけて都合が悪い箱の並び方は逆向きにすれば後ろからあけて都合が悪くなるためです。

つまり、これは先頭からあけているのと全く変わらないということです。

同じように、どんなに頭を働かせて考えてもアルゴリズムを決めた時点で箱をあける順番が決まっているアルゴリズムに対して効率を悪くするような “悪意ある箱の並び” が存在するということです。

アルゴリズムを決めたときに箱のあけ方が決まってしまうと悪意のある箱の並びが存在する… ってことはどんなアルゴリズムを考えてもダメなんじゃ?

ところがどっこい。そこで登場するのが乱択アルゴリズムなんよね。

適当にあける

意外に思えますが、どんな箱の並びに対しても常により良い手数を与えるのがこのいかにも愚直な “適当にあける” なのです。

これは手数を考えると “先頭から順番にあける” と違いはないのですが、どんな箱の並びがあっても極めて高速にりんごの箱を見つけることができます。

最良手数1
平均手数1.98
最悪手数50

これは実際に意地悪な人がいると考えればわかりやすいと思います。

意地悪な人はなるべくあなたが箱をあける回数を増やそうとします。

ところが、よく考えれば計算上は平均手数が1.98なのですから5回くらいあければりんごの箱は見つかる確率は十分高いのです。

なので、なるべくりんごの箱を見つけられないようにあなたが考えそうなあけ方で最も手数のかかる並べ方をしてきているのです。

こちらの戦略を考えた上での箱の並びに対する最良の戦略は “適当” ということになるわけです。

この戦略はとても有効で、例えば最初にあけた五つの中にりんごの箱が少なくとも一つある確率は、

となり、実に97%以上もあることがわかります。

中学数学で習った余事象の利用ですね。五つあければ97%以上の確率でりんごの箱が見つかるということです。

ロッカー問題

では、以上のことを考えて実際の問題に移りましょう。

  • 三つの部屋があり、部屋間での一切の情報のやり取りはできない
  • A部屋に十人のプレイヤーがいる
    • 十人はそれぞれ1~10の数字が書かれたカードを持っている
    • カードの数字は被りがない
    • カードを交換してもいいし、会話をしてもいい
  • A部屋から一人がB部屋に移動する
    • B部屋には10個のロッカーがある
    • ロッカーの中にはカードが入っている
    • ロッカーの中のカードの番号をあけずに知ることはできない
    • 一つずつあけていき、自分のカードの数字と同じカードを探す
    • 見つけたらC部屋に移動する
  • C部屋に移動したら新たにA部屋からB部屋に一人移動する
    • これを繰り返す
ロッカー問題

C部屋からA部屋へは連絡ができないので、どのロッカーにどの数字のカードが入っていたかを伝えることはできません。

さて、ロッカーをあけた回数の合計をNとしたとき以下の問題を考えます。

全ての並びに対する最大のNの最小

最大の最小ときくと矛盾していそうな気がしますが、実はしていません。

例えば十人が相談して「適当にあけよう」と決めたとします。

このとき、ロッカー内のカードの並びの運が良ければ全員一発で当ててN=10となりますが、運が悪いと全員十回ずつかかってN=100となります。

このときの最良の方法はしまけん(@ShimaKen_US)さんが考えた方法で「全員が同じあけ方をする」というものになります。

全員が同じ開け方を徹底(例、左から順に)すれば最大値55回で見つかると思う。

発展ロッカー問題

とまあここまでわかったら本題に入ります。

先程は一人あたりのロッカーをあける回数に制限がありませんでしたが、今回は一人五回しかロッカーをあけることが許されないとします。

このとき、全員が自分のカードを見つけられる確率はどのくらいまで高くできるでしょうか?

全員が同じあけ方をする(0%)

回数に制限がない場合に最良だった方法は、このケースでは全く役に立ちません。

何故なら、このあけ方ではカードを見つけるのに十回かかるプレイヤーが絶対に発生するためです。

つまり、成功率は0%です。先程の考えではダメなわけですね。

全員がランダムにあける(0.1%)

記事のタイトルが乱択アルゴリズムだから「全員が適当にあければ良いんじゃないか!?」って考えた方は方向性はいいですがそのやり方ではダメです。

試行回数が5で総数が10ということはランダムにあけて当たる確率は1/2です。

10人全員がカードを見つけようとすると、その作戦が成功する確率は、

となり、約0.1%になります。これでも全然ダメなわけですね。

前半と後半に分ける(0.4%)

ここで、ちょっとひねった作戦を考えます。

番号が1-5のプレイヤーは左から1-5番目のロッカーを調べ、6-10のプレイヤーは6-10番目のロッカーを調べます。

このとき、1のカードが最初の5つのロッカーに入っている確率は5/10、2のカードが4つのロッカーに入っている確率は4/9となるので帰納的に考えると、

となり、約0.4%になります。さっきの作戦よりは4倍くらい成功確率が高いですがやっぱりこれでもダメですね。

まとめ

さて、いくつかの作戦を提示しましたがどの作戦も確率1%以下で全く現実的な方法ではありませんでした。

やはり全員がカードを見つけるこれ以上の作戦はないのでしょうか?

いいえ、実はあるのです。

ですが、解答をすぐに載せてしまうのは楽しみを奪ってしまうようで気が引けました。

よって、これは数学好きなみなさんへの宿題ということにします。記事の中で答えを出さないんかい!!というツッコミはごもっともですが、やっぱりクイズは考えてこそだと思うので。

今回は別に当てても何も景品はありませんが、皆さんの休日の余暇を楽しませることができれば幸いです。

記事は以上。