充足可能性問題 (2-SAT)

概要

2-SAT問題を解く。

連言標準形(CNF)形式の論理式をグラフに変換し、強連結成分分解(SCC)を行うことで充足可能性の判定を行う。

グラフの構築

\(N\) 個の論理変数 \(x_1, ..., x_N\) を含む論理式について各変数ごとに \(x_i\) と \(\lnot x_i\) を表す \(2\) 個の頂点、全体で \(2N\) 個の頂点を用意する。

論理和 \((a \lor b)\) を \((\lnot a \Rightarrow b) \land (\lnot b \Rightarrow a)\) と考え、 \(\lnot a\) から \(b\) への辺 と \(\lnot b\) から \(a\) への辺 を追加する。

この \(v_0\) から \(v_1\) への辺は、 \(v_0\) が真の場合に \(v_1\) も真にする必要があることを表す。

充足可能性の判定

構築したグラフのSCCを求め、各変数 \(x_i\) と \(\lnot x_i\) が同じ強連結成分に含まれていないかを判定する。

論理式を満たす割り当て

強連結成分ごとのトポロジカル順序をもとに論理式が真になる時の各変数の割り当てを決定できる。

トポロジカル順序で \(\lnot x_i\) が \(x_i\) より先にくる場合は \(x_i\) を真、それ以外の場合は偽を割り当てる。

計算量

論理変数の数を \(N\), 節の数を \(M\) とした場合 \(O(N + M)\)

実装

from collections import deque

def scc(N, G, RG):
    order = []
    used = [0]*N
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    for i in range(N):
        if not used[i]:
            dfs(i)
    group = [-1]*N
    label = 0
    order.reverse()
    for s in order:
        if group[s] != -1:
            continue
        que = deque([s])
        group[s] = label
        while que:
            v = que.popleft()
            for w in RG[v]:
                if group[w] != -1:
                    continue
                que.append(w)
                group[w] = label
        label += 1
    return group # topological ordering

N = ...
G = [[] for i in range(2*N)]
RG = [[] for i in range(2*N)]
# add (a ∨ b)
# a =  x_i if neg_i = 0
# a = ~x_i if neg_i = 1
def add_edge(i, neg_i, j, neg_j):
    if neg_i:
        i0 = i+N; i1 = i
    else:
        i0 = i; i1 = i+N
    if neg_j:
        j0 = j+N; j1 = j
    else:
        j0 = j; j1 = j+N
    # add (~a ⇒ b)
    G[i1].append(j0); RG[j0].append(i1)
    # add (~b ⇒ a)
    G[j1].append(i0); RG[i0].append(j1)

group = scc(2*N, G, RG)

# check if the formula is satisfiable
def check(group):
    for i in range(N):
        if group[i] == group[i+N]:
            return False
    return True

# assign values to variables
def assign(group):
    res = [0]*N
    for i in range(N):
        if group[i] > group[i+N]:
            res[i] = 1
    return res

Verified

  • yukicoder: "No.274 The Wall": source (Python3, 653ms)

参考

  • 秋葉拓哉, 岩田陽一, and 北川宜稔. "プログラミングコンテストチャレンジブック." (2010).

戻る