Weblio辞書辞典>辞書･百科事典>乱択ｱﾙｺﾞﾘｽﾞﾑ>乱択ｱﾙｺﾞﾘｽﾞﾑの1ﾍﾟｰｼﾞ目
乱択ｱﾙｺﾞﾘｽﾞﾑとは?
ｽﾎﾟﾝｻｰﾘﾝｸ
乱択ｱﾙｺﾞﾘｽﾞﾑならｱﾏｿﾞﾝ
お急ぎ便利用で当日､翌日にお届け｡ｱﾏｿﾞﾝは常時無料配送／一部除く
ｳｨｷﾍﾟﾃﾞｨｱ目次へ乱択ｱﾙｺﾞﾘｽﾞﾑ（らんたくｱﾙｺﾞﾘｽﾞﾑ､英: Randomized algorithm､ﾗﾝﾀﾞﾑ･ｱﾙｺﾞﾘｽﾞﾑ）または確率的ｱﾙｺﾞﾘｽﾞﾑ（かくりつてき-､英: Probabilistic algorithm）は､その論理の一部に無作為性を導入したｱﾙｺﾞﾘｽﾞﾑである｡
通常､このようなｱﾙｺﾞﾘｽﾞﾑは擬似乱数を使うよう実装される｡ﾗﾝﾀﾞﾑなﾋﾞｯﾄ列を補助入力とし､ｱﾙｺﾞﾘｽﾞﾑの動作を誘導することで｢平均的に｣よい性能を実現することを目的としている｡
形式的には､乱択ｱﾙｺﾞﾘｽﾞﾑの性能はﾗﾝﾀﾞﾑﾋﾞｯﾄ列で決定される確率変数となる｡
その期待値を｢期待実行時間; expected runtime｣と呼ぶ｡
最悪の場合は滅多に起きないので無視できる｡目次
1 乱択ｱﾙｺﾞﾘｽﾞﾑが使われる背景
2 複雑性
3 応用
4 非乱数化
5 参考文献
n 個の要素からなる配列から 'a' という要素を探す問題を考える｡
この配列の各要素は半分が 'a' で残りが 'b' である｡
単純な手法は､配列の各要素を順次見ていく方法だが､配列の先頭の方に 'b' がかたまっている場合に長時間かかってしまう（n/2回の操作）｡
逆の順番で見て行っても､1つおきに見ていったとしても同じような問題が発生する｡
実際､要素を調べる順序が固定されている全ての戦略（決定性ｱﾙｺﾞﾘｽﾞﾑ）では､あらゆる組合せの入力に対して常に高速なｱﾙｺﾞﾘｽﾞﾑであるとは保証できない｡
一方､配列要素を｢無作為な｣順序で調べる場合､入力がどうであっても､高い確率で 'a' を素早く見つけ出すことができる｡
乱択ｱﾙｺﾞﾘｽﾞﾑは､入力に故意に間違いが含まれているような場合に特に有用である｡
そのため､暗号理論でﾗﾝﾀﾞﾑ性がよく使われる｡
暗号では､敵が予測できる擬似乱数は使えない（そのような擬似乱数ではｱﾙｺﾞﾘｽﾞﾑが実質的には決定性を帯びる）｡
従って､真の乱数を使うか､暗号理論上安全とされる擬似乱数を使う必要がある｡
また､量子ｺﾝﾋﾟｭｰﾀでは本質的にﾗﾝﾀﾞﾑ性が備わっている｡
上の例では､乱択ｱﾙｺﾞﾘｽﾞﾑは常に正しい答えを返す｡
実行時間が長くなる可能性も確率は低いが存在する｡
ｴﾗｰを返す可能性を認めてでも､常に素早く答えを得たいということもある｡
前者のような乱択ｱﾙｺﾞﾘｽﾞﾑをﾗｽﾍﾞｶﾞｽ法と呼び､後者のような乱択ｱﾙｺﾞﾘｽﾞﾑをﾓﾝﾃｶﾙﾛ法と呼ぶ｡
ﾗｽﾍﾞｶﾞｽ法で所定の時間内に完了しない場合に間違った答えを返すようにすれば､ﾓﾝﾃｶﾙﾛ法に変換される｡
また､確率解析学はありうべき全ての入力の集合に何らかの前提を設ける｡
この前提が効率的なｱﾙｺﾞﾘｽﾞﾑの設計に使われる｡
あるｱﾙｺﾞﾘｽﾞﾑへの入力の性質が不明な場合､確率解析的手法は使えない｡
乱択ｱﾙｺﾞﾘｽﾞﾑでは､ﾌﾟﾛｸﾞﾗﾑ内の擬似乱数生成機能が使われることが多い｡
あるｱﾙｺﾞﾘｽﾞﾑが乱択であると言えるのは､その出力が入力だけでなく擬似乱数にも依存する場合である｡
計算複雑性理論では､乱択ｱﾙｺﾞﾘｽﾞﾑは確率的ﾁｭｰﾘﾝｸﾞﾏｼﾝとしてﾓﾃﾞﾙ化される｡
ｽﾎﾟﾝｻｰﾘﾝｸ
乱択ｱﾙｺﾞﾘｽﾞﾑならｱﾏｿﾞﾝ
お急ぎ便利用で当日､翌日にお届け｡ｱﾏｿﾞﾝは常時無料配送／一部除く
注目の情報
ﾍﾟｰｼﾞ(1/4)
次ﾍﾟｰｼﾞ≫