ラスベガス法のソースを表示

{{Expand English|Las Vegas algorithm|date=2024年5月}}
'''ラスベガス法'''（ラスベガスほう、{{lang-en-short|Las Vegas algorithm}}{{efn|この用語はL. Babaiによって1979年に（現在の慣習とはやや異なる意味で）導入された{{sfn|Motwani|Raghavan|1995|p=24}}。}}）は、間違った解を返さない[[乱択アルゴリズム]]を指す{{sfn|Atallah|Blanton|2010|loc={{google books quote|id=5uA1c8TuOC0C|page=SA12-PA22|12-22}}}}。すなわち、解を返すときは常に正しく、正しい解が求められない場合は失敗を通知する。換言すれば、[[ラスベガス]]法は答え（解）については賭けをせず、計算に使用するリソース量についてのみ賭けをする。さらに平均実行時間が入力長の多項式関数で押さられるようなラスベガス法は{{訳語疑問点範囲|効率的|date=2017-06-18}}<!-- 日本語の定訳を知らないのでとりあえず直訳 -->(efficient)であるという{{sfn|Motwani|Raghavan|1995|p={{google books quote|id=QKVY4mDivBEC|page=10|10}}}}。ラスベガス法の単純な例にランダム化された[[クイックソート]]がある{{sfn|Motwani|Raghavan|1995|pp=3&ndash;7}}。ピボット値をランダムに選択するクイックソートではソート結果は常に正しい。一般に無作為な情報に対してラスベガス法を使う際には、定義上、実行時間の上限を設けることが多い。

== 複雑性クラス ==
平均実行時間が多項式時間となるラスベガス法をもつ[[決定問題]]の[[複雑性クラス]]を '''[[ZPP]]''' と呼ぶ{{sfn|Motwani|Raghavan|1995|loc=Definition 1.9|p={{google books quote|id=QKVY4mDivBEC|page=22|22}}}}。

次のような性質がある{{sfn|Motwani|Raghavan|1995|loc=Exercise 1.9|p={{google books quote|id=QKVY4mDivBEC|page=22|22}}}}。
:<math>\mathbf{ZPP} = \mathbf{RP} \cap \text{co-}\mathbf{RP}.</math>
これは、ラスベガス法に属するアルゴリズムを構築する方法と密接に関係している。'''[[RP (計算複雑性理論)|RP]]'''クラスは、多項式時間の乱択アルゴリズムがある決定問題のクラスであり、解が「no」であるときは常に正しいが、解が「yes」であるときは間違っている可能性がある。そのようなアルゴリズムが、ある問題とその補問題（「yes」と「no」が逆転した問題）について存在するとき、その2つのアルゴリズムを同時にかつ繰り返し実行するとする。すると、最終的にどちらかで間違いのない解が得られる。これが多項式時間を期待できるラスベガス法のアルゴリズムを構築する標準的な方法である。ラスベガス法には最悪実行時間の上限が存在しないことに注意されたい。

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

== 注釈 ==
{{notelist}}

== 出典 ==
{{reflist|2}}

== 参考文献 == 
* {{cite book
|last1      = Atallah
|first1     = Mikhail J.
|last2      = Blanton
|first2     = M.
|year       = 2010
|title      = Algorithms and Theory of Computation Handbook: General Concepts and Techniques
|edition    = Second
|series     = Chapman & Hall/CRC Applied Algorithms and Data Structures Series
|url        = {{google books|5uA1c8TuOC0C|plainurl=yes}}
|publisher  = CRC Press
|isbn       = 978-1-58488-822-2
|mr         = 2766439
|zbl        = 1193.68001
|ref        = harv
}}
* {{cite book
|last1      = Motwani
|first1     = R.
|last2      = Raghavan
|first2     = P.
|year       = 1995
|title      = Randomized Algorithms
|url        = {{google books|QKVY4mDivBEC|plainurl=yes}}
|publisher  = Cambridge University Press
|isbn       = 0-521-47465-5
|mr         = 1344451
|zbl        = 0849.68039
|doi        = 10.1017/CBO9780511814075
|ref        = harv
}}

== 関連項目 ==
* [[ランダム]]
* [[モンテカルロ法]]

{{DEFAULTSORT:らすへかすほう}}
[[Category:ランダム・アルゴリズム]]
[[Category:数学に関する記事]]