《狀態(tài)壓縮DP入門》PPT課件.ppt

經(jīng)典入門,狀態(tài)壓縮動(dòng)態(tài)規(guī)劃,狀態(tài)壓縮動(dòng)態(tài)規(guī)劃,狀態(tài)壓縮動(dòng)態(tài)規(guī)劃：動(dòng)態(tài)規(guī)劃的狀態(tài)有時(shí)候比較惡心，不容易表示出來，需要用一些編碼技術(shù)，把狀態(tài)壓縮的用簡(jiǎn)單的方式表示出來。典型方式：當(dāng)需要表示一個(gè)集合有哪些元素時(shí)，往往利用2進(jìn)制用一個(gè)整數(shù)表示。,經(jīng)典問題：TSP,一個(gè)n個(gè)點(diǎn)的帶權(quán)的有向圖，求一條路徑，使得這條路經(jīng)過每個(gè)點(diǎn)恰好一次，并且路徑上邊的權(quán)值和最小（或者最大）?；蛘咔笠粭l具有這樣性質(zhì)的回路，這是經(jīng)典的TSP問題。n=16(重要條件,狀態(tài)壓縮的標(biāo)志)今天講第一個(gè)問題的狀態(tài)壓縮動(dòng)態(tài)規(guī)劃的解法，第2個(gè)問題大同小異。,TSP,如何表示一個(gè)點(diǎn)集：由于只有16個(gè)點(diǎn)，所以我們用一個(gè)整數(shù)表示一個(gè)點(diǎn)集：例如：50000000000000101；（2進(jìn)制表示）它的第0位和第2位是1，就表示這個(gè)點(diǎn)集里有2個(gè)點(diǎn)，分別是點(diǎn)0和點(diǎn)2。310000000000011111；（2進(jìn)制表示）表示這個(gè)點(diǎn)集里有5個(gè)點(diǎn)，分別是0，1，2，4，5；,TSP,所以一個(gè)整數(shù)i就表示了一個(gè)點(diǎn)集；整數(shù)i可以表示一個(gè)點(diǎn)集，也可以表示是第i個(gè)點(diǎn)。狀態(tài)表示：dpij表示經(jīng)過點(diǎn)集i中的點(diǎn)恰好一次，不經(jīng)過其它的點(diǎn)，并且以j點(diǎn)為終點(diǎn)的路徑,權(quán)值和的最小值，如果這個(gè)狀態(tài)不存在，就是無窮大。,TSP,狀態(tài)轉(zhuǎn)移：?jiǎn)吸c(diǎn)集：狀態(tài)存在dpij=0；否則無窮大。非單點(diǎn)集：狀態(tài)存在dpij=min(dpks+wsj)k表示i集合中去掉了j點(diǎn)的集合，s遍歷集合k中的點(diǎn)并且dpks狀態(tài)存在，點(diǎn)s到點(diǎn)j有邊存在，wsj表示邊的權(quán)值。狀態(tài)不存在dpij為無窮大。,TSP,最后的結(jié)果是：min(dp(1n)1j)(0=jn)；技巧：利用2進(jìn)制，使得一個(gè)整數(shù)表示一個(gè)點(diǎn)集，這樣集合的操