Return to Video

06-36 Reduce 3-Colorability to SAT

  • 0:00 - 0:08
    3-COLがNPならSATはNP完全で 同時にNP困難です
  • 0:08 - 0:13
    つまり3-COL問題はSATを使えば解くことができます
  • 0:13 - 0:16
    実に興味深いやり方です
  • 0:16 - 0:23
    4つのノードと4つのエッジがある
    簡単なグラフを用意します
  • 0:23 - 0:27
    このグラフに3色を当てはめていきます
  • 0:27 - 0:31
    ここではグラフに3色が当てはまるなら
    充足可能なブールの論理式を作成します
  • 0:31 - 0:36
    同じ問題だからです
  • 0:36 - 0:40
    まずは複数のブール論理変数を作ります
  • 0:40 - 0:47
    正確には12です 4つのノードa、b、c、dのうち
    どれかに対応します
  • 0:47 - 0:50
    各ノードにブール論理変数を当てはめて
  • 0:50 - 0:54
    赤、緑、黄の3色のうちのどれかを割り当てます
  • 0:54 - 1:01
    変数のA_redが真 A_greenが偽 A_yellowが偽の場合は
  • 1:01 - 1:06
    ノードaを赤で塗りましょう
  • 1:06 - 1:11
    12の変数でこの3つのうち1つが真であり
    かつ色が被らない場合のみ真となる式を作ります
  • 1:11 - 1:16
    気をつけていただきたいのは真が2つある場合です
  • 1:16 - 1:20
    ブールの論理式ではしばしば起こり得ますが
    これでは色の割り振りは無理ですね
  • 1:20 - 1:27
    オレンジ色にしたくなりますがそれではダメです
  • 1:27 - 1:37
    12の変数すべてに実行して真の式を作成します
  • 1:37 - 1:46
    対応する色が有効である限り3色に割り振られる値は
  • 1:46 - 1:49
    不調和を起こしません
  • 1:49 - 1:55
    例えば隣接ノードは違う色になりますので
  • 1:55 - 1:58
    ノードaとノードbの両方が赤になることはありません
  • 1:58 - 2:05
    このケースで自動的に作成される方程式があるので
    見てみましょう
  • 2:05 - 2:12
    これは一例です 少し奇妙で複雑に見えますが
  • 2:12 - 2:16
    実際はよくできた構造をしています
  • 2:16 - 2:25
    まず論理として
  • 2:25 - 2:30
    まず"Aは赤""Aは緑""Aは黄"の
    どれか1つが真になります
  • 2:30 - 2:37
    もしすべてが偽ならAの色は分かりません
  • 2:37 - 2:41
    次の論理として1つのノードに対して
    2つの色が真になることはありません
  • 2:41 - 2:45
    "Aは赤""Aは緑"の両方が真だとおかしいわけです
  • 2:45 - 2:51
    真になるのは赤か緑のどちらかのみです
  • 2:51 - 2:57
    同じく赤と黄 緑と黄もどちらかのみになります
  • 2:57 - 3:02
    この論理を4つのノードすべてに当てはめていき
  • 3:02 - 3:07
    有効な色の割り当てを導き出します
  • 3:07 - 3:10
    そして追加の節で
  • 3:10 - 3:14
    "AとBが両方赤になることはない"と追加します
  • 3:14 - 3:19
    同様に"AとBが両方緑になることはない"と
  • 3:19 - 3:21
    "AとBが両方黄になることはない"も追加します
  • 3:21 - 3:25
    つまりエッジを共有しているので
    Aが何色になろうとも
  • 3:25 - 3:32
    Bと同じ色になることはないと指示します
  • 3:32 - 3:38
    各エッジに対してこれら3つの命令を与え
    色を1つずつ除外していきます
  • 3:38 - 3:42
    エッジ1の場合 エッジ2の場合といった具合です
  • 3:42 - 3:45
    エッジは4本あるので4つの塊がありますね
  • 3:45 - 3:50
    この論理式は充足可能な命題で
  • 3:50 - 3:56
    3色の割り当てが可能な場合に限り真を導きます
  • 3:56 - 4:00
    この方程式は私がグラフと見比べながら
    少しずつ作成していきましたが
  • 4:00 - 4:06
    ご自身が使用される際には自動的に適用できます
  • 4:06 - 4:10
    自分なりの使い方を考えてみてください
  • 4:10 - 4:12
    次で解いていきましょう
タイトル:
06-36 Reduce 3-Colorability to SAT
Video Language:
English
Team:
Udacity
プロジェクト:
CS215 - Intro to Algorithms
Duration:
04:13

Japanese subtitles

改訂