网站建议:179001057@qq.com

由对称性解2-SAT问题

技术2022-05-11  3

由对称性解2-SAT问题 (by 伍昱,03年IOI国家集训队论文ppt) 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对两两不和的代表编号 其中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不可选 8必须选,4、7不可选 5、6可以任选一个 矛盾的情况为: 存在Ai,使得Ai既必须被选又不可选。 得到算法1: 枚举每一对尚未确定的Ai, Ai' ,任选1个,推导出相关的组,若不矛盾,则可 选择;否则选另1个,同样推导。若矛盾,问题必定无解。 此算法正确性简要说明: 由于Ai,Ai' 都是尚未确定的,它们不与之前的组相关联,前面的选择不会影响Ai, Ai'。 算法的时间复杂度在最坏的情况下为O(nm)。 在这个算法中,并没有很好的利用图中边的对称性 上图中1和3构成一个环,这样1和3要么都被选择,要么都不被选。 2和4同样如此。 更一般的说: 在每个一个环里,任意一个点的选择代表将要选择此环里的每一个点。不妨把环 收缩成一个子节点(规定这样的环是极大强连通子图)。新节点的选择表示选择 这个节点所对应的环中的每一个节点。 对于原图中的每条边Ai→Aj(设Ai属于环Si,Aj属于环Sj)如果Si≠Sj, 则在新图中连边:      Si→Sj ╭──╮                                        │     ↓                                        ①      ③     ④ ╭─⑦         (s1)    ④ ╭─⑦ ↑     ││       │               │       │      ╰──╯╰───┼─╮    <=>     ╰───┼─╮ ╭──╮╭───╯   │           ╭───╯   │ │     ↓↓           ↓           ↓           ↓ ②      ④     ⑤      ⑧         (s2)    ⑤      ⑧ ↑     │                                        ╰──╯                                        这样构造出一个新的有向无环图。 此图与原图等价。 通过求强连通分量,可以把图转换成新的有向无环图,在这个基础上,介绍一个 新的算法。 新算法中,如果存在一对Ai, Ai'属于同一个环,则判无解,否则将采用拓扑排序 ,以自底向上的顺序进行推导,一定能找到可行解。 至于这个算法的得来及正确性,将在下一段文字中进行详细分析。 深入分析: 回忆构图的过程: 对于两个不相容的点 Ai, Aj,构图方式为:      Ai→Aj'        Aj→Ai' 前面提到过,这样的两条边对称,也就是说: 如果存在Ai→Aj,必定存在Aj'→Ai' 。 引理:原图具有对称传递性 Ai→Aj→Ak 等价于 Ai→Ak 方便起见,之后“→”代表这样一种传递关系 猜测1:图中的环分别对称 如果存在Ai,Aj,Ai,Aj属于同一个环(记作Si),那么Ai' , Aj' 也必定属于一 个环(记作Si' )。 再根据前面的引理,不难推断出每个环分别对称。 推广1:新图中,同样具有对称传递性。 推广2:对于任意一对Si, Si' ,Si的后代节点与Si' 的前代节点相互对称。 继而提出 猜测2:若问题无解,则必然存在Ai, Ai' ,使得Ai, Ai'   属于同一个环。 也就是,如果每一对Ai,Ai' 都不属于同一个环,问题必定有解。下面给出简略证明: 先提出一个跟算法1相似的步骤: 如果选择Si,那么对于所有Si→Sj,Sj都必须被选择。 而Si' 必定不可选,这样Si’的所有前代节点也必定不可选(将这一过程称之为删除)。 由推广2可以得到,这样的删除不会导致矛盾。 假设选择S3' →选择S3'的后代节点, S1' →删除S3 →删除S3的前代节点S1 S1与S1'是对称的 另外,若每次盲目的去找一个未被确定的Si,时间复杂度相当高。 以自底向上的顺序进行选择、删除,这样还可以免去“选择Si的后代节点”这一步。 用拓扑排序实现自底向上的顺序。 算法2的流程: 1.构图 2.求图的极大强连通子图 3.把每个子图收缩成单个节点,根据原图关系构造一个有向无环图 4.判断是否有解,无解则输出(退出) 5.对新图进行拓扑排序 6.自底向上进行选择、删除 7.输出 小结: 整个算法的时间复杂度大概是O(m),解决此问题可以说是相当有效了。 在整个算法的构造、证明中反复提到了一个词:对称。发现、利用了这个图的特 殊性质,我们才能够很好的解决问题。    并且,由2-SAT问题模型变换出的类似的题目都可以用上述方法解决。 全文总结: 充分挖掘图的性质,能够更好的解决问题。 不仅仅是对于图论,这种思想可以在很多问题中得到很好的应用。 希望我们能掌握此种解题的思想,在熟练基础算法的同时深入分析、灵活运用、 大胆创新,从而解决更多更新的难题。

最新回复(0)