ラスベガス法

ラスベガス法（ラスベガスほう、英: Las Vegas algorithm[注釈 1]）は、間違った解を返さない乱択アルゴリズムを指す[2]。すなわち、解を返すときは常に正しく、正しい解が求められない場合は失敗を通知する。換言すれば、ラスベガス法は答え（解）については賭けをせず、計算に使用するリソース量についてのみ賭けをする。さらに平均実行時間が入力長の多項式関数で押さられるようなラスベガス法は効率的[訳語疑問点](efficient)であるという[3]。ラスベガス法の単純な例にランダム化されたクイックソートがある[4]。ピボット値をランダムに選択するクイックソートではソート結果は常に正しい。一般に無作為な情報に対してラスベガス法を使う際には、定義上、実行時間の上限を設けることが多い。

複雑性クラス

平均実行時間が多項式時間となるラスベガス法をもつ決定問題の複雑性クラスを ZPP と呼ぶ[5]。

次のような性質がある[6]。

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

モンテカルロ法との関係

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

注釈

  1. ^ この用語はL. Babaiによって1979年に（現在の慣習とはやや異なる意味で）導入された[1]。

出典

  1. ^ Motwani & Raghavan 1995, p. 24.
  2. ^ Atallah & Blanton 2010, 12-22.
  3. ^ Motwani & Raghavan 1995, p. 10.
  4. ^ Motwani & Raghavan 1995, pp. 3–7.
  5. ^ Motwani & Raghavan 1995, p. 22, Definition 1.9.
  6. ^ Motwani & Raghavan 1995, p. 22, Exercise 1.9.

参考文献

  • Atallah, Mikhail J.; Blanton, M. (2010). Algorithms and Theory of Computation Handbook: General Concepts and Techniques. Chapman & Hall/CRC Applied Algorithms and Data Structures Series (Second ed.). CRC Press. ISBN 978-1-58488-822-2. MR2766439. Zbl 1193.68001. https://books.google.co.jp/books?id=5uA1c8TuOC0C 
  • Motwani, R.; Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press. doi:10.1017/CBO9780511814075. ISBN 0-521-47465-5. MR1344451. Zbl 0849.68039. https://books.google.co.jp/books?id=QKVY4mDivBEC 

関連項目