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