わかりやすく 乱択アルゴリズム とは

サイコロで選ぶ

ある解き方は、次に何をするかをサイコロを振って決めます。考えて選ぶのではなく、ただ運に任せるのです。
ボタンを押すたびに、サイコロが一回転がります。
どの目が出るかは、前もってわかりません。

押すとサイコロが転がります。次の目は前もってわかりません。

なぜわざわざ運に任せるのでしょうか。いつも同じやり方で選んでいると、だれかがその癖をねらって、わざと難しい入力を作れてしまいます。
ランダムに選べば、そうしたねらいをかわせます。
本当の使い道は、次の段階で見えてきます。

ランダムな基準を使う

速い並べ替えの中には、基準を一つ決めて、それより小さいものは左、大きいものは右に分けるやり方があります。
ところが、いつも最後の値を基準にすると、もう並んでいる入力では分け方が片方にばかり偏り、とても遅くなります。

いつも最後が基準 vs ランダムな基準で、分ける回数を比べます。（片方に偏る = 遅い）

基準をランダムに選べば、どんな入力が来ても、片方にばかり偏ることはほとんどなくなります。悪い入力をねらったわなも通用しません。
だから平均すると分け方がまんべんなくなり、並べ替えが速くなります。

たくさん投げて見積もる

ランダムは見積もりにも使えます。正方形の中に、円を四つに分けた一切れ、つまり四分円を描き、その中に点をどんどん打ちます。
四分円の中に入った点が全体のどれくらいかを見れば、四分円が占める面積を見積もれます。
点を一つずつ打ってみましょう。

点を打つほど、割合が真の値に近づきます。（円の中の点 / 全部の点）

点が少ないうちは、見積もりがばらばらです。でも点をたくさん打つほど、割合は真の値にぴたりと寄っていきます。
一、二回の運は信用できなくても、数えきれないほど投げた平均は信用できるからです。
これが、たくさん投げて答えを見積もる方法です。

確かさと速さを交換する

ランダムな解き方はただではありません。速くて簡単なかわりに、毎回同じ答えになるとは約束できず、運が悪いとときどき遅くなることもあります。
何を得て何を手放すのか、両方を押して比べてみましょう。

得るものと手放すものを押して比べます。（速さ·簡単さ vs 毎回同じ答えとは限らない）

だからランダムはいつもよいわけではなく、ふさわしい場所があります。
速くて簡単なことが、少しの不確かさより価値があるときに使います。確かさを少し手放して、速さと単純さを買うのです。

ひと目でまとめる

ランダムな解き方をひと目でまとめるとこうなります。サイコロで選び、ランダムな基準でわなを避け、たくさん投げて答えを見積もり、確かさと速さを交換する。
要点を順に押して、自分でまとめましょう。

要点の四つを順に押してまとめます。（サイコロ · ランダムな基準 · たくさん投げて見積もる · 交換）

運に任せるというと頼りなく聞こえますが、うまく使えばランダムは速くて心強い道具です。
データが途方もなく多いところほど、たくさん投げて見積もるこの考え方が大きく生きてきます。
次のレッスンでは、点と線でつながった世界、グラフへ進みます。