我想为100000个文字实现2-SAT问题.所以会有200000个顶点.所以我坚持从每个顶点获得所有可到达顶点的数组,其空间复杂度 O(200000^2)是不可行的所以请为此提出一个解决方案.请详细说明有效实施2-SAT问题.
我读了许多用于找到2-SAT问题的算法,即给定表达式是否可满足,可以在多项式时间内求解.例子(算法).
对于Krom的程序(维基百科),我构建了图,我可以从中轻松验证其在多项式时间内的可满足性.
现在,我想找到这个表达式的解决方案是可以满足的.
我这样想(验证它):首先我采用形成强连通分量的任何字面表示x,并将值赋值为0.然后根据算法,存在edge(x! - > y).因此y不能为0.(因为1 - > 0是假的)并且如果可能的话同样地进行.
否则取x = 0,然后只选择y = 1,同样继续获得任何可满足的实例.
现在,是在多项式时间内找到任何一个的任何可行解决方案
对于这类问题,我没有得到任何多项式算法.