乱択アルゴリズム Randomized algorithm

出典: フリー百科事典『ウィキペディア（Wikipedia）』 Source: material may be challenged Wikipedia encyclopedia (Wikipedia) 』

移動: ナビゲーション , 検索 Jump to: navigation, search

乱択アルゴリズム （らんたく-、英 : Randomized algorithm ）または確率的アルゴリズム （かくりつてき-、英 : Probabilistic algorithm ）は、その論理の一部に無作為性を導入したアルゴリズムである。 Randomized algorithm (Rantaku -, UK: Randomized algorithm) or probabilistic algorithms (stochastic come -, UK: Probabilistic algorithm) is an algorithm introduced the random part of the logic that. 通常、このようなアルゴリズムは擬似乱数を使うよう実装される。 Usually, these algorithms are implemented to use a pseudo-random number. ランダムなビット列を補助入力とし、アルゴリズムの動作を誘導することで「平均的に」よい性能を実現することを目的としている。 Auxiliary input and random bits, and can induce the behavior of the algorithm "on average" are intended to achieve good performance. 形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。 Formally, the performance of randomized algorithms will be determined by a random variable and random bits. その期待値を「期待実行時間; expected runtime」と呼ぶ。 Value expected that "expected running time; expected runtime" called. 最悪の場合は滅多に起きないので無視できる。 If the worst that can happen so rarely ignored.

目次 Contents

[ 編集 ] 乱択アルゴリズムが使われる背景 Background randomized algorithm is used

n個の要素からなる配列から 'a' という要素を探す問題を考える。 n from an array of elements of each 'a' think that the problem of finding the elements. この配列の各要素は半分が 'a' で残りが 'b' である。 Each element of this array is half 'a' the rest 'b' is. 単純な手法は、配列の各要素を順次見ていく方法だが、配列の先頭の方に 'b' がかたまっている場合に長時間かかってしまう（n/2回の操作）。 Simple technique, but how we look at each element of the array sequentially, toward the beginning of the array 'b' if it takes a long time in a cluster is (n / 2 single operation). 逆の順番で見て行っても、1つおきに見ていったとしても同じような問題が発生する。 We have also seen the reverse order, one similar problems as every one went to see. 実際、要素を調べる順序が固定されている全ての戦略（決定性アルゴリズム）では、あらゆる組合せの入力に対して常に高速なアルゴリズムであるとは保証できない。 In fact, all strategies that determine a fixed order the elements (deterministic algorithm), the algorithm is fast and the input of any combination is not always guaranteed. 一方、配列要素を「無作為な」順序で調べる場合、 入力がどうであっても、高い確率で 'a' を素早く見つけ出すことができる。 Meanwhile, the array element "random" If you look in the order, even if the input is a high probability 'a' can quickly find out.

乱択アルゴリズムは、入力に故意に間違いが含まれているような場合に特に有用である。 Randomized algorithm is particularly useful when a mistake like that deliberately included in the input. そのため、暗号理論でランダム性がよく使われる。 Therefore, the use of often random cryptography. 暗号では、敵が予測できる擬似乱数は使えない（そのような擬似乱数ではアルゴリズムが実質的には決定性を帯びる）。 The cipher is a pseudo-random number can not be used to predict the enemy (in such a pseudo-random algorithm that effectively take the decision). 従って、真の乱数を使うか、暗号理論上安全とされる擬似乱数を使う必要がある。 So, why use a true random number, it is necessary to use a pseudo-random cipher is theoretically safe. また、量子コンピュータでは本質的にランダム性が備わっている。 The computer is equipped with quantum randomness in nature.

上の例では、乱択アルゴリズムは常に正しい答えを返す。 In the above example is a randomized algorithm always returns the correct answer. 実行時間が長くなる可能性も確率は低いが存在する。 Probability could be there a long time to run low. エラーを返す可能性を認めてでも、常に素早く答えを得たいということもある。 But acknowledged the possibility of returning the error, there is always that want a quick answer. 前者のような乱択アルゴリズムをラスベガス法と呼び、後者のような乱択アルゴリズムをモンテカルロ法と呼ぶ。 Las Vegas algorithm is called randomized algorithms such as the former, the algorithm called Monte Carlo method selected, such as turbulence in the latter. ラスベガス法で所定の時間内に完了しない場合に間違った答えを返すようにすれば、モンテカルロ法に変換される。 If you return the wrong answer so if it does not complete within the time prescribed by law in Las Vegas, will be converted to Monte Carlo.

また、確率解析学はありうべき全ての入力の集合に何らかの前提を設ける。 Also, establish a set of all input assumptions Haariubeki some stochastic calculus. この前提が効率的なアルゴリズムの設計に使われる。 Used to design more efficient algorithms for this assumption. あるアルゴリズムへの入力の性質が不明な場合、確率解析的手法は使えない。 If you are unsure of the nature of the input to the algorithm, probabilistic analysis techniques can not be used. 乱択アルゴリズムでは、プログラム内の擬似乱数生成機能が使われることが多い。 Randomized algorithms are often used pseudo-random number generation function in the program. あるアルゴリズムが乱択であると言えるのは、その出力が入力だけでなく擬似乱数にも依存する場合である。 And say there is a randomized algorithm is a pseudo-random number also depends on if you input as well as its output.

