Div*_*ood 44
如果你有n个变量和m个子句:
创建一个包含2n个顶点的图形:直观地说,每个顶点类似于每个变量的真实或非真实文字.对于每个子句(avb),其中a和b是文字,从!a到b和从!b到a创建边.这些边缘意味着如果a不为真,则b必须为真,反之亦然.
一旦创建了这个有向图,就可以浏览图表,看看是否有一个循环包含一个和一个变量a的a.如果有,则2SAT不可满足(因为暗示!a和反之亦然).否则,它是令人满意的,这甚至可以给你一个令人满意的假设(选择一些文字a,这样一个并不意味着!a,强制从那里产生所有影响,重复).您可以使用任何标准图算法,ala 广度优先搜索,Floyd-Warshall或任何类似算法执行此操作,具体取决于您对算法时间复杂度的敏感程度.
这是关于该主题的维基百科页面,其描述了多项式时间算法.(只是尝试所有不同的真值分配的强力算法是指数时间.)也许一些进一步的解释将有所帮助.
当P为真且Q为假时,表达"if P then Q"仅为假.因此表达式具有与"Q或不P"相同的真值表值.它也相当于它的对立面,"如果不是Q则不是P",而这相当于"非P或Q"(与另一个相同).
因此,该算法涉及用两个表达式替换"A或B"形式的每个表达式,"如果不是A则B"和"如果不是B然后A".(换句话说,A和B不能都是假的.)
接下来,构建一个表示这些含义的图表.为每个"A"和"非A"创建节点,并为上面获得的每个含义添加链接.
最后一步是确保所有变量都不等同于它自己的否定.也就是说,对于每个变量A(或不是A),请按照链接发现可以从中获取的所有节点,注意检测循环.
如果其中一个变量A可以达到"非A",而"非A"也可以达到A,则原始表达式不可满足.(这是一个悖论.)如果没有变量这样做,那么它是可以满足的.
(如果A暗示"不是A",那就没关系,但不是相反.这只是意味着A必须被否定才能满足表达式.)