ラスベガス・アルゴリズム

ラスベガス・アルゴリズムというのを知った。名前がかっこいい。これは乱択アルゴリズム(randomized algorithm)のカテゴリの一つで、モンテカルロ・アルゴリズムと対になっている。

モンテカルロ法とはランダムで生成した値で近似することで本来複雑な問題を単純化する手法。よくある例として、円の面積を求める際にランダムでデータ点を生成し原点から一定距離(半径)以内に入っているデータ点の比率を調べることで円の面積を求めるというのがある。
モンテカルロ法はあくまで「近似」しているに過ぎないので生成したランダム値によって結果は変化する(ランダム値の生成数が少ないほどブレは大きい)。
これに対してラスベガス法というのはある処理の効率化のために乱択アルゴリズムを用いるが結果は一意に定まるものを指す。例えばクイックソートではピボット選択を乱択化することで効率良くソートするという方法があるが、どのような乱数であっても処理効率に対する違いだけで最終的にソートされた配列は一意に定まる。従ってクイックソートの乱択化したものはラスベガス法に分類される。

このあたりの話は↓の本がで知った。説明がわかり易い良書なので詳細を知りたい方は是非読んでみると良い。