ラスベガス法

ラスベガス法（英: Las Vegas algorithm）とは、間違った解を返さない乱択アルゴリズムを指す。すなわち、解を返すときは常に正しく、正しい解が求められない場合は失敗を通知する。換言すれば、ラスベガス法は答え（解）についは賭けをせず、計算に使用するリソース量についてのみ賭けをする。単純な例としてランダム化されたクイックソートがある。ピボット値をランダムに選択するクイックソートではソート結果は常に正しい。一般に無作為な情報に対してラスベガス法を使う際には、定義上、実行時間の上限を設けることが多い。

ラスベガス法で多項式時間で解けると期待される決定問題の複雑性クラスを ZPP と呼ぶ。

次のような性質がある。

これは、ラスベガス法に属するアルゴリズムを構築する方法と密接に関係している。RPクラスは、多項式時間の乱択アルゴリズムがある決定問題のクラスであり、解が「no」であるときは常に正しいが、解が「yes」であるときは間違っている可能性がある。そのようなアルゴリズムが、ある問題とその補問題（「yes」と「no」が逆転した問題）について存在するとき、その2つのアルゴリズムを同時にかつ繰り返し実行するとする。すると、最終的にどちらかで間違いのない解が得られる。これが多項式時間を期待できるラスベガス法のアルゴリズムを構築する標準的な方法である。ラスベガス法には最悪実行時間の上限が存在しないことに注意されたい。

ラスベガス法をモンテカルロ法から構築することもできる。モンテカルロ法は、リソースは制限されているが、解が100%正解とは限らないアルゴリズムである。

関連項目

• ランダム
• モンテカルロ法

外部リンク

• Example code of Miller-Rabin primality test using the Las Vegas method, C++

参考文献

• Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "Las Vegas algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 July 2006. (accessed TODAY) Available from: [1]

ラスベガス法の書籍検索結果