乱択アルゴリズムが使われる背景
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/01 06:20 UTC 版)
「乱択アルゴリズム」の記事における「乱択アルゴリズムが使われる背景」の解説
n 個の要素からなる配列から「a」という要素を探す問題を考える。この配列の各要素は半分が「a」で残りが「b」である。単純な手法は、配列の各要素を順次見ていく方法だが、配列の先頭の方に「b」がかたまっている場合に長時間かかってしまう（n/2回の操作）。逆の順番で見て行っても、ひとつおきに見ていったとしても同じような問題が発生する。実際、要素を調べる順序が固定されている全ての戦略（決定性アルゴリズム）では、あらゆる組合せの入力に対して常に高速なアルゴリズムであるとは保証できない。一方、配列要素を「無作為な」順序で調べる場合、入力がどうであっても高い確率で「a」を素早く見つけ出すことができる。 上の例では、乱択アルゴリズムは常に正しい答えを返す。実行時間が長くなる可能性も確率は低いが存在する。しかし、エラーを返す可能性を認めてでも、常に素早く答えを得たいということもある。前者のような乱択アルゴリズムをラスベガス法と呼び、後者のような乱択アルゴリズムをモンテカルロ法と呼ぶ。ラスベガス法で所定の時間内に完了しない場合に間違った答えを返すようにすれば、モンテカルロ法に変換される。 また、確率解析学はありうべき全ての入力の集合に何らかの前提を設ける。この前提が効率的なアルゴリズムの設計に使われる。あるアルゴリズムへの入力の性質が不明な場合、確率解析的手法は使えない。乱択アルゴリズムでは、プログラム内の擬似乱数生成機能が使われることが多い。あるアルゴリズムが乱択であると言えるのは、その出力が入力だけでなく擬似乱数にも依存する場合である。
※この「乱択アルゴリズムが使われる背景」の解説は、「乱択アルゴリズム」の解説の一部です。
「乱択アルゴリズムが使われる背景」を含む「乱択アルゴリズム」の記事については、「乱択アルゴリズム」の概要を参照ください。
- 乱択アルゴリズムが使われる背景のページへのリンク
