由对称性解2-SAT问题概要.ppt

由对称性解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个党派 /dx / /dx/150910/4694207.html /dx/151205/4738748.html /dx/151205/4738750.html /dx/151205/4738751.html /dx/150910/4694176.html /dx/150907/4692216.html /dx/150905/4691645.html /dx/150902/4691147.html /dx/151207/4739192.html /dx/151207/4739197.html /dx/151207/4739201.html /dx/151207/4739215.html /dx/150902/4691141.html /dx/151208/4740618.html /dx/151208/4740619.html /dx/151209/4741159.html /dx/151209/4741163.html /dx/151209/4741170.html /dx/151209/4741172.html /dx/151210/4741687.html 输入n（党派数），m（不友好对数）及m对两两不和的代表编号 其中1≤n≤8000，0≤m ≤20000 求和平委员会是否能创立。 若能，求一种构成方式。 例：输入：3 2 输出：1 1 3 4 2 4 5 分析： 原题可描述为： 有n个组，第i个组里有两个节点Ai, Ai 。需要从每个组中选出一个。而某些点不可以同时选出（称之为不相容）。任务是保证选出的n个点都能两两相容。 （在这里把Ai, Ai 的定义稍稍放宽一些，它们同时表示属于同一个组的两个节点。也就是说，如果我们描述Ai，那么描述这个组的另一个节点就可以用Ai） 初步构图 如果Ai与Aj不相容，那么如果选择了Ai，必须选择Aj‘ ；同样，如果选择了Aj，就必须选择Ai’ 。 Ai Aj Aj Ai‘ 这样的两条边对称 我们从一个例子来看： 假设4个组，不和的代表为：1和4，2和3，7和3，那么构图： 1 3 2 4 5 6 7 8 假设： 首先选1 ?3必须选，2不可选 ?8必须选，4、7不可选 5、6可以任选一个 矛盾的情况为： 存在Ai，使得Ai既必须被选又不可选。 得到算法1： 枚举每一对尚未确定的Ai, Ai‘ ，任选1个，推导出相关的组，若不矛盾，则可选择；否则选另1个，同样推导。若矛盾，问题必定无解。 1 3 2 4 5 6 7 8 此算法正确性简要说明： 由于Ai,Ai 都是尚未确定的，它们不与之前的组相关联，前面的选择不会影响Ai, Ai 。 算法的时间复杂度在最坏的情况下为O(nm)。 在这个算法中，并没有很好的利用图中边的对称性 先看这样一个结构： 更一般的说： 在每个一个环里，任意一个点的选择代表将要选择此环里的每一个点。不妨把环收缩成一个子节点（规定这样的环是极大强连通子图）。新节点的选择表示选择这个节点所对应的环中的每一个节点。 此图中1和3构成一个环，这样1和3要么都被选择，要么都不被选。 2和4同样如此。 图的收缩 1 3 2 4 5 6 7 8 对于原图中的每条边Ai Aj（设Ai属于环Si，Aj属于环Sj）如果Si≠Sj，则在新图中连边： Si Sj 这样构造出一个新的有向无环图。 此图与原图等价。 1 3 2 4 5 6 7 8 S1 S1 S2 S2 S3 S3 图的收缩 通过求强连通分量，可以把图转换成新的有向无环图，在这个基础上，介绍一个新的算法。 新算法中，如果存