算法学习：图论之2-SAT

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,由对称性解,2-SAT,问题,伍昱,2-SAT:,2-SAT,就是,2,判定性问题，是一种特殊的逻辑判定问题。,2-SAT,问题有何特殊性？该如何求解？,我们从一道例题来认识,2-SAT,问题，并提出对一类,2-SAT,问题通用的解法。,Poi 0106 Peaceful Commission,和平委员会,某国有,n,个党派，每个党派在议会中恰有,2,个代表。,现在要成立和平委员会，该会满足：,每个党派在和平委员会中有且只有一个代表,如果某两个代表不和，则他们不能都属于委员会,代表的编号从,1,到,2n,，编号为,2a-1,、,2a,的代表属于第,a,个党派,输入,n,（,党派数），,m,（,不友好对数）及,m,对两两不和的代表编号,其中,1n8000,，,0m 20000,求和平委员会是否能创立。,若能，求一种构成方式。,例：输入：,3 2,输出：,1,1 3 4,2 4 5,分析：,原题可描述为：,有,n,个组，第,i,个组里有两个节点,A,i,A,i,。,需要从每个组中选出一个。而某些点不可以同时选出（称之为不相容）。任务是保证选出的,n,个点都能两两相容。,（在这里把,A,i,A,i,的定义稍稍放宽一些，它们同时表示属于同一个组的两个节点。也就是说，如果我们描述,A,i,，,那么描述这个组的另一个节点就可以用,A,i,）,初步构图,如果,A,i,与,A,j,不相容，那么如果选择了,A,i,，,必须选择,A,j,；,同样，如果选择了,A,j,，,就必须选择,A,i,。,A,i,A,j,A,j,A,i,这样的两条边,对称,我们从一个例子来看：,假设,4,个组，不和的代表为：,1,和,4,，,2,和,3,，,7,和,3,，那么构图：,1,3,2,4,5,6,7,8,假设：,首先选,1,3,必须选，,2,不可选,8,必须选，,4,、,7,不可选,5,、,6,可以任选一个,矛盾,的情况为：,存在,A,i,，,使得,A,i,既必须被选又不可选。,得到,算法,1,：,枚举每一对尚未确定的,A,i,A,i,，,任选,1,个，推导出相关的组，若不矛盾，则可选择；否则选另,1,个，同样推导。若矛盾，问题必定无解。,1,3,2,4,5,6,7,8,此算法正确性简要说明：,由于,A,i,A,i,都是尚未确定的，它们不与之前的组相关联，前面的选择不会影响,A,i,A,i,。,算法的时间复杂度在最坏的情况下为,O(nm,),。,在这个算法中，并没有很好的利用图中边的,对称,性,先看这样一个结构：,更一般的说：,在每个一个环里，任意一个点的选择代表将要选择此环里的每一个点。不妨把环收缩成一个子节点（规定这样的环是,极大强连通子图,）。新节点的选择表示选择这个节点所对应的环中的每一个节点。,此图中,1,和,3,构成一个,环,，这样,1,和,3,要么都被选择，要么都不被选。,2,和,4,同样如此。,图的,收缩,1,3,2,4,5,6,7,8,对于原图中的每条边,A,i,A,j,（设,A,i,属于环,S,i,，,A,j,属于,环,S,j,）,如果,S,i,S,j,，,则,在新图中连边：,S,i,S,j,这样构造出一个新的,有向无环图。,此图与原图,等价,。,1,3,2,4,5,6,7,8,S,1,S,1,S,2,S,2,S,3,S,3,图的,收缩,通过求强连通分量，可以把图转换成新的有向无环图，在这个基础上，介绍一个新的算法。,新算法中，如果存在一对,A,i,A,i,属于同一个环，则判无解，否则将采用拓扑排序，以自底向上的顺序进行推导，一定能找到可行解。,至于这个算法的得来及正确性，将在下一段文字中进行详细分析。,新算法的提出,深入分析：,回忆构图的过程：,对于两个不相容的点,A,i,A,j,，,构图方式为：,A,i,A,j,A,j,A,i,前面提到过，这样的两条边,对称,，也就是说：,如果存在,A,i,A,j,，,必定存在,A,j,A,i,。,1,3,2,4,5,6,7,8,引理：原图具有,对称,传递性,等价于：,A,i,A,k,A,k,A,i,方便起见，之后“”代表这样一种传递关系,A,i,A,k,A,j,A,i,A,k,A,j,猜测,1,：图中的环分别,对称,如果存在,A,i,A,j,，,A,i,A,j,属于同一个环（记作,S,i,），,那么,A,i,A,j,也必定属于一个环（记作,S,i,）。,再根据前面的引理，不难推断出每个环分别对称。,A,i,A,j,A,i,A,j,1,3,2,4,5,6,7,8,推广,1,：新图中，同样具有,对称,传递性。,S,1,S,1,S,2,S,2,S,3,S,3,一个稍稍复杂点的结构,其中红、蓝色部分分别为两组,对称,的链结构,证明方式与引理相类似,S,1,S,1,S,2,S,2,S,3,S,3,分开来看，更加一般的情况，即下图：,（说明：此图中,S,i,有可能为,S,i,的后代节点）,于是可以得到,推广,2,：对于任意一对,S,i,S,i,，,S,i,的后代节点与,S,i,的前代节点相互,对称,。,继而提出,猜测,2,：若问题无解，则必然存在,A,i,A,i,，,使得,A,i,A,i,属于同一个环。,也就是，如果每一对,A,i,A,i,都不属于同一个环，问题必定有解。下面给出简略证明：,问题的关键,先提出一个跟,算法,1,相似的步骤：,如果选择,S,i,，,那么对于所有,S,i,S,j,，,S,j,都必须被选择。,而,S,i,必定不可选，这样,S,i,的所有前代节点也必定不可选（将这一过程称之为,删除,）。,由,推广,2,可以得到，这样的删除不会导致矛盾。,对称性的利用,每次找到一个未被确定的,S,i,，,使得不存在,S,i,S,i,选择,S,i,及其后代节点而删除,S,i,及,S,i,的前代节点。,一定可以构造出一组可行解。,因此,猜测,2,成立。,S,1,S,1,S,2,S,2,S,3,S,3,假设选择,S,3,选择,S,3,的后代节点,S,1,删除,S,3,删除,S,3,的前代节点,S,1,S,1,与,S,1,是,对称,的,另外，若每次盲目的去找一个未被确定的,S,i,，,时间复杂度相当高。,以,自底向上,的顺序进行选择、删除，这样还可以免去“,选择,S,i,的后代节点,”,这一步。,用,拓扑排序,实现自底向上的顺序。,S,1,S,1,S,2,S,2,S,3,S,3,一组可能的拓扑序列,(,自底向上）,S,1,S,2,S,2,S,3,S,3,S,1,算法,2,的流程：,1,构图,2,求图的极大强连通子图,3,把每个子图收缩成单个节点，根据原图关系构造一个有向无环图,4,判断是否有解，无解则输出（退出）,5,对新图进行拓扑排序,6,自底向上进行选择、删除,7,输出,小结：,整个算法的时间复杂度大概是,O(m),，,解决此问题可以说是相当有效了。,在整个算法的构造、证明中反复提到了一个词：,对称,。发现、利用了这个图的特殊性质，我们才能够很好的解决问题。,并且，由,2-SAT,问题模型变换出的类似的题目都可以用上述方法解决。,全文总结：,充分挖掘图的性质，能够更好的解决问题。,不仅仅是对于图论，这种思想可以在很多问题中得到很好的应用。,希望我们能掌握此种解题的思想，在熟练基础算法的同时深入分析、灵活运用、大胆创新，从而解决更多更新的难题。,