拓?fù)渑判驁D算法sat_歐拉h(huán)amilton路教學(xué)課件(參考版)
2024-09-04 09:37本頁面
【正文】 我們一定能找到某個(gè)中間點(diǎn) Vi，使得圖中存在邊 (Vi,p)和 (p,Vi+1)，于是可以得到新路 V1→ V2→ …→ Vi→ p→ Vi+1→ …→ Vn –故原題可在多項(xiàng)式時(shí)間內(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ì) –對(duì)于所有不相鄰的頂點(diǎn)對(duì)，有 deg(x)+deg(y)=n –滿足 Ore性質(zhì)的圖一定有 Hamilton回路，且能在多項(xiàng)式時(shí)間內(nèi)構(gòu)造出這樣一條回路 ?旅行售貨商問題 (TSP) 。 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 競(jìng)賽圖的 Hamilton路 –構(gòu)造方法： ?假設(shè)我們已經(jīng)找到了一條路 V1→ V2→ …→ Vn ?我們可以把每個(gè)新點(diǎn) p都加進(jìn)這條路里面去，從而最終得到一條 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 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 例題分析 ?競(jìng)賽圖：特殊的有向圖，對(duì)于任意點(diǎn)對(duì)(i,j)都有邊 (i,j)或邊 (j,i) ?實(shí)際上，競(jìng)賽圖的 Hamilton路一定存在，并且可以在多項(xiàng)式時(shí)間內(nèi)構(gòu)造出來。求要完成所有任務(wù)所需的最少的重啟次數(shù)，以及完成任務(wù)的順序。那么狀態(tài)轉(zhuǎn)移方程為： opt[mask][k] = min(opt[mask{k}][i] + cost[i][k]) 其中 i是所有與 k相鄰的點(diǎn)， 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要用一臺(tái)機(jī)器完成一系列的任務(wù)，給定一些 i→ j條件，表示機(jī)器在做完 i以后可以繼續(xù)做 j，而不用重新啟動(dòng)。 ?權(quán)值為兩點(diǎ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)過圖中每個(gè) 點(diǎn) 恰好一次的路 ?經(jīng)典 NP完全問題，尚未發(fā)現(xiàn)多項(xiàng)式算法 ?常見解決方案 –狀態(tài)壓縮 DP (點(diǎn)數(shù)較少的情況 , 如 N=15) –利用問題特殊性 (對(duì)某些特殊的圖有多項(xiàng)式算法 ) 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解法 ?對(duì)于點(diǎn)數(shù)較少的情況，可以用狀態(tài)壓縮的DP來做。 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 130 例題分析 ? Ouroboros Snake –TOJ1070 (此處略有改動(dòng) ) –題目大意：給定長(zhǎng)度 k，進(jìn)制 b，求出一個(gè)由[0..b1]的數(shù)組成的環(huán)狀序列，使得從環(huán)上任一個(gè)位置開始的 k位數(shù)表示一個(gè)唯一的 b進(jìn)制數(shù)。 –在不同的連通分量之間必然要有一次空著手的移動(dòng)。 –求最少的移動(dòng)次數(shù) (M=500, n=50) 42513
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1