拓?fù)渑判驁D算法sat_歐拉h(huán)amilton路教學(xué)課件-展示頁
2024-09-12 09:37本頁面
【正文】 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 18 SAT ? 可滿足性問題 (Satisfiability Problem) –給定一布爾表達(dá)式，求一個(gè)使其為真的解 –一般的 SAT問題是 NPC的 ? kSAT問題 –析取范式 :(A or B) and (A or not C) and… –如果每個(gè)子式包含的變量數(shù)不超過 k，則稱為 kSAT問題 ( ) ( ) ( )A B C A D C D? ? ? ? ? ? ? ?425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 19 2SAT ? 2SAT有多項(xiàng)式算法 –把每個(gè)變量當(dāng)作兩個(gè)點(diǎn)： A和 not A –對于子式 (A or B)，添加兩條邊 ?(not A ? B) ?(not B ? A) –邊的含義：設(shè)存在邊 (u,v)，則如果選擇了 u，必須要同時(shí)選擇 v 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 110 2SAT ?對原圖求強(qiáng)連通分量，可知：每個(gè)強(qiáng)連通分量中的所有點(diǎn)必定同時(shí)被選擇 ?But…點(diǎn) A和點(diǎn) not A只能選一個(gè) ?如果某點(diǎn) x和點(diǎn) not x屬于同一 SCC，必?zé)o解 ?反之？ 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 111 2SAT ?解的構(gòu)造： (1)將原圖縮點(diǎn)后得到 DAG: G (2)把 G圖的邊反向，得到 G’，對 G’拓?fù)渑判? (3)選擇拓?fù)湫蜃羁壳暗奈慈旧c(diǎn) p (4)將 p染紅色，將與 p矛盾的點(diǎn) p’及 p’的所有后代染藍(lán)色 (5)重復(fù)第 (3)(4)步直至所有點(diǎn)被染色，紅色點(diǎn)即為要選擇的點(diǎn) 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 112 2SAT ( ) ( ) ( )x y x z y z? ? ? ? ? ? ? ? ?x0 x1 y0 y1 z1 z0 x0 x1 y0 y1 z1 z0 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 113 例題分析 ? Perfect election (TOJ 3122) – i和 j至少有一個(gè)被選 (i OR j) – i和 j至少有一個(gè)不被選 (~i OR ~j) – i被選或 j不被選 (i OR ~j) – i不被選或 j被選 (~i OR j) ? Get Luffy Out (POJ 2723) 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 114 例題分析 ? Building Roads (POJ 2749) ? FJ有 N個(gè)牛棚和兩個(gè)中轉(zhuǎn)站，現(xiàn)在要從每個(gè)牛棚修一條路連接到兩個(gè)中轉(zhuǎn)站之一，并且滿足給出的限制條件，限制條件形式是 (i和 j必須連到同一個(gè)中轉(zhuǎn)站 )或者(i和 j不能連到同一個(gè)中轉(zhuǎn)站 ) 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 115 例題分析 ?兩個(gè)牛棚之間的距離定義為 –如果兩牛棚連到同一個(gè)中轉(zhuǎn)站，則距離為兩條路之和 –如果兩牛棚連到不同中轉(zhuǎn)站，則距離為兩條路之和再加上兩中轉(zhuǎn)站間的距離 ?要求在滿足限制條件下，任意兩牛棚距離的最大值最小。425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 11 圖算法 (2) ——拓?fù)渑判?,2SAT,歐拉 /Ha
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1