MAX SAT に対する近似アルゴリズムの研究

MAX SAT に対する
近似アルゴリズムの研究
中央大学大学院情報工学専攻
浅野研究室
堀邦彰
MAX SAT とは…
入力: 重み付きクローズの集合
出力: 満たされているクローズの
重みの和が最大となるような
真偽割り当て
各クローズが高々2個のリテラルしか
持たない場合でかつ重みが同一の場合に
おいてもNP‐hard であることが知られている.
したがって MAX SAT も NP‐hard である.
近似アルゴリズム
具体例
1つ１つが
重み付きクローズ
入力:
{( x1 , 4) , ( x 2 , 2) , ( x 3 , 6) , ( x 1∨ x2 ,8) ,
( x2∨ x3 , 2) , ( x1∨ x2∨ 3x, 6) }
真偽割り当て得られる重み
18
( x1 , x 2 , x 3) = ( T , F , F)
20
( T , T , F)
出力
( F , T , F)
22
α‐近似アルゴリズムとは
x* を最適解, F(x) を得られる重みの和と
したときに
F ( x)

(0    1)
F ( x*)
となるような真偽割り当て x を求める
多項式時間アルゴリズム
どんな入力に
対しても
近似率αは理論的
性能指標といえる
近似アルゴリズムの
代表的な手法

確率的方法
{T, F}の真偽割り当てを行なうのではなく,真に
なる確率を変数に割り当てその期待値を見積も
るといった方法
Johnson,Yannakakis,Goemans-Williamson(a)

Semidefinite Programming を用いた方法
Goemans-Williamson によって提案された手法
Goemans-Williamson(b), Asano ら
種々の近似アルゴリズム
近似率







Johnson ’74
Yannakakis ’92
Goemans-Williamson (a) ’94
Goemans-Williamson (b) ’95
Asano-Ono-Hirata ’96
Asano-Hori-Ono-Hirata ’96
Asano ’97
α=0.5
α=0.75
α=0.75
α=0.7584
α=0.765
α=0.767
α=0.770
アルゴリズムの比較の重要性
近似率が良い
計算時間は
よいアルゴリズム
平均的にはどれがいい
様々な入力のもとに様々なアル
ゴリズムで実験する必要がある
行なった研究概要

Goemans-Williamson(a),Yannakakis のアル
ゴリズムの詳細検討．
Yannakakisのアルゴリズムはかなり複雑
昨年のアルゴリズム研究会で発表を行なった．
その際のメインはYannakakisのアルゴリズムの
改良及びその検討．

現在, Semidefinite programming を研究中．
 Semidefinite programming 問題への定式化の
方法及び Semidefinite programming 問題自体
の解法を研究．
Goemans-Williamson (a)の
アルゴリズム
MAX SATを整数線形計画問題として定式
(p1,p2,p3,...,pn)=(1/2,1/2,1/2,...,1/2)
=( x1 ,1/2,1/2,...,1/2)
化し，線形計画問題に緩和．その問題を解
x1 , x2 ,1/2,...,1/2)
き，random rounding=(技法によって真偽割
：
り当てを求める． =( x , x , x ,..., x )
1
2
3 = y
n
Pr(x
i=T)
i
m
max
w z
j
j
j 1
各変数が真になる確率を
1/2 とし，そこか
s.t.
ら真偽割り当てを求める．
 yi   (1  yi )  z j (j )
iC j
iC j
y i , z j  {0,1}
(i and j )
求められた2つの割り当ての良い方を選ぶ
0  yi , z j  1
今後の予定

Yannakakis のアルゴリズムを計算機上で
実現するため，制約付き最大流問題の解
き方を研究する．

最終的には種々のアルゴリズムをプログラ
ム化し，計算機実験により実際的性能の
比較を行なう．

Download Report