next up previous
: VLSIレイアウト問題(minimum cut linear arrangement問題) : 近似アルゴリズムでよく取り扱われる問題(代表的なものの一部) : 最大クリーク問題(MAX-CLIQUE)

最大充足割当問題(MAX-SAT)

論理式Fが入力として与えられ, なるべく多くの節を真にしたい.最大幾つの節を真にできるか? 例えば, 論理式が以下のような場合,

(x1 ∨ ¬x2 ∨ x5) ∧ (¬x1 ∨ x3 ∨ x4) ∧ (¬x1 ∨ ¬x3 ∨ x5) ∧ (¬x2 ∨ x3 ∨ ¬x4) ∧ (¬x2 ∨ ¬x4 ∨ ¬x5) ∧ (¬x1 ∨ x4 ∨ ¬x5) ∧ (x2 ∨ ¬x3 ∨ ¬x5)

x1=1, x2=1, x3=1, x4=0, x5=1 の割当では真,真,真,真,真,偽,真となり

x1=0, x2=0, x3=0, x4=0, x5=0 の割当では真,真,真,真,真,真,真となる。



Koichi Yamazaki 平成12年3月15日