2-SATと強連結成分分解 - naoya_t@hatenablog
ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。（ちなみにSRM464には出場している） SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみのあれです (x_0 ∨ ¬x_1) ∧ (¬x_0 ∨ ¬x_3) ∧ ... みたいな論理式（乗法標準形）を満たす真偽値 x_0, x_1, ... の組み合わせが存在するか否か。（存在する場合、その組み合わせを知りたかったりする） 上の例ではすべての節が(高々)2変数なので2-SATと呼ばれる。 （2-SATは線形時間で解けるらしい）。 論理和 x ∨ y が論理包含 ¬x⇒y （または ¬y⇒x）に書き換え可能なことを利用して、論理式を有向グラフに変換してみたり 出来上がっ
強連結成分分解 - Win The Game
蝶本, Tips 強連結成分有向グラフにおいて、頂点の部分集合Sが「任意の２頂点u,vをとったとき、uからvへ到達できる」とき、Sは強連結であるという。 頂点の強連結な集合Sに、他のどの頂点集合を付け加えても強連結にできないとき、Sを強連結成分(SCC:Strongly Connected Component)という。 また、任意の有向グラフはいくつかの強連結成分の、共通部分を持たない和集合に分解することができる。 強連結成分分解任意の有向グラフをいくつかの強連結成分の、共通部分を持たない和集合に分解すること。 強連結成分を１つの頂点につぶすｋとで、DAG(閉路をもたない有向グラフ)になる。 強連結成分分解は２回の簡単なDFSで行うことができる。 １回目のDFSでは、適当な頂点からはじめ、まだ通っていない頂点を帰りがけの順で番号をつけていく。まだ通っていない頂点がある場合は、再びそこからは
2SAT - yasu0207の日記
強連結成分分解のアルゴリズムをゼミでやったのでメモ。 2SATは強連結成分分解を利用して解ける。 2SATは多項式時間で解ける。ちなみに3SATはNP完全。解き方は２つある。 (1)ある変数xの割り当てを0で固定すると、2SATなので、xを含む節のxとは異なる変数の割り当てが決まる。 このようにして矛盾が起こると、xへの割り当てが決定し、xを含む節を消去して再帰。 (2)2SATなので節は(x∨¬y)のような形をしている。これはy⇒xと同じである 各論理変数、論理否定それぞれに頂点を用意して、y⇒xを式が含んでいれば有効辺(y,x)をグラフに加える。 このようにしてできたグラフに強連結成分分解アルゴリズムを適用し、ある強連結成分が同じ変数の真リテラルと偽リテラルを含んだときに充足割り当てが存在しなくなる。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Microsoft PowerPoint - SATSolving.ppt
