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

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

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

3、確立狀態(tài) 設(shè)設(shè) f (i, j, S) 表示轉(zhuǎn)移完表示轉(zhuǎn)移完(i, j) ，輪廓線上從左到輪廓線上從左到右右n+1個(gè)插頭是否存在以及它們的連通性為個(gè)插頭是否存在以及它們的連通性為S的方案總數(shù)的方案總數(shù) 如何表示如何表示S? 最小表示法12201 無插頭標(biāo)記無插頭標(biāo)記0 0，有插頭標(biāo)記一個(gè)正整數(shù)，有插頭標(biāo)記一個(gè)正整數(shù) 連通的插頭標(biāo)記相同的數(shù)字連通的插頭標(biāo)記相同的數(shù)字 從左到右依次標(biāo)記從左到右依次標(biāo)記f (3,2,1,2,2,0,1)狀態(tài)轉(zhuǎn)移 考慮每個(gè)格子的狀態(tài)考慮每個(gè)格子的狀態(tài), 根據(jù)上一個(gè)狀態(tài)根據(jù)上一個(gè)狀態(tài)O(n)掃掃描計(jì)算出新的最小表示狀態(tài)描計(jì)算出新的最小表示狀態(tài) 對(duì)于對(duì)于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)基本解決 本題為一個(gè)棋盤模型的本題為一個(gè)棋盤模型的簡(jiǎn)單回路簡(jiǎn)單回路問題問題針對(duì)問題的特殊性針對(duì)問題的特殊性, 是否有更好的方法呢是否有更好的方法呢?進(jìn)一步分析 每個(gè)非障礙格子恰好有每個(gè)非障礙格子恰好有2個(gè)插頭個(gè)插頭 輪廓線以上由若干條互不相交的路徑構(gòu)成輪廓線以上由若干條互不相交的路徑構(gòu)成 每條路徑的兩端對(duì)應(yīng)兩個(gè)插頭每條路徑的兩端對(duì)應(yīng)兩個(gè)插頭插頭兩兩匹配 從左到右一定不會(huì)出現(xiàn)從左到右一定不會(huì)出現(xiàn)4個(gè)插頭個(gè)插頭a, b, c, d，a, c匹配，匹配，b, d匹配匹配dcab插

5、頭不會(huì)交叉 括號(hào)表示法( () (0：無插頭狀態(tài)，用：無插頭狀態(tài)，用 # 表示表示1：左括號(hào)插頭，用：左括號(hào)插頭，用 ( 表示表示 2：右括號(hào)插頭，用：右括號(hào)插頭，用 ) 表示表示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è)新的連通塊構(gòu)成一個(gè)新的連通塊 ) 插頭插頭 ( 插頭插頭轉(zhuǎn)移時(shí)間：轉(zhuǎn)移時(shí)間：O(1)Case 2有上插頭

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

7、se 2.3 左插頭為左插頭為( (插頭，上插頭為插頭，上插頭為) )插頭插頭Case 3上上插頭和左插頭恰好有一個(gè)，這種情況相當(dāng)插頭和左插頭恰好有一個(gè)，這種情況相當(dāng)于于延續(xù)原來的連通分量延續(xù)原來的連通分量 ) 插頭插頭)插頭插頭無插頭無插頭轉(zhuǎn)移時(shí)間：轉(zhuǎn)移時(shí)間：O(1)實(shí)驗(yàn)比較測(cè)試數(shù)據(jù) 最小表示 7Based最小表示 8Based括號(hào)表示 3Based括號(hào)表示 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)過所有非障礙格子的哈密頓哈密頓路徑路徑的個(gè)數(shù)呢的個(gè)數(shù)呢?獨(dú)立插頭獨(dú)立插頭 0 無插頭狀態(tài)無插頭狀態(tài) 1 左括號(hào)插頭左括號(hào)插頭 2 右括號(hào)插頭右括號(hào)插頭 3 獨(dú)立插頭獨(dú)立插頭3進(jìn)制進(jìn)制4進(jìn)制進(jìn)制 如果一個(gè)連通塊只有如果一個(gè)連通塊只有1個(gè)插頭或大于個(gè)插頭或大于2個(gè)插頭呢個(gè)插頭呢?廣義的括號(hào)匹配 括號(hào)表示法需要滿足一個(gè)括號(hào)表示法需要滿足一個(gè)連通塊內(nèi)恰好有連通塊內(nèi)恰好有2個(gè)插頭個(gè)插頭特殊性 對(duì)于一個(gè)對(duì)于一個(gè)大于大于2個(gè)插頭的個(gè)插頭的連通塊連通塊 最左邊的插頭標(biāo)記為最左邊的插頭標(biāo)記為 ( 最右邊的插頭標(biāo)記為最右邊的插頭標(biāo)記為 ) 中間的插頭

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

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

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

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

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

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

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