| 翻訳と辞書 |
乱択アルゴリズム[らんたくあるごりずむ]
乱択アルゴリズム（らんたくアルゴリズム、、ランダム・アルゴリズム）または確率的アルゴリズム（かくりつてき-、）は、その論理の一部に無作為性を導入したアルゴリズムである。通常、このようなアルゴリズムは擬似乱数を使うよう実装される。ランダムなビット列を補助入力とし、アルゴリズムの動作を誘導することで「平均的に」よい性能を実現することを目的としている。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を「期待実行時間; expected runtime」と呼ぶ。最悪の場合は滅多に起きないので無視できる。
== 乱択アルゴリズムが使われる背景 ==
''n'' 個の要素からなる配列から 'a' という要素を探す問題を考える。この配列の各要素は半分が 'a' で残りが 'b' である。単純な手法は、配列の各要素を順次見ていく方法だが、配列の先頭の方に 'b' がかたまっている場合に長時間かかってしまう（n/2回の操作）。逆の順番で見て行っても、1つおきに見ていったとしても同じような問題が発生する。実際、要素を調べる順序が固定されている全ての戦略（決定性アルゴリズム）では、あらゆる組合せの入力に対して常に高速なアルゴリズムであるとは保証できない。一方、配列要素を「無作為な」順序で調べる場合、入力がどうであっても、高い確率で 'a' を素早く見つけ出すことができる。
乱択アルゴリズムは、入力に故意に間違いが含まれているような場合に特に有用である。そのため、暗号理論でランダム性がよく使われる。暗号では、敵が予測できる擬似乱数は使えない（そのような擬似乱数ではアルゴリズムが実質的には決定性を帯びる）。従って、真の乱数を使うか、暗号理論上安全とされる擬似乱数を使う必要がある。また、量子コンピュータでは本質的にランダム性が備わっている。
上の例では、乱択アルゴリズムは常に正しい答えを返す。実行時間が長くなる可能性も確率は低いが存在する。しかし、エラーを返す可能性を認めてでも、常に素早く答えを得たいということもある。前者のような乱択アルゴリズムをラスベガス法と呼び、後者のような乱択アルゴリズムをモンテカルロ法と呼ぶ。ラスベガス法で所定の時間内に完了しない場合に間違った答えを返すようにすれば、モンテカルロ法に変換される。
また、確率解析学はありうべき全ての入力の集合に何らかの前提を設ける。この前提が効率的なアルゴリズムの設計に使われる。あるアルゴリズムへの入力の性質が不明な場合、確率解析的手法は使えない。乱択アルゴリズムでは、プログラム内の擬似乱数生成機能が使われることが多い。あるアルゴリズムが乱択であると言えるのは、その出力が入力だけでなく擬似乱数にも依存する場合である。
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「乱択アルゴリズム」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|