乱択アルゴリズムのソースを表示

{{読み仮名|'''乱択アルゴリズム'''|らんたくアルゴリズム}}、'''ランダム・アルゴリズム'''（{{lang-en-short|randomized algorithm}}）または{{読み仮名|'''確率的アルゴリズム'''|かくりつてきアルゴリズム|{{lang-en-short|probabilistic algorithm}}}}は、その論理の一部に無作為性を導入した[[アルゴリズム]]である。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的とすることがある。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その[[期待値]]を'''期待実行時間'''<ref>{{lang-en-short|expected runtime}}</ref>と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。

== 乱択アルゴリズムが使われる背景 ==
<var>n</var> 個の要素からなる[[配列]]から「a」という要素を探す問題を考える。この配列の各要素は半分が「a」で残りが「b」である。単純な手法は、[[配列]]の各要素を順次見ていく方法だが、配列の先頭の方に「b」がかたまっている場合に長時間かかってしまう（n/2回の操作）。逆の順番で見て行っても、ひとつおきに見ていったとしても同じような問題が発生する。実際、要素を調べる順序が固定されている全ての[[戦略]]（決定性アルゴリズム）では、あらゆる組合せの入力に対して常に高速なアルゴリズムであるとは保証できない。一方、配列要素を「無作為な」順序で調べる場合、入力がどうであっても高い確率で「a」を素早く見つけ出すことができる。<!--

乱択アルゴリズムは、入力に故意に間違いが含まれているような場合に特に有用である。そのため、[[暗号理論]]で[[ランダム|ランダム性]]がよく使われる。暗号では、敵が予測できる擬似乱数は使えない（そのような擬似乱数ではアルゴリズムが実質的には決定性を帯びる）。従って、真の乱数を使うか、暗号理論上安全とされる擬似乱数を使う必要がある。また、[[量子コンピュータ]]では本質的にランダム性が備わっている。

--><!--

↑えーと……ストリーム暗号とかで普通に擬似乱数使いますよ？　なにか猛烈な勘違いが入ってませんか？

-->

上の例では、乱択アルゴリズムは常に正しい答えを返す。実行時間が長くなる可能性も確率は低いが存在する。しかし、エラーを返す可能性を認めてでも、常に素早く答えを得たいということもある。前者のような乱択アルゴリズムを[[ラスベガス法]]と呼び、後者のような乱択アルゴリズムを[[モンテカルロ法]]と呼ぶ。ラスベガス法で所定の時間内に完了しない場合に間違った答えを返すようにすれば、モンテカルロ法に変換される。

また、確率解析学はありうべき全ての入力の集合に何らかの前提を設ける。この前提が効率的なアルゴリズムの設計に使われる。あるアルゴリズムへの入力の性質が不明な場合、確率解析的手法は使えない。乱択アルゴリズムでは、プログラム内の擬似乱数生成機能が使われることが多い。あるアルゴリズムが乱択であると言えるのは、その出力が入力だけでなく擬似乱数にも依存する場合である。

== 複雑性 ==
[[計算複雑性理論]]では、乱択アルゴリズムは[[確率的チューリングマシン|確率的]][[チューリングマシン]]としてモデル化される。ラスベガス法とモンテカルロ法を含むいくつかの「[[複雑性クラス]]」が研究されている。

