アルゴリズム入門（5）（局所探索法））（局所探索法）

宮崎修一

京都大学 学術情報メディアセンター

アルゴリズム入門（ 5 ）

（局所探索法）

和積形論理式の最大充足問題（MAX SAT）

f = (x₁+x₂ +x₃ ) (x₁+x₈ ) … (x₃+x₆ +x₇ +x₁₂)

入力：和積形論理式

出力： x , x , …, x に0/1 を割り当てて、1となる項の数を 最大にする。^{1 2 n}

x_i =0ならば x_i =1 x_i =1ならば x_i =0

項

x はxの反転を表す

項の中にある変数が、どれか１つでも1であれば その項は1となる。

(x₁ +x₂ +x₃ ) 例

x₁=0 x₂=0 x₃=1 (x₁ +x₂ +x₃ )

の場合

0 1 1 (x₁ +x₂ +x₃ ) = 1

x₁=0 x₂=1 x₃=0 (x₁ +x₂ +x₃ )

の場合

(x +x +x ) = 0

項が「充足される」と言う

( )

(x₁ +x₂ +x₃ ) ( ) (x₁ x ₂ +x₃ ) ( )x₃ x₂ (x₁ +x₂ +x₃ ) (x ₁ +x₃ ) (x ₂ +x₃ )

問題：3変数からなる以下の入力の最適解は？

例：

2人の人物AとB。それぞれは「正直者」か「嘘つき」。

正直者は本当のことを言う。嘘つきは嘘を言う。

A: 「Bは嘘つきだ。」

B: 「Aは正直だ。」

変数 x _A ：Aが正直者ならば1、嘘つきならば0。 変数 x _B ：Bが正直者ならば1、嘘つきならば0。

変数 y _A ：Aの言っていることが正しければ1、間違っていれば0。 変数 y B ：Bの言っていることが正しければ1、間違っていれば0。 SATを利用して、いろいろな問題を解くことが出来る。

これらの変数を使って論理式を立てる。

( x_A + )y_{A A}が正直ならば、Aの言っていることは本当でなくてはならない。

x_A =1^ならば、y_A=1^{でなければならない。}

同様に、 ( x_A + )y_A ( x_B + )y_B ( x_B + )y_B

( y_A + )x_B ( y_A + )x_B ( y_B + )x_A ( y_B + )x_A

これらを全て満たす割り当てが、AとBが正直者か嘘つきかを表す。

別の例：時間割

簡単のため、小さな問題を取り扱う。

教室は2つ（r1, r2） 2日分（月曜と火曜）

1日3時間

先生は3人（t1, t2, t3）

講義は10個（c1, c2, …, c10） 先生の担当

t1: c1, c2, c3, c4 t2: c5, c6, c7

t3: c8, c9, c10

教室r1 月曜 火曜

1時間目 2時間目 3時間目

教室r2 月曜 火曜

1時間目 2時間目 3時間目

変数 x_i,j

①

②

③

④

⑤

⑥

⑦

⑧

⑨

⑩

⑪

⑫

c1 ～c10を、①～⑫の枠に割り当てる。

を用意する

x_i,j =1：講義 i を枠 j で行う。

=0： 〃 行わない。

（例えば x_c5,⑥ ）

「講義c1は必ず行わなくてはいけない。」

( x_c1,① + + … + x_c1,② x_c1,⑫ )

「講義c1は2回以上行わない。」

( x_c1,① + )xc1,② ( x_c1,① + )xc1,③ ・・・ ( x_c1,⑪ + )x_c1,⑫

「同じ先生の講義を同じ時間帯に割り当てない。」

( x_c1,① + )xc3,⑦ ( x_c1,② + )xc3,⑧ ・・・

「先生t2の講義を火曜日1時間目に割り当てない。」

( x_c5,④ )( x_c6,④ )( x_c7,④ )( x_c5,⑩ )( x_c6,⑩ )( x_c7,⑩ )

単純な解法

x₁, x₂ , …, x_n 0 0 0

1となる項の個数 0 0 1

1 1 1

…

14 43

22

これらの中で最大のものを 出力すればよい

2 ^{通りあるので}

指数時間アルゴリズム

n

局所探索法の考え方

0000000 0000001 0000010 0000011 0000100 0000101

0101100 0101101 0101110 0101111 0110000 0110001

…..

1つの割り当て

132

29 63

98

165 33

102

187 23

72

45 88

その割り当てによって 充足される項の数

2 個あるので、全てを 調べることは出来ない

n

局所探索法の考え方

ランダムに選んだ初期解から出発して、「近傍」に移りながら 良い解を探していく。

0101110

87

1101110 0101111 63

102

0101100

14

0101010

23

0100110

91 ¹¹ 0111110

0001110

75

近傍＝今の割り当てから、1変数だけ変更した割り当て

今よりも改善する近傍に移る。

0101110

87

1101110 0101111 63

102

0101100

14

0101010

23

0100110

91 ¹¹ 0111110

0001110

75

次はこれを中心にして、この近傍を探索する もう改善が出来なくなった所で、やめる。

その時の割り当てを出力する。

※移り方のルールもいろいろあり得る（近傍の中で最も良い

( )

(x₁ +x₂ +x₃ ) ( ) (x₁ x ₂ +x₃ ) ( )x₃ x₂ (x₁ +x₂ +x₃ )

(x ₁ +x₃ ) (x ₂ +x₃ )

0 1 0 x₁ x₂ x₃

4

1 1 0 0 0 0 0 1 1

5 5 6

局所探索法の考え方

解同士の「近傍」を定義する。

ランダムに選んだ初期解から、

近傍の中でより良い解に移る ことを繰り返す。

これ以上移れなくなったら、

その時の解を出力する。

局所探索法で、必ず最適解が求まるとは限らない。

（むしろ一般には求まらない。）

充足される 項の数

出力 本当の最適解

局所探索法の利点：

局所探索法では、近傍の定義の仕方はいろいろある。

例えば極端な話

全てが、お互いに近傍同士と定義しても良い。

必ず最適解にたどりつくが、1回のステップにかかる時間が大きくなる。

MAX CUT

入力：グラフG

出力：Gの頂点集合の2分割

間にある枝数が出来るだけ多くなるように 局所探索法の例をもう1つ

例

4本

問題：最適解は？

MAX CUTに対する局所探索法

近傍：＝1頂点だけを反対側のグループへ移す

例えばこの頂点を 動かすことで、解は 改善する

問題： 局所探索法で最適解が得られないグラフ（と初期解）の例 を与えよ。