欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

对于《由对称性解2

程序员文章站 2024-04-05 14:01:06
...

问题:微软笔试题——http://hihocoder.com/problemset/problem/1108 最初想法,仍有待验证:http://bbs.bccn.net/thread-441260-1-1.html 最初想法是:只有成对出现的约束,1 2 0,才能够对问题进行限制,对问题结果照成影响,因此只需要考虑成对出现的约束

问题:微软笔试题——http://hihocoder.com/problemset/problem/1108


最初想法,仍有待验证:http://bbs.bccn.net/thread-441260-1-1.html

最初想法是:只有成对出现的约束,1 2 0,才能够对问题进行限制,对问题结果照成影响,因此只需要考虑成对出现的约束。对于成对出现的节点,在构图中有

1 2 1

无向边进行连接,然后检测最终构图中是否存在节点个数为奇数的环,从而得到最后的结果。



解答:http://blog.csdn.net/kk303/article/details/42869039


由对称性解2-sat问题:http://wenku.baidu.com/link?url=G8jqWFFet0uc164GJnXwyCtJRoi0DQH0U1aoDIRdI7sdSS7R7-h6iacr4cENA808XvkbUV7Atj3MZxTP_r4gksh_IwXV1Bn76YRRMTwSIWq



1.问题模型:

存在n组元素

A1 A2 A3 ... An
~A1 ~A2 ~A3
... ~An

规定每组元素中能且仅能选择一个,同时给定m组约束(Ai,Aj),约束也可能是(Ai,~Aj)。一组约束中的两个元素相互冲突,不能同时被选择。


求解是否能在约束限制下,在n组元素中选择出n个元素。若能,进行选择。


2.解法:步骤(1):对每对约束(Ai,Aj)。因为存在关系选择 Ai 则必须选择 ~Aj ,而选择 Aj 则必须选择 ~Ai ,因此在构图( 图的节点个数为2n)时,对于(Ai,~Aj),(Aj,~Ai)添加有向边

步骤(2):在构图中查找极大强连通分量。将强连通分量转化为节点。这个步骤叫做缩图。

步骤(3):查找是否存在(Ai,~Ai)处于同一个强连通分量中,如果存在,问题无解,程序终止。

步骤(4):根据拓扑排序找到一个可行解。