乱択アルゴリズム

ウィキペディア

乱択アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/11/26 18:36 UTC 版)

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

乱択アルゴリズムが使われる背景

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

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

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

複雑性

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

RP

最も基本的な確率的複雑性クラス。決定問題LがRPに属するとは、ある(最悪計算量の意味での)多項式時間乱択アルゴリズムAが存在して、A(x)が「はい」を出力した場合に $x\in {}L$

縮約の図示

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

脱乱択（derandomization）

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

逆に乱択アルゴリズムからランダム性を除去し、強力な決定的アルゴリズムを構築する研究が活発に行われている。 実際、多項式時間アルゴリズムの場合、乱数はあっても無くても差がないのではないかと予想されている。(P=BPP予想)。

参考文献

• 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–122.
• Christos Papadimitriou (1993年). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1  Chapter 11: Randomized computation, pp.241–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. [1]

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

外部リンク

• RASC: Randomized Algorithms for Scientific Computing
• Randomized Algorithms for Scientific Computing (RASC), OSTI.GOV (2021年7月10日レポート、PDFファイル).