問題タブ [2-satisfiability]

2-SAT問題の延長である問題があります。標準の2-SAT問題では、選択した頂点の順序に依存する真理の割り当てを見つけることができます。式が充足可能な真理代入が1つだけ（つまり、組み合わせが1つだけ）存在するかどうかを確認したいと思います。リテラルの数は100000にすることができます。1つの方法は、考えられるすべての真理の割り当てを見つけて、それらが異なる場合はそれらを比較することです。しかし、問題は比較ごとにあり、100000個の値（リテラルなし）を比較する必要があります。効率的な方法はありますか？

100000 個のリテラルに対して 2-SAT 問題を実装したいと考えています。したがって、頂点の数は 200000 になります。したがって、各頂点から到達可能なすべての頂点の配列を持つことに固執しています。その空間の複雑さ O(200000^2)は実行不可能です。したがって、これに対する解決策を提案してください。そして、2-SAT問題の効率的な実装に光を当ててください。

私は2充足可能性問題のSATソルバーを作成しました。誰かが、充足可能な割り当てが1つだけ、つまりソリューションが1つしかない10000リテラルのテストケースを提供してください。

しばらく探していましたが、2-Satアルゴリズムの実装が見つからないようです。

私はブーストライブラリ（強力に接続されたコンポーネントモジュールを持っています）を使用してC ++で作業しており、効率的な2-Satプログラムを作成するか、c++で利用できる既存のライブラリを見つけるためのガイダンスが必要です。

2-Satのアルゴリズムを検索するたびに、問題の決定形式のアルゴリズムが返されます。すべての句を満たす有効な値のセットが存在しますか。ただし、それでは満足のいくブール値のセットを簡単に見つけることができません。

2-Satインスタンスを満たす正当な値のセットを効率的に見つけるにはどうすればよいですか？

私はブーストライブラリを使用してC++で作業していますが、簡単に統合できるコードをいただければ幸いです。

前もって感謝します

私は現在、試験のために2SATの問題を研究していますが、力ずくで解決策が存在するかどうかを確認する方法がよくわかりません。これは少し奇妙に思えますが、含意グラフをもう少しうまく実装する方法は理解していますが、ブルートフォース戦略を実装する方法がよくわかりません。

誰かがいくつかの洞察を共有できますか？たぶん擬似コードかJavaで。

ありがとう

次のコードを使用しています。

出力は次のとおりです。この例をここでオンラインで実行します

この例では、行列 M は 2-SAT インスタンスを CNF (参照) として定義します。この例では、行列 M が手動で入力として導入されました。行列 M を自動的に導入する方法を教えてください ( matrix )。どうもありがとう。

問題が多項式時間で解ける場合、Digraph に強結合コンポーネントを適用すると、 2-SAT ブール値の充足可能性を確認できることがわかっています。

問題が充足可能であると仮定しましょう。

質問: 2-SAT に依存してその解を計算するための一般的なアルゴリズムはありますか?

u -> v含意グラフは、各ノードに true または false のいずれかが割り当てられ、任意のエッジがそれを意味する有向グラフですif u is true then v is true。

O(n^2)一般的な含意グラフで割り当てを見つける簡単なアルゴリズムと、いくつかの特殊なケース ( 2-SAT問題O(n)から生じる含意グラフなど) のアルゴリズムを知っています。

O(n)それで、含意グラフの割り当てを見つけるアルゴリズムがあるかどうか疑問に思っていましたか？