100000 個のリテラルに対して 2-SAT 問題を実装したいと考えています。したがって、頂点の数は 200000 になります。したがって、各頂点から到達可能なすべての頂点の配列を持つことに固執しています。その空間の複雑さ O(200000^2)は実行不可能です。したがって、これに対する解決策を提案してください。そして、2-SAT問題の効率的な実装に光を当ててください。
1374 次
2 に答える
5
ウィキペディアから：
... 2-充足可能性は多項式時間で解くことができます。Aspvall , Plass & Tarjan (1979)が観察したように、インスタンスのすべての変数が含意グラフの同じ変数の否定とは異なる強連結成分に属している場合にのみ、2-充足可能インスタンスが解ける。深さ優先探索に基づくアルゴリズムによって線形時間で強連結成分を見つけることができるため、同じ線形時間境界が 2-充足可能性にも適用されます。
その段落のほとんどを理解しているふりをするつもりはありませんが、2-SAT 問題を解決するために使用できるアルゴリズムがあり、その参照ドキュメント内で説明されているようです(特定の数量化されたブール式の真実)。オンラインで約 20 米ドルで購入できるようです。参考になるかわかりませんが、参考になりました！
于 2009-11-03T04:34:44.560 に答える
1
このスレッド全体が少しめちゃくちゃです。はい、線形時間で 2-sat を解くことはできますが、いいえ、多くの変数について解くことはできません。2-sat を解く時間は、含意の数に対して線形であり、200,000 変数の場合、最大 (200000*199999)/2 に達する可能性があり、さらに、この解を使用する場合は、ほぼ同じ量のメモリが必要になります。 . 別の解決策があります（低速ですが、それほど多くのメモリを必要としない、強く接続されたコンポーネントを使用しない）。
于 2010-04-12T14:01:13.243 に答える