SAT充足解の偏りを利用した局所探索の高速化

スポンサーリンク

概要

論文の詳細を見る
近年、Schoningは3SATに対する最も良い上限、すなわち時間計算量が1.334^nである単純な局所探索アルゴリズムを示した。本稿では充足解にある種の偏りがあり、それについての情報が与えられたときに、アルゴリズムを高速化できることを示す。特に、充足解の0の個数と1の個数が偏っている場合、すなわちp_0nの0とp_1nの1を含む場合、例えばp_0=1/3ならば1.260^nでp_0=0.1ならば1.072^nで解を見つけることができる。そのような偏りは他の問題からSATに還元した例題によく見られる。本稿では具体例として、3次元マッチングから変換した例題に対してこの修正されたアルゴリズムが、総当たりよりも高速に動作することを示した。また、いくつかの実験も行なった。
2001-05-10

著者

関連論文

もっと見る

スポンサーリンク