基于連通性狀態(tài)壓縮的動態(tài)規(guī)劃問題_Cdq

1、Email : skyfish_引入狀態(tài)總數(shù)為狀態(tài)總數(shù)為指數(shù)級指數(shù)級以集合信息為狀態(tài)以集合信息為狀態(tài) 我的論文針對其中的一類問題進(jìn)行探討和我的論文針對其中的一類問題進(jìn)行探討和研究研究 狀態(tài)中需要記錄若干個元素之間狀態(tài)中需要記錄若干個元素之間的的連通連通情況，稱為情況，稱為【例】Formula 1 (Ural1519) 一個一個 m * n 的棋盤的棋盤 有的格子存在障礙有的格子存在障礙 求經(jīng)過所有非障礙格子的哈密頓回路個數(shù)求經(jīng)過所有非障礙格子的哈密頓回路個數(shù)m, n12初步分析 問題特點：問題特點： 數(shù)據(jù)規(guī)模小數(shù)據(jù)規(guī)模小m, n12搜索?O(mn)!)狀態(tài)壓縮! 棋盤模型棋盤模型劃分階段：從上

2、到下，從左到右逐格遞推劃分階段：從上到下，從左到右逐格遞推基本概念：插頭，輪廓線基本概念：插頭，輪廓線基本概念 插頭一個格子某個方向的插頭存在一個格子某個方向的插頭存在表示這個格子在這個方向與相表示這個格子在這個方向與相鄰格子相連鄰格子相連 輪廓線已決策格子和未決策格已決策格子和未決策格子的分界線子的分界線輪廓線上方與其相連的輪廓線上方與其相連的有有n+1個插頭，包括個插頭，包括n個個下插頭和下插頭和1個右插頭個右插頭初步分析 問題特點：問題特點： 數(shù)據(jù)規(guī)模小數(shù)據(jù)規(guī)模小 棋盤模型棋盤模型每個插頭是否存在每個插頭是否存在 所有的非障礙格子連通所有的非障礙格子連通插頭之間的連通性插頭之間的連通性!

3、確立狀態(tài) 設(shè)設(shè) f (i, j, S) 表示轉(zhuǎn)移完表示轉(zhuǎn)移完(i, j) ，輪廓線上從左到輪廓線上從左到右右n+1個插頭是否存在以及它們的連通性為個插頭是否存在以及它們的連通性為S的方案總數(shù)的方案總數(shù) 如何表示如何表示S? 最小表示法12201 無插頭標(biāo)記無插頭標(biāo)記0 0，有插頭標(biāo)記一個正整數(shù)，有插頭標(biāo)記一個正整數(shù) 連通的插頭標(biāo)記相同的數(shù)字連通的插頭標(biāo)記相同的數(shù)字 從左到右依次標(biāo)記從左到右依次標(biāo)記f (3,2,1,2,2,0,1)狀態(tài)轉(zhuǎn)移 考慮每個格子的狀態(tài)考慮每個格子的狀態(tài), 根據(jù)上一個狀態(tài)根據(jù)上一個狀態(tài)O(n)掃掃描計算出新的最小表示狀態(tài)描計算出新的最小表示狀態(tài) 對于對于m = n = 1

4、2的無障礙棋盤的極限數(shù)據(jù)的無障礙棋盤的極限數(shù)據(jù), 擴(kuò)展擴(kuò)展?fàn)顟B(tài)總數(shù)為狀態(tài)總數(shù)為1333113 , 問題已經(jīng)基本解決問題已經(jīng)基本解決 本題為一個棋盤模型的本題為一個棋盤模型的簡單回路簡單回路問題問題針對問題的特殊性針對問題的特殊性, 是否有更好的方法呢是否有更好的方法呢?進(jìn)一步分析 每個非障礙格子恰好有每個非障礙格子恰好有2個插頭個插頭 輪廓線以上由若干條互不相交的路徑構(gòu)成輪廓線以上由若干條互不相交的路徑構(gòu)成 每條路徑的兩端對應(yīng)兩個插頭每條路徑的兩端對應(yīng)兩個插頭插頭兩兩匹配 從左到右一定不會出現(xiàn)從左到右一定不會出現(xiàn)4個插頭個插頭a, b, c, d，a, c匹配，匹配，b, d匹配匹配dcab插

