【算法与数据结构】——2-SAT问题

た入场券 2022-10-16 06:20 147阅读 0赞

## 导引问题 ##

A，B，C三人中有两个女生；  
如果A是男生，那么B一定是女生；  
A和C性别相同；  
求A、B、C三人的性别。

## 2—SAT问题 ##

SAT的全称：satisfiability（可满足性 ）  
有一个有N个布尔值组成的序列A，给出一些限制关系，比如A\[x\]ANDA\[y\]=0、A\[x\] OR A\[y\] OR A\[z\]=1等，要确定A\[0···N-1\]的值，适得其反满足所有限制关系，这就是SAT问题。

特别的，若每种限制关系中最多只对两个元素进行限制，则称为2—SAT问题。

2—SAT问题是有多项式解法的，而3—SAT就是npc问题。

2—SAT问题是要确定N个布尔变量的值，使得其满足所有限制关系。

## 判断是否有解 ##

建立2N个点的有向图，不妨设：i点表示 x i x\_i xi=False  i 1 i^1 i1表示 x i x\_i xi=True

一条u->v的有向边表示如果选择了u，那么一定要选择v。  
2—SAT有解当且仅当对于任意一个i(1<=i<=N)不能出现如下情况：在这个有向图中从i点出发可以到达 i 1 i^1 i1点，且从 i 1 i^1 i1点出发可以到达i点。

由此只需要判断 i 和 i 1 i和i^1 i和i1是否位于同一强连通分量即可！使用Kosaraju算法可以在线性时间内求出强连通分量。

## 输出可行方案 ##

如果从i点出发可以到达 i 1 i^1 i1点，则选了i会导致选 i 1 i^1 i1,矛盾，因此只能选 i 1 i^1 i1

Kosaraju算法在求强连通分量的时候顺带求出了一个遍历顺序q\[1\],q\[2\],…,q\[cnt\]；只需要比较i和 i 1 i^1 i1所属强连通分量在q中位置的前后关系即可构造出可行方案。

## 一元限制的构图方法 ##

限制： x i x\_i xi=True

连边i-> i 1 i^1 i1

表示如果i选了False那么i必须要是true

与i只能选一个True或者False矛盾，强迫i只能是True

## 二元限制的构图方法 ##

一条边u->v的含义：若u则v。

命题"若u则v"的逆否命题为"若非v则非u"

命题与其逆否命题等价。

建图时需要将其逆否命题建图

即u->v同时 v 1 − > u 1 v^1->u^1 v1−>u1

限制u or v=true  
若u为假，则v为真：连边u-> v 1 v^1 v1。  
若v为假，则u为真：连边v-> u 1 u^1 u1。

限制u or v=false  
u为假：连边 u 1 − > u u^1->u u1−>u。  
v为假，连边 v 1 − > v v^1->v v1−>v。

限制u and v=false  
若u为真，则v为假：连边 u 1 u^1 u1\->v。  
若v为真，则u为假：连边 v 1 v^1 v1\->u。

限制u and v=true  
u为真，连边 u − > u 1 u->u^1 u−>u1。  
v为真，连边 v − > v 1 v->v^1 v−>v1。

限制u ！= v  
若u为真，则v为假：连边 u 1 u^1 u1\->v。  
若u为假，则v为真：连边 u − > v 1 u->v^1 u−>v1  
若v为真，则u为假：连边 v 1 v^1 v1\->u。  
若v为假，则u为真：连边 v − > u 1 v->u^1 v−>u1

限制 u==v  
若u为真，则v为真：连边 u 1 u^1 u1\-> v 1 v^1 v1。  
若u为假，则v为假：连边 u − > v u->v u−>v  
若v为真，则u为真：连边 v 1 v^1 v1\-> u 1 u^1 u1。  
若v为假，则u为假：连边 v − > u v->u v−>u