2-Satのアルゴリズムを検索するたびに、問題の決定形式のアルゴリズムが返されます。すべての句を満たす有効な値のセットが存在しますか。ただし、それでは満足のいくブール値のセットを簡単に見つけることができません。
2-Satインスタンスを満たす正当な値のセットを効率的に見つけるにはどうすればよいですか？
私はブーストライブラリを使用してC++で作業していますが、簡単に統合できるコードをいただければ幸いです。
前もって感謝します
2444 次
2 に答える
1
2-SATへの有効な割り当てが存在するかどうかを検出するための決定アルゴリズムがある場合は、それを使用して実際の割り当てを実際に見つけることができます。
最初に、式全体に対して2-SAT決定アルゴリズムを実行します。有効な割り当てがあると言っていると仮定します。
ここで、x_1がリテラルの場合、x_1を0に割り当てます。次に、結果の式の2-SATを計算します（このため、他のリテラルを割り当てる必要があります。たとえば、x_1またはx_3が表示される場合は、x_3も設定する必要があります。 1）に。
結果の式が2-Satisfiableの場合、x_1を0にするか、x_1を1にすることができます。
これで、各リテラルについてこれを見つけることができます。
より効率的なアルゴリズムについては、含意グラフアプローチを使用してみることをお勧めします。
あなたはここでより多くの情報を見つけることができます：http：//en.wikipedia.org/wiki/2-satisfiability
関連する部分：
2満足度インスタンスは、インスタンスのすべての変数が、同じ変数の否定とは異なる強連結成分に属している場合にのみ解決可能です。深さ優先探索に基づくアルゴリズムにより、強連結成分が線形時間で検出される可能性があるため、同じ線形時間範囲が2満足度にも適用されます。
強く連結された各コンポーネントのリテラルは、すべてゼロまたはすべて1です。
于 2010-02-22T17:03:36.827 に答える
0
Tomas Federによる2sat問題のすべての解決策をリストするアルゴリズムが少なくとも1つあります：http ：//www.springerlink.com/content/j582276p06276l12/
于 2010-02-22T17:01:49.307 に答える