乱択アルゴリズム

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

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

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

複雑性

計算複雑性理論では、乱択アルゴリズムは確率的チューリングマシンとしてモデル化される。ラスベガス法とモンテカルロ法を含むいくつかの﹁複雑性クラス﹂が研究されている。 RP 最も基本的な確率的複雑性クラス。決定問題LがRPに属するとは、ある(最悪計算量の意味での)多項式時間乱択アルゴリズムAが存在して、A(x)が﹁はい﹂を出力した場合に

x\in {}L

である確率は1/2以上で、﹁いいえ﹂を出力した場合に

x\notin {}L

である確率は1であるときに言う。(なお上述の﹁1/2﹂を0と1の間にある任意の定数に置き換えても定義は変わらない)。 Co-RP RPの補問題のクラス。すなわち、L^cがRPに属するとき、決定問題LはCo-RPに属するという。 BPP 決定問題LがBPPに属するとは、ある(最悪計算量の意味での)多項式時間乱択アルゴリズムAが存在して、A(x)が﹁はい﹂を出力した場合に

x\in {}L

である確率も、﹁いいえ﹂を出力した場合に

x\notin {}L

である確率も2/3以上であるときに言う。(なお上述の﹁2/3﹂を1/2と1の間にある任意の定数に置き換えても定義は変わらない)。 ZPP 決定問題LがZPPに属するとは、(最悪時間は多項式とは限らないが)平均は多項式時間のある乱択アルゴリズムAが存在し、A(x)が﹁はい﹂を出力した場合に

x\in {}L

である確率も、﹁いいえ﹂を出力した場合に

x\notin {}L

である確率も1であるときに言う。 NP困難問題などのようにこれらのクラスよりも難しい問題では、乱択アルゴリズムでさえも十分ではなく、近似アルゴリズムが必要となる。歴史的に見れば、1976年にミラー-ラビン素数判定法によって素数判定が乱択アルゴリズムで効率的に解けることが発見され、乱択アルゴリズムの研究が盛んになった。当時、素数判定の実用的な決定的アルゴリズムは知られていなかった。ミラー-ラビン素数判定法は、2つの正の整数 kと nについて﹁k は nが合成数であることの証拠である﹂というような二項関係に基づいている。これをもう少し具体化すると、 ●n が合成数である証拠があるなら、n は合成数︵素数でない︶である ●n が合成数なら、n 未満の自然数の少なくとも4分の3は nの合成性の証拠である ●n と kが与えられたとき、k が nの合成性の証拠かどうかを素早く判定するアルゴリズムがある以上から、素数判定問題が Co-RP クラスであることを暗示していることがわかる。ある合成数 nより小さい100個のランダムに選ばれた数があるとき、合成数である証拠となる数を見つけられない確率は (1/4)¹⁰⁰ であり、多くの実用的な目的にはこれが十分によい素数判定となる。n が大きい場合、これ以外の実用的な素数判定法は存在しないだろう。間違う確率は、乱数を使った判定を行う回数を増やせば増やすほど減っていく。従って、実際には間違う確率を非常に小さくできるため、間違った場合のことは無視できる。実際、素数判定の多項式時間の決定的アルゴリズムが発見されたが︵AKS素数判定法︶、暗号ソフトウェアでは未だに乱択アルゴリズムが使われていることも多く、将来的にも全て決定的アルゴリズムに置換されることにはならないだろう。

乱数列の選択

乱数列の生成には、擬似乱数を使用することもあれば、真の乱数を利用することもある。﹁良い﹂乱数列である必要性に関しては、他の多くの乱数の応用の場合と同様だろう。再現性のためには、真の乱数であればどのような乱数列が使用されたかを全て保存しなければならない︵擬似乱数であれば、シードだけ保存しておけば再現できる︶。真の乱数には、それの生成に要する時間的コストといった問題もある︵情報理論と物理法則にもとづく、絶対的な限界がある︶。

応用

実用的なアルゴリズムとしては最も有名なクイックソートでも、ランダム性が有効である。このアルゴリズムの決定的なバージョンで n個の数をソートするのに要する時間は最悪で O(n²) となる︵既にソートされている入力を使った場合︶。しかし、事前にランダムに要素を入れ替えてからクイックソートを行うと、どんな入力であっても高い確率で O(n log n) の時間で完了する。ソート対象が大きければ大きいほど、この違いは重要となる。より複雑な例として、グラフ理論での乱択アルゴリズムの利用として、以下のような最小カットを求める乱択アルゴリズムがある。

   procedure find_min_cut(無向グラフ G) is
       while グラフ G 中に2つ以上のノードが存在する do
           G から無作為にエッジ (u,v) を選ぶ
           そのエッジが多重辺であれば縮約する
           すべてのループを削除する
       end while
       残っているエッジを出力する
   end procedure

ここで、エッジ (u,v) を縮約するとは、新たなノードwを追加し、(u,x_i) や (v,x_i) といったエッジ︵枝︶を︵w,x_i︶と置換し、グラフGからuとvを削除することを意味する。

縮約の図示

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

脱乱択（derandomization）

一般に、乱択アルゴリズムは同じ問題の決定的アルゴリズムに比較してより洗練されていて、計算資源の消費も少ない。逆に乱択アルゴリズムからランダム性を除去し、強力な決定的アルゴリズムを構築する研究が活発に行われている。実際、多項式時間アルゴリズムの場合、乱数はあっても無くても差がないのではないかと予想されている。(P=BPP予想)。

脚注

^ 英: expected runtime

参考文献

●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月︶。 ●結城浩‥﹁数学ガール/乱択アルゴリズム﹂、SBクリエイティブ、 ISBN 978-4797361001︵2011年2月︶。

外部リンク

[1] 英: expected runtime

[1]