由对称性解2-SAT问题.PPT
《由对称性解2-SAT问题.PPT》由会员分享,可在线阅读,更多相关《由对称性解2-SAT问题.PPT(24页珍藏版)》请在三一文库上搜索。
1、由对称性解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 2
2、0000,求和平委员会是否能创立。 若能,求一种构成方式。,例:输入: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 这样的两条边对称,我们从一个例子
3、来看:,假设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)。 在这个算法中,并没有很
4、好的利用图中边的对称性,先看这样一个结构:,更一般的说: 在每个一个环里,任意一个点的选择代表将要选择此环里的每一个点。不妨把环收缩成一个子节点(规定这样的环是极大强连通子图)。新节点的选择表示选择这个节点所对应的环中的每一个节点。,此图中1和3构成一个环,这样1和3要么都被选择,要么都不被选。 2和4同样如此。,图的收缩,对于原图中的每条边Ai Aj(设Ai属于环Si,Aj属于环Sj)如果SiSj,则在新图中连边: Si Sj,这样构造出一个新的有向无环图。 此图与原图等价。,图的收缩,通过求强连通分量,可以把图转换成新的有向无环图,在这个基础上,介绍一个新的算法。 新算法中,如果存在一对A
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对称性 SAT 问题
链接地址:https://www.31doc.com/p-2665745.html