; [[RP (計算複雑性理論)|'''RP''']]
:最も基本的な確率的複雑性クラス。[[決定問題]]''L''がRPに属するとは、ある(最悪計算量の意味での)[[多項式時間]]乱択アルゴリズム''A''が存在して、''A(x)''が「はい」を出力した場合に<math>x\in{}L</math>である確率は1/2以上で、「いいえ」を出力した場合に<math>x\notin{}L</math>である確率は1であるときに言う。(なお上述の「1/2」を0と1の間にある任意の定数に置き換えても定義は変わらない)。
; '''Co-RP'''
:RPの補問題のクラス。すなわち、''L''<sup>c</sup>がRPに属するとき、決定問題''L''はCo-RPに属するという。
; [[BPP (計算複雑性理論)|'''BPP''']]
:決定問題''L''がBPPに属するとは、ある(最悪計算量の意味での)多項式時間乱択アルゴリズム''A''が存在して、''A(x)''が「はい」を出力した場合に<math>x\in{}L</math>である確率も、「いいえ」を出力した場合に<math>x\notin{}L</math>である確率も2/3以上であるときに言う。(なお上述の「2/3」を1/2と1の間にある任意の定数に置き換えても定義は変わらない)。
; '''[[ZPP]]'''
:決定問題''L''がZPPに属するとは、(最悪時間は多項式とは限らないが)平均は多項式時間のある乱択アルゴリズム''A''が存在し、''A(x)''が「はい」を出力した場合に<math>x\in{}L</math>である確率も、「いいえ」を出力した場合に<math>x\notin{}L</math>である確率も1であるときに言う。

[[NP困難|'''NP'''困難]]問題などのようにこれらのクラスよりも難しい問題では、乱択アルゴリズムでさえも十分ではなく、[[近似アルゴリズム]]が必要となる。

歴史的に見れば、1976年に[[ミラー-ラビン素数判定法]]によって[[素数判定]]が乱択アルゴリズムで効率的に解けることが発見され、乱択アルゴリズムの研究が盛んになった。当時、素数判定の実用的な[[決定的アルゴリズム]]は知られていなかった。

ミラー-ラビン素数判定法は、2つの正の整数 ''k'' と ''n'' について「''k'' は ''n'' が合成数であることの証拠である」というような二項関係に基づいている。これをもう少し具体化すると、
* ''n'' が合成数である証拠があるなら、''n'' は合成数（[[素数]]でない）である
* ''n'' が合成数なら、''n'' 未満の自然数の少なくとも4分の3は ''n'' の合成性の証拠である
* ''n'' と ''k'' が与えられたとき、''k'' が ''n'' の合成性の証拠かどうかを素早く判定するアルゴリズムがある

以上から、素数判定問題が Co-'''RP''' クラスであることを暗示していることがわかる。ある合成数 ''n'' より小さい100個の[[ランダム]]に選ばれた数があるとき、合成数である証拠となる数を見つけられない確率は (1/4)<sup>100</sup> であり、多くの実用的な目的にはこれが十分によい[[素数判定]]となる。''n'' が大きい場合、これ以外の実用的な素数判定法は存在しないだろう。間違う確率は、乱数を使った判定を行う回数を増やせば増やすほど減っていく。

従って、実際には間違う確率を非常に小さくできるため、間違った場合のことは無視できる。実際、素数判定の多項式時間の決定的アルゴリズムが発見されたが（[[AKS素数判定法]]）、[[暗号]][[ソフトウェア]]では未だに乱択アルゴリズムが使われていることも多く、将来的にも全て決定的アルゴリズムに置換されることにはならないだろう。

== 乱数列の選択 ==
乱数列の生成には、[[擬似乱数]]を使用することもあれば、真の乱数を利用することもある。「良い」乱数列である必要性に関しては、他の多くの乱数の応用の場合と同様だろう。再現性のためには、真の乱数であればどのような乱数列が使用されたかを全て保存しなければならない（擬似乱数であれば、シードだけ保存しておけば再現できる）。真の乱数には、それの生成に要する時間的コストといった問題もある（情報理論と物理法則にもとづく、絶対的な限界がある）。

== 応用 ==
実用的なアルゴリズムとしては最も有名な[[クイックソート]]でも、ランダム性が有効である。このアルゴリズムの決定的なバージョンで ''n'' 個の数をソートするのに要する時間は最悪で ''[[ランダウの記号|O]](n<sup>2</sup>)'' となる（既にソートされている入力を使った場合）。しかし、事前にランダムに要素を入れ替えてからクイックソートを行うと、どんな入力であっても高い確率で ''O(n log n)'' の時間で完了する。ソート対象が大きければ大きいほど、この違いは重要となる。

