【2017年整理】由对称性解2-SAT问题(伍昱).pptVIP

由对称性解2-SAT问题;2-SAT:;Poi 0106 Peaceful Commission [和平委员会];输入n（党派数），m（不友好对数）及m对两两不和的代表编号 其中1≤n≤8000，0≤m ≤20000 ;分析：;初步构图;假设4个组，不和的代表为：1和4，2和3，7和3，那么构图：;矛盾的情况为： 存在Ai，使得Ai既必须被选又不可选。 ;此算法正确性简要说明： 由于Ai,Ai 都是尚未确定的，它们不与之前的组相关联，前面的选择不会影响Ai, Ai 。 ;先看这样一个结构： ;对于原图中的每条边Ai Aj（设Ai属于环Si，Aj属于环Sj）如果Si≠Sj，则在新图中连边： Si Sj;通过求强连通分量，可以把图转换成新的有向无环图，在这个基础上，介绍一个新的算法。 新算法中，如果存在一对Ai, Ai属于同一个环，则判无解，否则将采用拓扑排序，以自底向上的顺序进行推导，一定能找到可行解。 至于这个算法的得来及正确???，将在下一段文字中进行详细分析。;深入分析：;引理：原图具有对称传递性;猜测1：图中的环分别对称;推广1：新图中，同样具有对称传递性。;分开来看，更加一般的情况，即下图： （说明：此图中Si有可能为Si的后代节点） ;于是可以得到 推广2：对于任意一对Si, Si ，Si的后代节点与Si 的前代节点相互对称。 ;先提出一个跟算法1相似的步骤： 如果选择Si，那么对于所有Si Sj，Sj都必须被选择。 而Si 必定不可选，这样Si’的所有前代节点也必定不可选（将这一过程称之为删除）。 由推广2可以得到，这样的删除不会导致矛盾。;每次找到一个未被确定的Si，使得不存在Si Si 选择Si及其后代节点而删除Si’及Si‘的前代节点。 一定可以构造出一组可行解。 因此猜测2成立。;另外，若每次盲目的去找一个未被确定的Si，时间复杂度相当高。 以自底向上的顺序进行选择、删除，这样还可以免去“选择Si的后代节点”这一步。 用拓扑排序实现自底向上的顺序。;算法2的流程： ;小结：;全文总结：