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

基于連通性狀態(tài)壓縮的

動態(tài)規(guī)劃問題長沙市雅禮中學(xué)陳丹琦Email:skyfish_cdq@163.com引入狀態(tài)壓縮動態(tài)規(guī)劃狀態(tài)總數(shù)為指數(shù)級以集合信息為狀態(tài)我的論文針對其中的一類問題進(jìn)行探討和研究——狀態(tài)中需要記錄若干個元素之間的連通情況，稱為基于連通性狀態(tài)壓縮的動態(tài)規(guī)劃問題【例】Formula1(Ural1519)一個m*n

的棋盤有的格子存在障礙求經(jīng)過所有非障礙格子的哈密頓回路個數(shù)m,n≤12初步分析問題特點：數(shù)據(jù)規(guī)模小m,n≤12搜索?O((mn)!)狀態(tài)壓縮!√棋盤模型劃分階段：從上到下，從左到右逐格遞推基本概念：插頭，輪廓線基本概念插頭一個格子某個方向的插頭存在表示這個格子在這個方向與相鄰格子相連．輪廓線已決策格子和未決策格子的分界線輪廓線上方與其相連的有n+1個插頭，包括n個下插頭和1個右插頭．初步分析問題特點：數(shù)據(jù)規(guī)模小棋盤模型每個插頭是否存在所有的非障礙格子連通插頭之間的連通性!確立狀態(tài)設(shè)

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

括號表示法(()))(0：無插頭狀態(tài)，用#表示1：左括號插頭，用(表示2：右括號插頭，用)表示3進(jìn)制#(1120212)3狀態(tài)的轉(zhuǎn)移每次轉(zhuǎn)移相當(dāng)于輪廓線上當(dāng)前決策格子的左插頭改成下插頭，上插頭改成右插頭的狀態(tài)．Case1沒有上插頭和左插頭，有下插頭和右插頭，相當(dāng)于構(gòu)成一個新的連通塊．)插頭(插頭(###)(()#)轉(zhuǎn)移時間：O(1)Case2有上插頭和左插頭，這種情況下相當(dāng)于合并兩個連通分量預(yù)處理每個狀態(tài)每的括號所匹配的括號轉(zhuǎn)移時間:O(1)(插頭(插頭#(())(##()(插頭Case2.1上插頭和左插頭均為(插頭Case2有上插頭和左插頭轉(zhuǎn)移時間：O(1)(#)()(###)(插頭)插頭Case2.2左插頭為)插頭，上插頭為(插頭Case2有上插頭和左插頭(插頭)插頭路徑的兩端連接起來形成回路Case2.3左插頭為(插頭，上插頭為)插頭Case3上插頭和左插頭恰好有一個，這種情況相當(dāng)于延續(xù)原來的連通分量)插頭)插頭無插頭轉(zhuǎn)移時間：O(1)(()#)(()#)實驗比較測試數(shù)據(jù)最小表示7Based最小表示8Based括號表示3Based括號表示4Basedm=n=10無障礙31ms15ms0ms0msm=n=11(1,1)為障礙187ms109ms46ms31msm=n=12無障礙873ms499ms265ms140ms建議使用2k進(jìn)制，位運算效率高拓展如果求經(jīng)過所有非障礙格子的哈密頓路徑的個數(shù)呢?獨立插頭0→無插頭狀態(tài)1→左括號插頭2→右括號插頭3→獨立插頭3進(jìn)制→4進(jìn)制如果一個連通塊只有1個插頭或大于2個插頭呢?廣義的括號匹配括號表示法需要滿足一個連通塊內(nèi)恰好有2個插頭．特殊性對于一個大于2個插頭的連通塊最左邊的插頭標(biāo)記為(最右邊的插頭標(biāo)記為)中間的插頭標(biāo)記為)(單獨為一個連通塊的插頭標(biāo)記為()廣義的括號表示法廣義的括號表示法左括號與右括號匹配對應(yīng)的插頭連通例:

最小表示法→廣義括號表示法12234321(()((())))普適性總結(jié)簡單回路最小表示法一般性特殊性括號表示法拓展簡單路徑3進(jìn)制→4進(jìn)制括號表示法的改進(jìn)廣義的括號表示法全文研究內(nèi)容一類簡單路徑問題一類棋盤染色問題一類基于非棋盤模型的問題一類最優(yōu)性問題的剪枝優(yōu)化RocketMania(Zju2125)生成樹計數(shù)(NOI2007)Black&White(Uva10532)Formula1(Ural1519)Formula2(改編自Formula1)Thankyouforlistening!Questionsarewelcome.棋盤染色問題k連通塊問題記錄輪廓線上n個格子的連通性和染色情況．相鄰的格子是否相連取決于兩個格子的顏色是否相同．棋盤與非棋盤問題的共通點存在一個序，在這個序中有邊相連的點的距離不超過k．k一定是一個比較小的數(shù)，以這k個數(shù)為輪廓線確立狀態(tài)．Formula1中點的序即為從左到右，從上到下，k=n．Noi2007的生成樹計數(shù)