宮崎修一
京都大学 学術情報メディアセンター
アルゴリズム入門（ 10 ）
（乱択アルゴリズム）
決定性アルゴリズム（これまで出てきたアルゴリズム）：
同じ入力に対しては、決まった動作しかしない。
常に同じ解が得られる。
乱択アルゴリズム（確率アルゴリズムとも呼ばれる）：
アルゴリズムが動作中にさいころを振る。さいころの出目に よって、動作を変える。
よって、同じ入力でも、さいころの出目によって、違う解が 得られる可能性がある。
まずは、簡単な話
…
n
個の箱の中に、k
個当たりが入っている。アルゴリズムの仕事：
箱を、順番に開けていく。当たりを
1
個でも見つければ終了。決定性アルゴリズムに出来ること： 開ける箱の順番を決定する。
どんな入力が来ても、箱を開ける順序は同じ。
（箱を開けた結果によって、その先の順番を変えても良いが、
当たりが出たらそこで終わりなので、アルゴリズムの動作中 は、常に外れしか出ない。つまり「箱を開けた結果」に差は ないので、結局「その先の順番を変える」ことに意味はない。）
どのような決定性アルゴリズムを設計したとしても、
それに対する悪い入力が存在する。
最初の
n-k
個が外れ。乱択アルゴリズム：
n
個の箱から1
個を、各 の確率で選ぶ。当たりが出るまで繰り返す。
1
回で当たる確率は 。n k
n 1
平均 回で終わる。
k n
例えば
3 k = n
決定性アルゴリズム： ステップ 乱択アルゴリズム ：
3
ステップどんな入力に対しても
3 1
2 n +
MAX CUT
（以前出てきた）入力：グラフ
G
出力：
G
の頂点集合の2
分割間にある枝数が出来るだけ多くなるように
例
4
本5
本局所探索法
→
近似度2
貪欲法→
近似度2
乱択アルゴリズムでも（平均的）近似度が
2
であることを示す。Ａ Ｂ
各頂点、コインを投げて、
表が出ればＡへ 裏が出ればＢへ
（以前やった）
近似度の解析
ある
1
つの枝に着目表 表 ×
表 裏 ○
裏 表 ○
裏 裏 ×
この枝がカットされる確率
＝
1/2
どの枝も、カットされる確率は
1/2
（
1
本の枝のカットされる期待値は1/2
本）期待値の線形性より、カットされる枝数の期待値は 1
2 + 1
2 + ⋯ 1
2 = 1 2 𝐸
（独立でなくても構わない）
最適解は≤ |𝐸|
よって、平均的に
2-
近似アルゴリズム和積形論理式の最大充足問題（
MAX SAT
）（前に出た）
f = (x
1+x
2+x
3) (x
1+x
8) … (x
3+x
6+x
7+x
12)
入力：和積形論理式
出力：
x , x , …, x
に0/1
を割り当てて、1
となる項の数を 最大にする。1 2 nx
i=0
ならばx
i=1
項
x
はx
の反転を表すx
i やx
i をリテラルというMAX E3-SAT
各項に、リテラルがちょうど
3
つずつ。f = (x
1+x
2+x
3) (x
1+x
8+x
7) … (x
3+x
6+x
12)
MAX E3-SAT
に対する確率アルゴリズム：各変数に、確率
1/2
で0
か1
かを割り当てる。問題：このときの平均近似度は？
（
MAX CUT
のときと似たような考え方で出来る）(x +x +x )
2 6 7
1
つの項が1
になる確率0 0 0
○0 0 1
×0 1 0
○0 1 1
○1 0 0
○1 0 1
○1 1 0
○1 1 1
○7/8
項が
m
個あるとしたら、1
になる項数の期待値はm 8 7
最適解 ≦
m
脱乱択化（
derandomization
）乱択アルゴリズムを決定性アルゴリズムに直すこと。
高い確率で正しい答えを出す。平均的に良い解を出す。
↓
常に正しい答えを出す。常に良い解を出す。
MAX E3-SAT
の例：ランダムな割り当て
→
項がm
個あるなら、平均的に 項を充足できる。必ず 項を充足する解を見つける。
8 m 7
8 m
7
f = (x
1+x
4+x
3) (x
2+x
8+x
7) … (x
1+x
6+x
8)
各変数に、確率1/2
で0
または1
を割り当てる場合。MAX E3-SAT
の例：ランダムな割り当て
→
項がm
個あるなら、平均的に 項を充足できる。必ず 項を充足する解を見つける。
8 m 7
8 m
7
脱乱択化f = (1 +x
4+x
3) (x
2+x
8+x
7) … (0 +x
6+x
8)
それぞれの項が充足される確率は変化する。
1 7/8 3/4
強制的に
x
1=1
としてみる残りの変数に、確率
1/2
で0
または1
を割り当てる場合。充足される項数の期待値＝
1+7/8+
・・・+3/4 =k
1とおく(
さっきは、7/8+7/8+
・・・7/8 = 7m/8
だった。)
f = (0 +x
4+x
3) (x
2+x
8+x
7) … (1 +x
6+x
8) 7/8 1
3/4
同様に
x
1=0
としてみる残りの変数に、確率
1/2
で0
または1
を割り当てる場合。充足される項数の期待値＝
3/4+7/8+
・・・+1 =k
0とおくx
1x
2x
3 ・・・x
n のそれぞれを、確率1/2
で0
または1
にする。x
1x
2x
3 ・・・x
n のそれぞれを、確率1/2
で0
または1
にする。を確率
1/2
で0
または1
にしたあと、そのとき充足される項数の期待値は
7m/8
そのとき充足される項数の期待値は？
それぞれが確率
1/2
で起こるのだから、期待値は 0 12 1 2
1 k
+k x
1が0
になったあとの期待値：k0k
1x
1が1
になったあとの期待値：m k
k 1 7
1
1
0 + =
上の
2
つは同じことをやっているのでm
k 8
7
0
平均の議論より、
k m
8 7
1 または
m
k 8
7
0 ならば
x
1=0
とするならば
x
1=1
とするm
k 8
7
1
変数を
1
つ減らして、充足する項数の期待値は7m/8
以上を 維持したまま。これを同様に繰り返していくと、変数の値がすべて決まる。
その時の「期待値」は、実は真の値。
（もはや確率的な議論ではなくなっているから）
模式的に描くと
期待値：
80
期待値：
68
期待値：92
x
1=0 x
1=1
x
2=0
x
2=0 x
2=1 x
2=1
95 89
99 91
x
3=0 x
3=1 x
3=0 x
3=1 x
3=0 x
3=1
x
3=0 x
3=1
少なくとも、元の期待値以上の答が得られる
問題：
