C++基础:2-SAT问题

C++基础:2-SAT问题,第1张

C++基础:2-SAT问题 概述

现有一个由 N 个布尔值组成的序列 A ,给出一些限制关系,比如 A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等,要确定A[0⋯N−1]的值,使得其满足所有限制关系。这个称为SAT问题(已确定非2-SAT的SAT问题为NP完全问题),特别的,若每种限制关系中最多只对两个元素进行限制,则称为 2-SAT 问题。

算法

我们可以把每个点拆成两个点,一个代表取值为 true ,另一个代表取值为 false ,对点对进行遍历,如果两个点都没被选,则先假设选 false ,沿边 DFS 对其所有能到达的点都标记为选择,如果染色过程中发现一个点对的两个点都被选了,也就是某个值是 false 会得出这个值为 true,那么就说明假设矛盾,沿路清空标记,然后尝试选 true 进行 DFS,如果再次失败就说明不存在满足所有条件的解。所有点对都有一个点被选了之后,我们就得到了一种整体的选择方式满足所有题目条件。

注意:这里的true和false不是绝对的,要视实际情况而定!比如:妻子(true)&丈夫(false),工作&休假,尽量是对立的!

算法实例

接下来,用一个例子说明算法执行的过程。

我们有 3 个布尔值组成的序列 A ,限制条件为:

A[0] OR A[1]=1A[1] AND A[2]=1

首先我们进行拆点,然后连边,根据第一个限制条件,我们把 A[0] 的 false 和 A[1] 的 true 连起来,把 A[1]的 false 和 A[0]的 true 也连起来,连有向边,因为这两个中只要有一个不是 11,另外一个就必须选 1。根据第二个条件,把 A[1] 的 false 和 A[1] 的 true 连有向边,把 A[2] 的 false 和 A[2] 的 true连有向边,因为只要有一个不是 1,这个等式就不可能成立。那么图会变成这样。

我们从 0 开始,发现 0 的 true 和 false 都没有选,那么先尝试选 false。

从这个点开始沿路进行选择,将 1 选为 true。

这时从 0 的 false 出发的路都选完了。再看 1,1 已经选了 true 就不再搜索这个点对了。再看 2 ,尝试选 false 后,自己的 true 也会被选,说明 2 选 false 不行,那么尝试选 true,发现可以,选择完成。

此时所有点对都有一个被选了,选择成功,我们就得到了一组满足所有限制条件的解。

时间复杂度为 O(VE),空间复杂度为 S(V+E)。

C++ 示例代码
#include 
#include 
using namespace std;
const int MAX_N = 100;  // 点的上限
const int MAX_M = 10000;  // 边的上限
struct edge {
    int v, next;
} E[MAX_M];
int p[MAX_N * 2], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v) {
    e[eid].v = v;
    e[eid].next = p[u];
    p[u] = eid++;
}
int n, m;  // n 表示点数, m 表示边数
bool selected[MAX_N * 2]; // 标记每个点对是否被选,每一点对为2*i和2*i+1
int S[MAX_N * 2]; // 标记此次选择经过的点
int c; // 此次选择的点数
bool dfs(int u) {
    if (selected[u ^ 1]) {
        return false;//和假设矛盾
    }
    if (selected[u]) {
        return true;//和假设一样
    }
    selected[u] = true;
    S[c++] = u;
    for (int i = p[u]; i != -1; i = E[i].next) {
        int v = E[i].v;
        if (!dfs(v)) {
            return false;
        }
    }
    return true;
}
bool Two_SAT(int n) {
    for(int i = 0; i < 2 * n; i += 2) {
        if (!selected[i] && !selected[i + 1]) {
            c = 0;
            if (!dfs(i)) {
                while (c > 0) {
                    selected[S[--c]] = false; // 失败后沿路清空选择
                }
                if (!dfs(i + 1)) {
                    return false;
                }
            }
        }
    }
    return true;
}
int main() {
    init();
    memset(selected,false,sizeof(selected));
    cin>>N>>M;
    for (int i=0;i>k>>x>>y;
        if (k==0){
            insert(2*x,2*x+1);
            insert(2*y,2*y+1);
        }else{
            insert(2*x,2*y+1);
            insert(2*y,2*x+1);
        }
    }
    if (Two_SAT(N)){
        cout<<"YES"< 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5715039.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存