最近算法作业做到了这么个有趣的问题,2-SAT,也就是Satisfiability(适应性问题),连续几个一起来也是喘不过气了orz。问题总体框架大概是这样的,扔一串表达式,例如

\(S = (x_1 \vee \overline{x_2}) \wedge (\overline{x_1} \vee \overline{x_3}) \wedge (x_1 \vee x_2) \wedge (\overline{x_3} \vee x_4) \wedge (\overline{x1} \vee x_4)\) 这种,然后叫你求一个解,使得 \(S\) 为True,也就是每个括号内的表达式中都至少得有一个为True~

问题映射

如何举个例子说明这个问题在现实中的原型?这里就引用POI 0106的题目了:

一国有n个党派,每个党派在议会中都有2个代表,现要组建和平委员会,要从每个党派在议会的代表中选出1人,一共n人组成和平委员会。已知有一些代表之间存在仇恨,也就是说他们不能同时被选为和平委员会的成员,现要你判断满足要求的和平委员会能否创立?如果能,请任意给出一种方案。

也就是说,如果其中党派A中的一个代表与党派B中的一个代表不和,假如分别为A1与B1,那么如果选择A1,就只能选择B2了。类似这个道理。

初步探索

比如我们假设\(x_1\)为True,那么第一个括号里面的表达式中的\(\overline{x_2}\)就可以设置为False了,依次类推,一个个尝试… 如果发生一种情况,即一个变量同时需要为True和False,那么尝试就失败了,需要回滚,是不是有点像DFS?(直觉告诉我或许可以用DFS和Greedy来解决这个问题,但复杂度相对就比较高了,这是不是也提供了k-SAT问题的普通解法呢…乱说的)当然DFS并不优雅,我们还是尽可能尝试找出一个线性时间可以解决的思路,于是我们需要把它转化成一个模型,然后来解决这个问题。

建立成什么模型呢?考虑到\(x_1 \vee x_2\)可以转变为\(\overline{x_1} \rightarrow x_2; \overline{x_2} \rightarrow x_1\) ,也就是说如果\(x_1\)为False,那么\(x_2\)就被迫为True;反之亦然。所以可以看成变量之间的推导关系。

现在有了各个变量和各个变量之间的二元关系,不难(好难)把这个问题映射为一个有向图问题。每个变量和它的取反可以看成图的顶点,变量之间的推导关系可以看成图中的边。

一个思考方向

那怎么用有向图去解决这个问题呢?

先不要硬着头皮想这个问题。

考虑一个情况,如果图中代表一个变量及其取反的两个顶点(比如\(x_1\)和\(\overline{x_1}\)),满足什么情况的时候,就发生了两个都得为True而矛盾的情况呢?答案是这两个顶点互相可达的时候,比如\(\overline{x_1} \rightarrow x_1; {x_1} \rightarrow \overline{x_1}\),那么可以得出\((x_1 \vee x_1) \wedge (\overline{x_1} \vee \overline{x_1})\)必须为True,也就是两个变量都得为True,从而发生了矛盾的情形。

那…怎么判断这两个变量相互可达?

想到了强连通分量(在一个强连通分量里面任意两个点互相可达)。如果有两个这样的变量代表的点在同一个强连通分量里边,这整个式子就不可能成立了,也就是无解。建图和求SCC都不是大问题。

问题是,如果没有发生这种矛盾的情况,就一定有解了吗,如果有,该怎么求出来呢?只要我们针对这么一个图,能构造出一个解出来,那么证明也就迎刃而解了(构造性证明)。

求解思路

依照上面的讨论,假设由原来的式子构造出来的有向图为\(G\),如果我们选择了图里面一个SCC其中的一个变量\(x_i\),那么该SCC中的其他全部变量也必须被选择(因为\(x_i\)可以到达)。如果没有产生上述的矛盾,我们可以把处于同一个强连通分量中的点和边缩成一个点(它们属于一个等价类),得到新的图\(G’\)。由于我们已经对图进行了收缩,那么\(G’\)必定是一个有向无环图(DAG)。

然后我们把图\(G’\)中的边都反过来,得到图\(G’’\)。为什么要反过来?

这是因为我们要传递的不是“选择”关系,而是“不选择”关系。为何要这么做?假设有有向图中,有\(a \rightarrow b\) 且有 \(a \rightarrow \overline{b} \) (这是完全有可能的),那么如果选择了\(a\),就必须选择\(b\)和\(\overline{b}\),这就造成矛盾了。

那么传递“不选择”关系又是什么意思?举个例子,比如我们选择了一个强连通分量\(S_1\)里面的\(x_1\),那么另一个强连通分量\(S_2\)里的\(\overline{x_1}\)就不能被选择了。然后,所有指向\(\overline{x_1}\)的边中对面的顶点也得被放弃了(想想为什么?)所以我们必须在放弃某个点之后,立即放弃连向它的所有顶点,依次传递。为了实现这个目标,我们就得把图反过来,才能较好的去完成这个“反向传递”。

然后…知道了以上的这些,怎么开始解决这个问题呢?

0、我们可以把最原始的图\(G’’\)中的每个顶点都标记为“未染色”状态

1、选择一个未着色的顶点\(x\),将它染成红色

2、把所有与顶点\(x\)矛盾的顶点\(y\)(只要顶点\(y\)中含有与顶点\(x\)中某个变量相反的变量)及其子孙染成蓝色

3、重复操作1和2,直到不存在未染色的顶点为止。此时,\(G’’\)中被染色红色的顶点在图\(G\)中所对应的顶点集合,就对应了该2-SAT问题的一组解

从上面的算法描述中,我们可以知道以上的操作是不会产生矛盾的情况的,即一个顶点与它的相反顶点不会都被染成红色。

那有没有可能两个都被染成蓝色呢?这个问题相应的证明极为精妙。我也理解了挺久_(:з」∠)_

看看参考的PDF吧~

其他

于是这个问题就说这么多啦,只是作业做到了感觉挺有趣。现在写博客总感觉文字很生硬重复,也不知道会不会慢慢变好。

其实2-SAT问题是k-SAT问题的一种特殊情况,但k-SAT问题现在还不在讨论的level,就不展开了,有兴趣的同学可以去看看。

参考来源