[ 編集 ] 複雑性 Complexity

計算複雑性理論では、乱択アルゴリズムは確率的チューリングマシンとしてモデル化される。 Complexity theory calculations, the algorithm selected the turbulence is modeled as a probabilistic Turing machine. ラスベガス法とモンテカルロ法を含むいくつかの「複雑性クラス」が研究されている。 Some, including Las Vegas and Monte Carlo method "Class of complexity" that has been studied.

RP ：最も基本的な確率的複雑性クラス。 RP: Probabilistic complexity classes the most basic. 決定問題 LがRPに属するとは、ある(最悪計算量の意味での) 多項式時間乱択アルゴリズムAが存在して、 A(x)が「yes」を出力した場合に Decision problem L belongs to the RP, there (in the sense of the amount calculated worst-case) polynomial time randomized algorithms exist A, A (x) is "yes" if the output $x \ in () L$ である確率は1/2以上で、「no」を出力した場合に Probability is 1 / 2 or more, "no" if the output $x \ notin () L$ である確率は1であるときに言う。 Is the probability that when one says. (なお上述の「1/2」を0と1の間にある任意の定数に置き換えても定義は変わらない)。 (The above "1 / 2" to 0 and 1 to replace the constant defined between any of the same).
Co-RP ：RPの補問題のクラス。 Co-RP: RP complement of the class of problems. すなわち、 L ^cがRPに属するとき、決定問題LはCo-RPに属するという。 Ie, L ^c when belonging to the RP, a decision problem L belongs to the Co-RP.
BPP ：決定問題LがBPPに属するとは、ある(最悪計算量の意味での)多項式時間乱択アルゴリズムAが存在して、 A(x)が「yes」を出力した場合に BPP: the decision problem L belongs to the BPP, there (in the sense of worst-case complexity) polynomial time randomized algorithms exist A, A (x) is "yes" if the output $x \ in () L$ の元である確率も、「no」を出力した場合に The probability of the original, "no" if the output $x \ notin () L$ である確率も2/3以上であるときに言う。 Probability of 2 / 3 or more say when. (なお上述の「2/3」を1/2と1の間にある任意の定数に置き換えても定義は変わらない)。 (The above "2 / 3" to 1 / 2 and 1 to replace the constant defined between any of the same).
ZPP ：決定問題LがZPPに属するとは、(最悪時間は多項式とは限らないが)平均は多項式時間のある乱択アルゴリズムAが存在し、 A(x)が「yes」を出力した場合に ZPP: the decision problem L belongs to ZPP (polynomial is not always the worst time) with the average randomized polynomial time algorithm A exists, A (x) is "yes" if the output $x \ in () L$ の元である確率も、「no」を出力した場合に The probability of the original, "no" if the output $x \ notin () L$ である確率も1であるときに言う。 When one says that the probability is.

NP困難問題などのようにこれらのクラスよりも難しい問題では、乱択アルゴリズムでさえも十分ではなく、近似アルゴリズムが必要となる。 NP on these difficult issues than the class of problems such as difficult, not enough even for randomized algorithms, which require approximation algorithms.

歴史的に見れば、1976年にミラー-ラビン素数判定法によって素数判定が乱択アルゴリズムで効率的に解けることが発見され、乱択アルゴリズムの研究が盛んになった。 If you look historically, 1976 was a mirror - was discovered to be solved efficiently in a randomized primality testing algorithm by Rabin primality test, were randomized algorithm actively researched. 当時、素数判定の実用的な決定的アルゴリズムは知られていなかった。 At that time, an algorithm for primality practical decision was not known.

ミラー-ラビン素数判定法は、2つの正の整数kとnについて「 kはnが合成数であることの証拠である」というような二項関係に基づいている。 Miller - Rabin primality test is one of two positive integers n and k for "k is the evidence that n is composite" is based on such a binary relation. これをもう少し具体化すると、 More concrete and this

nが合成数である証拠があるなら、 nは合成数（素数でない）である If there is evidence that n is composite, n is the number of composite (not prime) is
nが合成数なら、 n未満の自然数の少なくとも4分の3はnの合成性の証拠である If n is composite, n at least natural number n is less than three-quarters is evidence of synthesis of
nとkが与えられたとき、 kがnの合成性の証拠かどうかを素早く判定するアルゴリズムがある Given n and k, k n have a fast algorithm to determine whether evidence of synthesis of