より複雑な例として、[[グラフ理論]]での乱択アルゴリズムの利用として、以下のような[[最大フロー最小カット定理|最小カット]]を求める乱択アルゴリズムがある。

    '''procedure''' find_min_cut(無向グラフ <var>G</var>) '''is'''
        '''while''' グラフ <var>G</var> 中に2つ以上のノードが存在する '''do'''
            <var>G</var> から無作為にエッジ (u,v) を選ぶ
            そのエッジが多重辺であれば縮約する
            すべてのループを削除する
        '''end''' '''while'''
        残っているエッジを出力する
    '''end''' '''procedure'''

ここで、エッジ (u,v) を縮約するとは、新たなノード w を追加し、(u,x<sub>i</sub>) や (v,x<sub>i</sub>) といったエッジ（枝）を（w,x<sub>i</sub>）と置換し、グラフ G から u と v を削除することを意味する。[[File:Edge contraction.svg|thumb|縮約の図示]]

''n = |V[G]|'' とすると、このアルゴリズムが最小カットを出力する確率は最低でも ''n<sup>-2</sup>'' であり、''n<sup>2</sup>log(n)'' 回試行してその中で最小の出力を選べば、非常に高い確率で最小カットが得られる。

== 脱乱択（derandomization） ==
一般に、乱択アルゴリズムは同じ問題の[[決定的アルゴリズム]]に比較してより洗練されていて、[[計算資源]]の消費も少ない。

逆に乱択アルゴリズムからランダム性を除去し、強力な決定的アルゴリズムを構築する研究が活発に行われている。<!-- This general method is, of course, central in resolving many [[:en:complexity class|complexity class]]es describing randomized computation. -->
実際、多項式時間アルゴリズムの場合、乱数はあっても無くても差がないのではないかと予想されている。([[P=BPP予想]])。
<!-- 以下、制御工学的な話が続いていたが省略（訳者）-->

== 脚注 ==
{{reflist}}

==参考文献==
* R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York (NY), 1995.
* M. Mitzenmacher and E. Upfal. Probability and Computing : Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005.
* Thomas H. Cormen, Charles E. Leiserson, [[ロナルド・リベスト|Ronald L. Rivest]], and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. Chapter 5: Probabilistic Analysis and Randomized Algorithms, pp.91&ndash;122.
* {{cite book|author = Christos Papadimitriou | date = 1993年 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st edition | id = ISBN 0-201-53082-1}} Chapter 11: Randomized computation, pp.241&ndash;278.
* R. Tempo, G. Calafiore and F. Dabbene. Randomized Algorithms for Analysis and Control of Uncertain Systems. Springer-Verlag, London, 2005, ISBN 1-85233-524-6.
* R. Motwani and P. Raghavan. Randomized Algorithms. A survey on Randomized Algorithms. [http://portal.acm.org/citation.cfm?id=234313.234327]

* 玉木久夫：「乱択アルゴリズム」、共立出版、ISBN 978-4-320-12170-6（2008年8月15日）。
* 結城浩：「数学ガール/乱択アルゴリズム」、SBクリエイティブ、 ISBN 978-4797361001（2011年2月）。

== 外部リンク ==
* [https://web.cvent.com/event/02659cce-b9d1-4935-9d0a-5b671ea52fca/summary RASC: Randomized Algorithms for Scientific Computing]
* [https://www.osti.gov/biblio/1807223 Randomized Algorithms for Scientific Computing (RASC), OSTI.GOV (2021年7月10日レポート、PDFファイル).]

{{アルゴリズム}}

{{DEFAULTSORT:らんたくあるこりすむ}}
[[Category:ランダム・アルゴリズム|*]]
[[Category:アルゴリズム解析]]
[[Category:統計的ランダムネス]]
[[Category:数学に関する記事]]