乱択アルゴリズム : Freivald のアルゴリズム
乱択アルゴリズムは,確率的に解を返すアルゴリズムである.このようなアルゴリズムの例である Freival のアルゴリズムとその解説を行う.
まず,乱択アルゴリズムは二つの種類に大別できる.
- ラスベガスアルゴリズム : 解は常に正しいが,どれくらい時間がかかるかはランダム
- モンテカルロアルゴリズム : 時間は一定だが,解はランダム(1/2以上の確率で正しい)
モンテカルロアルゴリズムが与えられたら,ラスベガスアルゴリズムを自明に生成できる.(実際には,任意の確率で正しい解を生成できるアルゴリズムを生成できる.)
一方でラスベガスアルゴリズムが与えられた時,モンテカルロアルゴリズムを求める方法は自明ではない.
Quick Sort
- 種類 : ラスベガスアルゴリズム
- 平均計算量 :
\mathcal{O}(n\log n) - 最悪計算量
\mathcal{O}(n^2)
クイックソートはよく知られたアルゴリズムであるが,同時に確率的アルゴリズムでもある.
クイックソートの詳細については省略する.
この手法は,リストのどの元でリストを二分するかという選択の時点で確率性が用いられている.しかしながらこの確率性は(理論的には)本質的なものではなく,中央値を用いれば常に最適な計算量(定数部分は重くなるので非実用的だが)を実現できる.
この証明は省略する.
Freival のアルゴリズム
- 種類 : モンテカルロアルゴリズム
- 計算量 :
\mathcal{O}(n^2)
古典的な確率アルゴリズムである Freival のアルゴリズムは以下のようなアルゴリズムである.
Freival のアルゴリズム:
- 入力 :
次元行列n\times n .A,B,C - 出力 : 以下の式を満たす時 YES, 満たさない時 NO.
AB=C. - 手順 :
- ランダムな
次元ベクトルn を生成する.r\in \{0,1\}^n - 次の値
を計算する.p
p=A(Br)-Cr -
なら Yes,p = 0 ならば No.p\neq 0
- ランダムな
証明
正しさを示しておこう.この証明はWikipediaにもとづいている.
定理 : Freival のアルゴリズムは
-
ならば確率1 で YES を返す.AB=C -
ならば確率1/2 以上で NO を返す.AB\neq C
証明 :
このとき次が成立する.(
一方で Freival のアルゴリズムでランダムに選ぶ
である.アルゴリズムの定義から,
まず注意として
次に
またこれについて,確率はベイズの定理より
と分割できる.このとき (
であるので,
が成立する.ゆえに
ゆえに
次に計算量について考える.
定理 : Freival のアルゴリズムの計算量は
証明 :
Discussion