拓撲排序圖算法sat_歐拉h(huán)amilton路教學課件-資料下載頁
2025-08-22 09:37本頁面
【導(dǎo)讀】圖的結(jié)點存在一個拓撲序，即滿足下面。–未知數(shù)排序(給定一些未知數(shù)間的不等式，DP的狀態(tài)轉(zhuǎn)移關(guān)系實際上就是構(gòu)建在一。–所有與p相鄰的點的入度減1。到了入度為0的點，則加入隊列Q。–如果在執(zhí)行過程中發(fā)現(xiàn)找不到入度為0的點,如何求出字典序最小的拓撲序列?仍按字典序可以么?1應(yīng)該盡可能的早……對原圖求強連通分量，可知：每個強連。點A和點notA只能選一個。如果某點x和點notx屬于同一SCC，必。兩個牛棚之間的距離定義為。要求在滿足限制條件下，任意兩牛棚距。離的最大值最小。2）i和j必須連到同一個中轉(zhuǎn)站，增加(Xi. 設(shè)現(xiàn)在二分的答案是S。那么檢查每一對牛欄i和j（假設(shè)。4）D2i+D2j>S，就增加和取范式。檢驗此SAT問題是否有解，即可驗證S是否可以。每個子句里最多有一個positiveliteral. 存在多項式的構(gòu)造算法：
【正文】 點有偶數(shù)個，故我們可以將其兩兩配對，即可得出必須多走的距離。 ?權(quán)值為兩點間最短路 ?如果是有向圖，二分圖帶權(quán)匹配 ?如果是無向圖，一般圖帶權(quá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 135 Hamilton路 ?定義：經(jīng)過圖中每個 點 恰好一次的路 ?經(jīng)典 NP完全問題，尚未發(fā)現(xiàn)多項式算法 @@ ?常見解決方案 –狀態(tài)壓縮 DP (點數(shù)較少的情況 , 如 N=15) –利用問題特殊性 (對某些特殊的圖有多項式算法 ) 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 136 Hamilton路的 DP解法 ?對于點數(shù)較少的情況，可以用狀態(tài)壓縮的DP來做。比如用 opt[mask][k]表示已經(jīng)訪問過 mask表示的結(jié)點集合，并且最后位于點 k的最優(yōu)解。那么狀態(tài)轉(zhuǎn)移方程為： opt[mask][k] = min(opt[mask{k}][i] + cost[i][k]) 其中 i是所有與 k相鄰的點， mask{k}指從mask除去 k 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 137 例題分析 ? Task Sequences (Guangzhou 03) POJ1776 / TOJ1151 –題目大意 : Tom要用一臺機器完成一系列的任務(wù)，給定一些 i→ j條件，表示機器在做完 i以后可以繼續(xù)做 j，而不用重新啟動。一個任務(wù)只能被做一次。求要完成所有任務(wù)所需的最少的重啟次數(shù)，以及完成任務(wù)的順序。(任務(wù)數(shù) =1000) –數(shù)據(jù)保證對任意兩個不相同的任務(wù) i,j，都有i→ j或者 j→ i，或兩者兼有。 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 138 例題分析 ? Sample Input 3 0 1 1 1 0 1 0 0 0 ? Sample Output 1 3 2 1 3 1 3 2 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 139 例題分析 ?競賽圖：特殊的有向圖，對于任意點對(i,j)都有邊 (i,j)或邊 (j,i) ?實際上，競賽圖的 Hamilton路一定存在，并且可以在多項式時間內(nèi)構(gòu)造出來。 ?因此，最少的重啟次數(shù)一定是 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 140 競賽圖的 Hamilton路 –構(gòu)造方法： ?假設(shè)我們已經(jīng)找到了一條路 V1→ V2→ …→ Vn ?我們可以把每個新點 p都加進這條路里面去，從而最終得到一條 Hamilton路。 –(1)若圖中有邊 (p,V1)，得到 p→ V1→ V2→ …→ Vn –(2)若圖中有邊 (Vn,p)，得到 V1→ V2→ …→ Vn→ p –(3)否則，圖中必有邊 (V1,p)和 (p,Vn)。我們一定能找到某個中間點 Vi，使得圖中存在邊 (Vi,p)和 (p,Vi+1)，于是可以得到新路 V1→ V2→ …→ Vi→ p→ Vi+1→ …→ Vn –故原題可在多項式時間內(nèi)求解 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 141 More… ? Ore性質(zhì) –對于所有不相鄰的頂點對，有 deg(x)+deg(y)=n –滿足 Ore性質(zhì)的圖一定有 Hamilton回路，且能在多項式時間內(nèi)構(gòu)造出這樣一條回路 ?旅行售貨商問題 (TSP)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1