乱択アルゴリズム 応用

ウィキペディア

乱択アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/04/16 01:16 UTC 版)

応用

実用的なアルゴリズムとしては最も有名なクイックソートでも、ランダム性が有効である。このアルゴリズムの決定的なバージョンで 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) 回試行してその中で最小の出力を選べば、非常に高い確率で最小カットが得られる。