拓撲排序圖算法sat_歐拉h(huán)amilton路教學課件-全文預覽
【正文】 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 126 例題分析 ?容易聯(lián)想到歐拉路 –每個單詞相當于在首字母和尾字母之間連一條邊 –得到一個最多 26個點的有向圖，求歐拉路即可 –注意先判斷 連通性 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 127 例題分析 ? Ural1124 Mosaic –有 M種卡片，每種有 N張，初始時放在 M個盒子里，每個盒子里有 N張，但是可能有某些卡片放錯了位置，因此需要進行一些移動，最后使得每張卡片都放到它應該在的盒子（第 1種卡片都放入盒 1，第 2種卡片都放入盒 2 …）。 dfs()。 –如果圖連通，且恰有一點 u的出度比入度大1，另有一點 v的出度比入度小 1，其余的出度等于出度，則存在歐拉路，起點為 u，終點為 v。 –如果圖連通，且恰有兩點是奇數(shù)度，則有歐拉路。 ? 2） i和 j必須連到同一個中轉站，增加 (Xi OR ~Xj)和 (~Xi OR Xj)。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) ——拓撲排序 ,2SAT,歐拉 /Hamilton路 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 12 拓撲排序 ?有向無環(huán)圖 (Directed Acyclic Graph, DAG) ?圖的結點存在一個拓撲序，即滿足下面條件的序列： (序列不一定唯一 ) –如果圖中有邊 (u,v)，則 u必定排在 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 13 拓撲排序 ?典型例子： –課程安排 (一些課是另一些課的先修課程 ) –書本摞放 (一本書可能壓住下面的某幾本書 ) –未知數(shù)排序 (給定一些未知數(shù)間的不等式，求滿足這些不等式的一個排序序列 ) ? DP的狀態(tài)轉移關系實際上就是構建在一個 DAG上的 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 14 拓撲排序 ?算法 –(1) 計算每個點的入度，入度為 0的點加入隊列 Q –(2) 從 Q中取出一個點 p，輸出 –(3) 所有與 p相鄰的點的入度減 1。 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 116 例題分析 ?把每個點看作一個變量，取 0和 1分別表示連到兩個中轉站 ? 1） i和 j不連到同一個中轉站，增加 (Xi OR Xj)和 (~Xi OR ~Xj)。如果 ? 3） D1i + D1j S，就增加和取范式（ ~Xi OR ~Xj） ? 4） D2i + D2j S，就增加和取范式（ Xi OR Xj） ? 5） D1i + D2j + DD S，增加和取范式 (~Xi OR Xj) ? 6） D2i + D1j + DD S，增加和取范式 (Xi OR ~Xj) ? 檢驗此 SAT問題是否有解，即可驗證 S是否可以 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 118 HornSAT ? 每個子句里最多有一個 positive literal ? 存在多項式的構造算法： –如果每個子句都包含大于 1個變量，則所有變量取負即為解 –否則，存在包含 1個變量的子句，則這些變量的值可唯一確定，代入原式化簡即可 ? TOJ 2730 Horn Clauses ( ) ( )A B C B
環(huán)評公示相關推薦
鄂ICP備17016276號-1