5、頭不會交叉 括號表示法( () (0：無插頭狀態(tài)，用：無插頭狀態(tài)，用 # 表示表示1：左括號插頭，用：左括號插頭，用 ( 表示表示 2：右括號插頭，用：右括號插頭，用 ) 表示表示3進(jìn)制進(jìn)制#(1 1 2 0 2 1 2)3狀態(tài)的轉(zhuǎn)移 每次轉(zhuǎn)移相當(dāng)于輪廓線上當(dāng)前決策格子的左插每次轉(zhuǎn)移相當(dāng)于輪廓線上當(dāng)前決策格子的左插頭改成下插頭，上插頭改成右插頭的狀態(tài)頭改成下插頭，上插頭改成右插頭的狀態(tài)Case 1沒有上插頭和左插頭，有下插頭和右插頭，沒有上插頭和左插頭，有下插頭和右插頭，相當(dāng)于相當(dāng)于構(gòu)成一個新的連通塊構(gòu)成一個新的連通塊 ) 插頭插頭 ( 插頭插頭轉(zhuǎn)移時間：轉(zhuǎn)移時間：O(1)Case 2有上插頭

6、和左插頭，這種情況下相當(dāng)于有上插頭和左插頭，這種情況下相當(dāng)于合并合并兩個連通分量兩個連通分量預(yù)處理每個狀態(tài)每的預(yù)處理每個狀態(tài)每的括號所匹配的括號括號所匹配的括號轉(zhuǎn)移時間轉(zhuǎn)移時間: : O(1) ( 插頭插頭(插頭插頭 ( 插頭插頭Case 2.1 上插頭和左插頭均為上插頭和左插頭均為( (插頭插頭Case 2有上插頭和左插頭有上插頭和左插頭轉(zhuǎn)移時間：轉(zhuǎn)移時間：O(1) ( 插頭插頭)插頭插頭Case 2.2 左插頭為左插頭為) )插頭，上插頭為插頭，上插頭為( (插頭插頭Case 2有上插頭和左插頭有上插頭和左插頭 ( 插頭插頭)插頭插頭路徑的兩端連接路徑的兩端連接起來形成回路起來形成回路Ca

7、se 2.3 左插頭為左插頭為( (插頭，上插頭為插頭，上插頭為) )插頭插頭Case 3上上插頭和左插頭恰好有一個，這種情況相當(dāng)插頭和左插頭恰好有一個，這種情況相當(dāng)于于延續(xù)原來的連通分量延續(xù)原來的連通分量 ) 插頭插頭)插頭插頭無插頭無插頭轉(zhuǎn)移時間：轉(zhuǎn)移時間：O(1)實驗比較測試數(shù)據(jù) 最小表示 7Based最小表示 8Based括號表示 3Based括號表示 4Basedm = n = 10無障礙31ms15ms0ms0msm = n = 11(1,1)為障礙187ms109ms46ms31msm = n = 12無障礙873ms499ms265ms140ms建議使用建議使用2k進(jìn)制，位運(yùn)算

8、效率高進(jìn)制，位運(yùn)算效率高拓展 如果求經(jīng)過所有非障礙格子的如果求經(jīng)過所有非障礙格子的哈密頓哈密頓路徑路徑的個數(shù)呢的個數(shù)呢?獨立插頭獨立插頭 0 無插頭狀態(tài)無插頭狀態(tài) 1 左括號插頭左括號插頭 2 右括號插頭右括號插頭 3 獨立插頭獨立插頭3進(jìn)制進(jìn)制4進(jìn)制進(jìn)制 如果一個連通塊只有如果一個連通塊只有1個插頭或大于個插頭或大于2個插頭呢個插頭呢?廣義的括號匹配 括號表示法需要滿足一個括號表示法需要滿足一個連通塊內(nèi)恰好有連通塊內(nèi)恰好有2個插頭個插頭特殊性 對于一個對于一個大于大于2個插頭的個插頭的連通塊連通塊 最左邊的插頭標(biāo)記為最左邊的插頭標(biāo)記為 ( 最右邊的插頭標(biāo)記為最右邊的插頭標(biāo)記為 ) 中間的插頭

9、標(biāo)記為中間的插頭標(biāo)記為 )( 單獨為一個連通塊的插頭標(biāo)記為單獨為一個連通塊的插頭標(biāo)記為 ( )廣義的括號表示法 左括號與右括號匹配對應(yīng)的插頭連通左括號與右括號匹配對應(yīng)的插頭連通 例例: 最小表示法最小表示法 廣義括號表示法廣義括號表示法12234321()()普適性總結(jié)簡單回路簡單回路最小表示法最小表示法一般性一般性特殊性特殊性括號表示法括號表示法拓拓展展簡單路徑簡單路徑3 3進(jìn)制進(jìn)制4 4進(jìn)制進(jìn)制括號表示法的改進(jìn)括號表示法的改進(jìn)廣廣義義的的括括號號表表示示法法全文研究內(nèi)容 一類簡單路徑問題一類簡單路徑問題 一類棋盤染色問題一類棋盤染色問題 一類基于非棋盤模型的問題一類基于非棋盤模型的問題 一

10、類最優(yōu)性問題的剪枝優(yōu)化一類最優(yōu)性問題的剪枝優(yōu)化Rocket Mania (Zju2125)生成樹計數(shù) (NOI2007)Black & White(Uva10532)Formula 1(Ural1519)Formula 2(改編自Formula 1)Thank you for listening!Questions are welcome. 棋盤染色問題 k連通塊問題連通塊問題 記錄輪廓線上記錄輪廓線上n個格子的連通性和染色情個格子的連通性和染色情況況 相鄰的格子是否相連取決于兩個格子的相鄰的格子是否相連取決于兩個格子的顏色是否相同顏色是否相同棋盤與非棋盤問題的共通點 存在一個序，在這

11、個序中有邊相連的點的距離存在一個序，在這個序中有邊相連的點的距離不超過不超過k k一定是一個比較小的數(shù)，以這一定是一個比較小的數(shù)，以這k個數(shù)為輪廓線個數(shù)為輪廓線確立狀態(tài)確立狀態(tài) Formula 1中點的序即為從左到右，從上到下，中點的序即為從左到右，從上到下，k = n Noi2007的生成樹計數(shù)一題的生成樹計數(shù)一題, 序為序為1 . n, 有邊相有邊相連的點距離不超過連的點距離不超過5Rocket Mania 一個一個9 * 6的棋盤的棋盤, 左邊左邊9根火柴根火柴, 右邊右邊9根火根火箭每個格子可能為空格箭每個格子可能為空格,也可能為一段管道也可能為一段管道 管道有管道有4種：種： 點燃左

12、邊第點燃左邊第X根火根火柴，要求旋轉(zhuǎn)每個柴，要求旋轉(zhuǎn)每個管道使得發(fā)射的火管道使得發(fā)射的火箭盡可能的多箭盡可能的多Analysis 狀態(tài)狀態(tài)：f ijSFire 剪枝一：如果剪枝一：如果沒有一個插頭被火柴點燃，沒有一個插頭被火柴點燃，那么這個狀態(tài)可以舍去那么這個狀態(tài)可以舍去 剪枝二：如果一個插頭沒有被火柴點燃，剪枝二：如果一個插頭沒有被火柴點燃，并且這個插頭為一個獨立的連通塊，那并且這個插頭為一個獨立的連通塊，那么這個插頭為無效插頭么這個插頭為無效插頭, 可以設(shè)置為無可以設(shè)置為無效插頭狀態(tài)效插頭狀態(tài)Analysis 狀態(tài)狀態(tài)：f ijSFire 剪枝三：最優(yōu)性剪枝，對于一個剪枝三：最優(yōu)性剪枝，對

13、于一個(i, j)選選擇擇Fire中包含中包含1最多的狀態(tài)最多的狀態(tài)Best，如果一如果一個狀態(tài)的所有插頭在個狀態(tài)的所有插頭在Best中不僅存在而中不僅存在而且都被火柴點燃，那么這個狀態(tài)就可以且都被火柴點燃，那么這個狀態(tài)就可以舍去舍去問題的特點 數(shù)據(jù)規(guī)模中某一維或某幾維非常小，這是狀數(shù)據(jù)規(guī)模中某一維或某幾維非常小，這是狀態(tài)壓縮的基礎(chǔ)態(tài)壓縮的基礎(chǔ) 需要滿足動態(tài)規(guī)劃的基本性質(zhì)：最優(yōu)性原理需要滿足動態(tài)規(guī)劃的基本性質(zhì)：最優(yōu)性原理和無后效性和無后效性 它與圖論模型有著密切的關(guān)聯(lián)，問題本身與它與圖論模型有著密切的關(guān)聯(lián)，問題本身與連通性有關(guān)或者隱含著連通信息連通性有關(guān)或者隱含著連通信息哈密頓路徑的轉(zhuǎn)移 考慮

14、與獨立插頭有關(guān)的幾種轉(zhuǎn)移：考慮與獨立插頭有關(guān)的幾種轉(zhuǎn)移：I. 上插頭和左插頭都不存在上插頭和左插頭都不存在獨立插頭獨立插頭一個右插頭或下插頭成為了路徑的一端一個右插頭或下插頭成為了路徑的一端哈密頓路徑的轉(zhuǎn)移 考慮與獨立插頭有關(guān)的幾種轉(zhuǎn)移：考慮與獨立插頭有關(guān)的幾種轉(zhuǎn)移：II. 上插頭和左插頭都存在上插頭和左插頭都存在左括號插頭左括號插頭獨立插頭獨立插頭獨立插頭獨立插頭右括號插頭右括號插頭左括號插頭和獨立插頭連接起來后，左括號插左括號插頭和獨立插頭連接起來后，左括號插頭對應(yīng)的右括號插頭成為了新的獨立插頭頭對應(yīng)的右括號插頭成為了新的獨立插頭哈密頓路徑的轉(zhuǎn)移 考慮與獨立插頭有關(guān)的幾種轉(zhuǎn)移：考慮與獨立插

15、頭有關(guān)的幾種轉(zhuǎn)移：III. 上插頭和左插頭恰好有一個存在上插頭和左插頭恰好有一個存在左括號插頭左括號插頭右括號插頭右括號插頭獨立插頭獨立插頭左括號插頭被左括號插頭被“封住封住”，成為路徑的一端，它所，成為路徑的一端，它所對應(yīng)的右括號插頭成為了一個新的獨立插頭對應(yīng)的右括號插頭成為了一個新的獨立插頭相關(guān)試題 Uva10531 Maze Statistics SRM312 CheapestIsland IPSC2007 Delicious Cake NWERC2004 Pipes Hnoi2007 Park Poj1739 Tonys Tour 括號表示法的優(yōu)勢 元素之間相對獨立元素之間相對獨立 轉(zhuǎn)移代價低，常數(shù)因子小轉(zhuǎn)移代價低，常數(shù)因子小 更加直觀，清晰，自然更加直觀，清晰，自然參考文獻(xiàn)劉汝佳、黃亮算法藝術(shù)與信息學(xué)競賽金愷 Black & White解題報告, 2004年毛子青動態(tài)規(guī)劃算法的優(yōu)化技巧, 2001年/onl