以上から、素数判定問題が Co- RPクラスであることを暗示していることがわかる。 From above, the Co-RP Primes know that it is indicative of a class. ある合成数nより小さい100個のランダムに選ばれた数があるとき、合成数である証拠となる数を見つけられない確率は (1/4) ¹⁰⁰であり、多くの実用的な目的にはこれが十分によい素数判定となる。 Composite number n less than 100 when there are a few of the pieces chosen randomly, the probability that evidence will not find a composite number is (1 / 4) ¹⁰⁰ and, in many practical purposes Primes will be good enough this. nが大きい場合、これ以外の実用的な素数判定法は存在しないだろう。 If n is large, non-practical primality which will not exist. 間違う確率は、乱数を使った判定を行う回数を増やせば増やすほど減っていく。 Probability of mistakes is reduced The more we do to determine the number of times with a random number.

従って、実際には間違う確率を非常に小さくできるため、間違った場合のことは無視できる。 So, in fact, a very small probability to be wrong, if it's wrong to ignore. 実際、素数判定の多項式時間の決定的アルゴリズムが発見されたが（ AKS素数判定法）、暗号ソフトウェアでは未だに乱択アルゴリズムが使われていることも多く、将来的にも全て決定的アルゴリズムに置換されることにはならないだろう。 In fact, were found in polynomial time deterministic algorithm for primality (AKS-test prime), the software encryption is often used in randomized algorithms still are replaced by the deterministic algorithm in the future all As used herein will have to.

[ 編集 ] 応用 Applications

実用的なアルゴリズムとしては最も有名なクイックソートでも、ランダム性が有効である。 As a practical algorithm is also a sort most popular quick, effective randomness. このアルゴリズムの決定的なバージョンでn個の数をソートするのに要する時間は最悪でO (n ² )となる（既にソートされている入力を使った場合）。 The definitive version of this algorithm takes time to sort n the number of pieces is the worst O (N ²⁾ and (using the input is already sorted). しかし、事前にランダムに要素を入れ替えてからクイックソートを行うと、どんな入力であっても高い確率でO(n log n)の時間で完了する。 However, after sorting quick before replacing a random element, with high probability even what type O (n log n) time to complete. ソート対象が大きければ大きいほど、この違いは重要となる。 The larger is being sorted, this difference becomes important.

より複雑な例として、グラフ理論での乱択アルゴリズムの利用として、以下のような最小カットを求める乱択アルゴリズムがある: As more complex cases, as the use of randomized algorithms in graph theory, there are algorithms selected random seek minimum cut as follows:

   find_min_cut(undirected graph G) { find_min_cut (undirected graph G) (
       while there are more than 2 nodes in G do { while there are more than 2 nodes in G do (
           pick an edge (u,v) at random in G AN pick Edge (U, V) at random in G
           contract the edge, while preserving multi-edges contract the edge, while preserving multi-edges
           remove all loops remove all Loops
       } )
       output the remaining edges output the remaining edges
   } )

ここで、「contracting an edge (u,v)」とは、新たなノード w を追加し、(u,x) や (v,x) といったエッジ（枝）を（w,x）と置換し、グラフ G から u と v を削除することを意味する。 Here, "contracting an edge (u, v)" is a new node w and add a, (u, x) and (v, x) and edge (branch) to (w, x) and replace with graph G from u and v means to remove.

n = |V[G]|とすると、このアルゴリズムが最小カットを出力する確率は最低でもn ^-2であり、 n ² log(n)回試行してその中で最小の出力を選べば、非常に高い確率で最小カットが得られる。 n = | V [G] |, and that the probability that this algorithm outputs a minimum cut is at least n ^-2 is, n ² log (n) I choose the minimum output and in its attempts, very obtained high probability the minimum cut.

[ 編集 ] 非乱数化 Non-randomized

一般に、乱択アルゴリズムは同じ問題の決定的アルゴリズムに比較してより洗練されていて、計算資源の消費も少ない。 In general, randomized algorithms is they are a more sophisticated algorithm in comparison with the same problem decisively, low consumption of computational resources.

逆に乱択アルゴリズムからランダム性を除去し、強力な決定的アルゴリズムを構築する研究が活発に行われている。 Remove the randomness from randomized algorithm Conversely, active research has been done to build a strong deterministic algorithm. 実際、多項式時間アルゴリズムの場合、乱数はあっても無くても差がないのではないかと予想されている。 In fact, if a polynomial time algorithm, random number that is expected to have no idea of the difference even without. ( P=BPP予想 )。 (P = BPP expected).

[ 編集 ] 参考文献 References

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York (NY), 1995. 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. 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.91122. 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, Addison Wesley. ISBN 0-201-53082-1 . Christos Papadimitriou (1993年). Computational Complexity, 1st Edition, Addison Wesley. ISBN 0-201-53082-1. Chapter 11: Randomized computation, pp.241278. 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. 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] R. Motwani and P. Raghavan. Randomized Algorithms. A Survey on Randomized Algorithms. [1]

ビデオジャパンは、最大でランク。