yasu0207 https://blog.hatena.ne.jp/yasu0207/ yasu0207の日記 https://yasu0207.hatenadiary.org/ algorithm 強連結成分分解のアルゴリズムをゼミでやったのでメモ。 2SATは強連結成分分解を利用して解ける。2SATは多項式時間で解ける。ちなみに3SATはNP完全。解き方は２つある。 (1)ある変数xの割り当てを0で固定すると、2SATなので、xを含む節のxとは異なる変数の割り当てが決まる。 このようにして矛盾が起こると、xへの割り当てが決定し、xを含む節を消去して再帰。 (2)2SATなので節は(x∨¬y)のような形をしている。これはy⇒xと同じである 各論理変数、論理否定それぞれに頂点を用意して、y⇒xを式が含んでいれば有効辺(y,x)をグラフに加える。 このようにしてできたグラフに強連結成分分解ア… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyasu0207.hatenadiary.org%2Fentry%2F20091206%2F1260111871" title="2SAT - yasu0207の日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-12-06 00:04:31 rich https://yasu0207.hatenadiary.org/entry/20091206/1260111871 1.0 100%