基于連通性狀態壓縮的動態規劃問題長沙市雅禮中學陳丹琦【摘要】基于狀態壓縮的動態規劃問題是一類以集合信息為狀態且狀態總數為指數級的特殊的動態規劃問題．在狀態壓縮的根底上，有一類問題的狀態中必須要記錄假設干個元素的連通情況，我們稱這樣的問題為基于連通性狀態壓縮的動態規劃問題，本文著重對這類問題的解法及優化進行探討和研究．本文主要從動態規劃的幾個步驟——劃分階段，確立狀態，狀態轉移以及程序實現來介紹這類問題的一般解法，會特別針對到目前為止信息學競賽中涌現出來的幾類題型的解法作一個探討．結合例題，本文還會介紹作者在減少狀態總數和降低轉移開銷兩個方面對這類問題優化的一些心得．【關鍵詞】狀態壓縮連通性括號表示法輪廓線插頭棋盤模型【目錄】TOC\o"1-5"\h\z\u【序言】3【正文】5一.問題的一般解法5【例1】Formula15問題描述5算法分析5小結11二.一類簡單路徑問題12【例2】Formula215問題描述15算法分析15小結16三.一類棋盤染色問題17【例3】Black&White17問題描述17算法分析17小結19四.一類基于非棋盤模型的問題20【例4】生成樹計數20問題描述20算法分析20小結21五.一類最優性問題的剪枝技巧22【例5】RocketMania22問題描述22算法分析22小結25六.總結26【參考文獻】27【感謝】27【附錄】27【序言】先看一個非常經典的問題——旅行商問題(即TSP問題，TravelingSalesmanProblem)：一個n(≤15)個點的帶權完全圖，求權和最小的經過每個點恰好一次的封閉回路．這個問題已經被證明是NP完全問題，那么對于這樣一類無多項式算法的問題，搜索算法是不是解決問題的唯一途徑呢?答案是否認的．不難發現任何時候我們只需要知道哪些點已經被遍歷過而遍歷點的具體順序對以后的決策是沒有影響的，因此不妨以當前所在的位置i，遍歷過的點的集合S為狀態作動態規劃：，其中j<>i，i，jinS．動態規劃的時間復雜度為，雖然為指數級算法，但是對于n=15的數據規模來說已經比樸素的的搜索算法高效很多了．我們通常把這樣一類以一個集合內的元素信息作為狀態且狀態總數為指數級別的動態規劃稱為基于狀態壓縮的動態規劃或集合動態規劃．基于狀態壓縮的動態規劃問題通常具有以下兩個特點：1．數據規模的某一維或幾維非常小；2．它需要具備動態規劃問題的兩個根本性質：最優性原理和無后效性．一般的狀態壓縮問題，壓縮的是一個小范圍內每個元素的決策，狀態中元素的信息相對獨立．而有些問題，僅僅記錄每個元素的決策是不夠的，不妨再看一個例子：給你一個m*n(m,n≤9)的矩陣，每個格子有一個價值，要求找一個連通塊使得該連通塊內所有格子的價值之和最大．按從上到下的順序依次考慮每個格子選還是不選，下列圖為一個極端情況，其中黑色的格子為所選的連通塊．只考慮前5行的時候，所有的黑色格子形成了三個連通塊，而最后所有的黑色格子形成一個連通塊．如果狀態中只單純地記錄前一行或前幾行的格子選還是不選，是無法準確描述這個狀態的，因此壓縮的狀態中我們需要增加一維，記錄假設干個格子之間的連通情況．我們把這一類必須要在狀態中記錄假設干個元素之間的連通信息的問題稱為基于連通性狀態壓縮的動態規劃問題．本文著重對這類問題進行研究．連通是圖論中一個非常重要的概念，在一個無向圖中，如果兩個頂點之間存在一條路徑，那么稱這兩個點連通．而基于連通性狀態壓縮的動態規劃問題與圖論模型有著密切的關聯，比方后文涉及到的哈密爾頓回路、生成樹等等．通常這類問題的本身與連通性有關或者隱藏著連通信息．全文共有六個章節．第一章，問題的一般解法，介紹解決基于連通性狀態壓縮的動態規劃問題的一般思路和解題技巧；第二章，一類簡單路徑問題，介紹一類基于棋盤模型的簡單路徑問題的狀態表示的改良——括號表示法以及提出廣義的括號表示法；第三章，一類棋盤染色問題，介紹解決一類棋盤染色問題的一般思路；第四章，一類基于非棋盤模型的問題，介紹解決一類非棋盤模型的連通性狀態壓縮問題的一般思路；第五章，一類最優性問題的剪枝技巧，本章的重點是優化，探討如何通過剪枝來減少擴展的狀態的總數從而提高算法的效率；第六章，總結，回憶前文，總結解題方法．【正文】一.問題的一般解法基于連通性狀態壓縮的動態規劃問題通常具有一個比擬固定的模式，幾乎所有的題目都是在這個模式的根底上變形和擴展的．本章選取了一個有代表性的例題來介紹這一類問題的一般解法．【例1】Formula1Ural1519,TimusTopCoders:ThirdChallengeUral1519,TimusTopCoders:ThirdChallenge問題描述給你一個m*n的棋盤，有的格子是障礙，問共有多少條回路使得經過每個非障礙格子恰好一次．m,n≤12．如圖，m=n=4，(1,1),(1,2)是障礙，共有2條滿足要求的回路．算法分析【劃分階段】這是一個典型的基于棋盤模型的問題，棋盤模型的特殊結構，使得它成為連通性狀態壓縮動態規劃問題最常見的“舞臺〞．通常來說，棋盤模型有三種劃分階段的方法：逐行，逐列，逐格．顧名思義，逐行即從上到下或從下到上依次考慮每一行的狀態，并轉移到下一行；逐列即從左到右或從右到左依次考慮每一列的狀態，并轉移到下一列；逐格即按一定的順序(如從上到下，從左到右)依次考慮每一格的狀態，并轉移到下一個格子．對于此題來說，逐行遞推和逐列遞推根本類似有的題目,逐行遞推和逐列遞推的狀態表示有較大的區別,比方本文后面會講到的RocketMania一題，接下來我們會對逐行遞推和逐格遞推的狀態確立，狀態轉移以及程序實現一一介紹．有的題目,逐行遞推和逐列遞推的狀態表示有較大的區別,比方本文后面會講到的RocketMania一題【確立狀態】先提出一個非常重要的概念——“插頭〞．對于一個4連通的問題來說，它通常有上下左右4個插頭，一個方向的插頭存在表示這個格子在這個方向可以與外面相連．此題要求回路的個數，觀察可以發現所有的非障礙格子一定是從一個格子進來，另一個格子出去，即4個插頭恰好有2個插頭存在，共6種情況．逐行遞推不妨按照從上到下的順序依次考慮每一行．分析第i行的哪些信息對第i+1行有影響：我們需要記錄第i行的每個格子是否有下插頭，這決定了第i+1行的每個格子是否有上插頭．僅僅記錄插頭是否存在是不夠的，可能導致出現多個回路(如右圖)，而此題要求一個回路，也就隱含著最后所有的非障礙格子通過插頭連接成了一個連通塊，因此還需要記錄第i行的n個格子的連通情況．插頭：0011插頭：1111插頭：1001從左到右,0表示無插頭,1表示有插頭連通性：(3,4)連通性：(1,2)(3,4)連通性：(1,2,3,4)括號內的數表示的是格子的列編號,一個括號內的格子屬于一個連通塊括號內的數表示的是格子的列編號,一個括號內的格子屬于一個連通塊我們稱圖中的藍線為輪廓線，任何時候只有輪廓線上方與其直接相連的格子和插頭才會對輪廓線以下的格子產生直接的影響．通過上面的分析，可以寫出動態規劃的狀態：表示前i行，第i行的n個格子是否具有下插頭的一個n位的二進制數為，第i行的n個格子之間的連通性為的方案總數．如何表示n個格子的連通性呢?通常給每一個格子標記一個正數，屬于同一個的連通塊的格子標記相同的數．比方{1,1,2,2}和{2,2,1,1}都表示第1,2個格子屬于一個連通塊，第3,4個格子屬于一個連通塊．為了防止出現同一個連通信息有不同的表示，一般會使用最小表示法．一種最小表示法為：所有的障礙格子標記為0，第一個非障礙格子以及與它連通的所有格子標記為1，然后再找第一個未標記的非障礙格子以及與它連通的格子標記為2，……，重復這個過程，直到所有的格子都標記完畢．比方連通信息((1,2,5),(3,6),(4))表示為{1,1,2,3,1,2}．還有一種最小表示法，即一個連通塊內所有的格子都標記成該連通塊最左邊格子的列編號，比方上面這個例子，我們表示為{1,1,3,4,1,3}．兩種表示方法在轉移的時候略有不同，本文后面將會提到因為第一種表示法更加直觀,本文如果不作特殊說明,默認使用第一種最小表示法．如上圖三個狀態我們可以依次表示為，，．因為第一種表示法更加直觀,本文如果不作特殊說明,默認使用第一種最小表示法狀態表示的優化通過觀察可以發現如果輪廓線上方的n個格子中某個格子沒有下插頭，那么它就不會再與輪廓線以下的格子直接相連，它的連通性對輪廓線以下的格子不會再有影響，也就成為了“冗余〞信息．不妨將記錄格子的連通性改成記錄插頭的連通性，如果這個插頭存在，那么就標記這個插頭對應的格子的連通標號，如果這個插頭不存在，那么標記為0．這樣狀態就從精簡為，上圖三個狀態表示為，，．優化后不僅狀態表示更加簡單，而且狀態總數將會大大減少．逐格遞推按照從上到下，從左到右的順序依次考慮每一格．分析轉移完(i,j)這個格子后哪些信息對后面的決策有影響：同樣我們可以刻畫出輪廓線，即輪廓線上方是已決策格子，下方是未決策格子．由圖可知與輪廓線直接相連的格子有n個，直接相連的插頭有n+1個，包括n個格子的下插頭以及(i,j)的右插頭．為了保持輪廓線的“連貫性〞，不妨從左到右依次給n個格子標號，n+1個插頭標號．類似地，我們需要記錄與輪廓線直接相連的n+1個插頭是否存在以及n個格子的連通情況．通過上面的分析，很容易寫出動態規劃的狀態：表示當前轉移完(i,j)這個格子，n+1個插頭是否存在表示成一個n+1位的二進制數S0，以及n個格子的連通性為S1的方案總數．逐行遞推的時候我們提到了狀態的優化，同樣地，我們也可以把格子的連通性記錄在插頭上，新的狀態為，上圖3個狀態依次為，，．【轉移狀態】狀態的轉移開銷主要包含兩個方面：每個狀態轉移的狀態數，計算新的狀態的時間．逐行遞推假設從第i行轉移到第i+1行，我們需要枚舉第i+1行的每個格子的狀態(共6種情況)，對于任何一個非障礙格子，它是否有上插頭和左插頭，因此最多只有2種情況，狀態的轉移數≤2n．枚舉完第i+1行每個格子的狀態后，需要計算第i+1行n個格子之間的連通性的最小表示，通常可以使用并查集的Father數組對其重新標號或者重新執行一次BFS/DFS，時間復雜度為O(n)，最后將格子的連通性轉移到插頭的連通性上．特別需要注意的是在轉移的過程中，為了防止出現多個連通塊，除了最后一行，任何時候一個連通分量內至少有一個格子有下插頭．逐格遞推仔細觀察下面這個圖，當轉移到時，輪廓線上n個格子只有(i-1,j)被改成(i,j)，n+1個插頭只有2個插頭被改動，即(i,j-1)的右插頭修改成(i,j)的下插頭和(i-1，j)的下插頭修改成(i,j)的右插頭．轉移的時候枚舉(i,j)的狀態分情況討論．一般棋盤模型的逐格遞推轉移有3類情況：新建一個連通分量，合并兩個連通分量，以及保持原來的連通分量．下面針對此題進行分析：ConditionIConditionIConditionIIIConditionII情況1新建一個連通分量，這種情況出現在(i,j)有右插頭和下插頭．新建的兩個插頭連通且不與其它插頭連通，這種情況下需要將這兩個插頭連通分量標號標記成一個未標記過的正數，重新O(n)掃描保證新的狀態滿足最小表示．情況2合并兩個連通分量，這種情況出現在(i,j)有上插頭和左插頭．如果兩個插頭不連通，那么將兩個插頭所處的連通分量合并，標記相同的連通塊標號，O(n)掃描保證最小表示；如果已經連通，相當于出現了一個回路，這種情況只能出現在最后一個非障礙格子．情況3保持原來的連通分量，這種情況出現在(i,j)的上插頭和左插頭恰好有一個，下插頭和右插頭也恰好有一個．下插頭或右插頭相當于是左插頭或上插頭的延續，連通塊標號相同，并且不會影響到其他的插頭的連通塊標號，計算新的狀態的時間為O(1)．注意當從一行的最后一個格子轉移到下一行的第一個格子的時候，輪廓線需要特殊處理．值得一提的是，上面三種情況計算新的狀態的時間分別為O(n),O(n),O(1)，如果使用前面提到的第二種最小表示方法，情況1只需要O(1)，但是情況3可能需要O(n)重新掃描．比擬一下逐行遞推和逐格遞推的狀態的轉移，逐行遞推的每一個轉移的狀態總數為指數級，而逐格遞推為O(1)，每次計算新的狀態的時間兩者最壞情況都為O(n)，但是逐行遞推的常數要比逐格遞推大，從轉移開銷這個角度來看，逐格遞推的優勢是毋庸置疑的．【程序實現】逐行遞推和逐格遞推的程序實現根本一致，下面以逐格遞推為例來說明．首先必須解決的一個問題是，對于像這樣的一個狀態我們該如何存儲，可以開一個長度為n+1的數組來存取n+1個插頭的連通性，但是數組判重并不方便，而且空間較大．不妨將n+1個元素進行編碼，用一個或幾個整數來存儲，當我們需要取一個狀態出來對它進行修改的時候再進行解碼．編碼最簡單的方法就是表示成一個n+1位的p進制數，p可以取能夠到達的最大的連通塊標號加1因為還要把0留出來存沒有插頭的情況，對此題來說，最多出現個連通塊，不妨取p=7．在不會超過數據類型的范圍的前提下，建議將p改成2的冪，因為位運算比普通的運算要快很多，此題最好采用8進制來存儲．因為還要把0留出來存沒有插頭的情況如需大范圍修改連通塊標號，最好將狀態O(n)解碼到一個數組中，修改后再O(n)計算出新的p進制數，而對于只需要局部修改幾個標號的情況下，可以直接用(xdivpi-1)modp來獲取第i位的狀態，用直接對第i位進行修改．最后我們探討一下實現的方法，一般有兩種方法：1．對所有可能出現的狀態進行編碼，枚舉編碼方式：預處理將所有可能的連通性狀態搜索出來，依次編號1,2,3,…,Tot，那么狀態為表示轉移完(i,j)后輪廓線狀態編號為k的方案總數．將所有狀態存入Hash表中，使得每個狀態與編號一一對應，程序框架如下：ForiFori←1tomForj←1tonFork←1toTotForx←(i,j,State[k])的所有轉移后的狀態←狀態x的編號，為的后繼格子．EndForQueue.Push(所有初始狀態)WhilenotEmpty(Queue)Queue.Push(所有初始狀態)WhilenotEmpty(Queue)p←Queue.Pop()Forx←p的所有轉移后的狀態Ifx之前擴展過ThenSum[x]←Sum[x]+Sum[p]Else Queue.Push(x)Sum[x]←Sum[p]EndIfEndForEndWhile比擬上述兩種實現方法，直接編碼的方法實現簡單，結構清晰，但是有一個很大的缺點：無效狀態可能很多，導致了很屢次空循環，而大大影響了程序的效率．下面是一組實驗的比擬數據：表1．直接編碼與寬度優先搜索擴展狀態總數比擬測試數據寬度優先搜索擴展狀態總數直接編碼TotTot*m*n無效狀態比率m=9,n=9(1,1)為障礙30930218817722882.5%m=10,n=10無障礙134011579857980076.8%m=11,n=11(1,1)為障礙33326415511187683182.2%m=12,n=12無障礙133311341835602424077.9%可以看出直接編碼擴展的無效狀態的比率非常高，對于障礙較多的棋盤其比照更加明顯，因此通常來說寬度優先搜索擴展比直接編碼實現效率要高．Hash判重的優化：使用一個HashSize較小的Hash表，每轉移一個(i,j)清空一次，每次判斷狀態x是否擴展過的程序效率比用一個HashSize較大的Hash表每次判斷狀態(i,j,x)高很多．類似地，在不需要記錄路徑的情況下，也可以使用滾動的擴展隊列來代替一個大的擴展隊列．最后我們比擬一下，不同的實現方法對程序效率的影響測試環境:測試環境:IntelCore2DuoT7100,,1G內存Program1：8-Based，枚舉編碼方式．Program2：8-Based，隊列擴展，HashSize=3999997．Program3：8-Based，隊列擴展，HashSize=4001，Hash表每次清空．Program4：7-Based，隊列擴展，HashSize=4001，Hash表每次清空．表2．不同的實現方法的程序效率的比擬測試數據Program1Program2Program3Program4m=10,n=10無障礙棋盤46ms31ms15ms31msm=11,n=11(1,1)為障礙140ms499ms109ms187msm=12,n=12無障礙624ms1840ms499ms873ms小結本章從劃分階段，確立狀態，狀態轉移以及程序實現四個方面介紹了基于連通性狀態壓縮動態規劃問題的一般解法，并在每個方面歸納了一些不同的方法，最后對不同的算法的效率進行比擬．在平時的解題過程中我們要學會針對題目的特點和數據規模“對癥下藥〞，選擇最適宜的方法而到達最好的效果．由于逐格遞推的轉移開銷比逐行遞推小很多，下文如果不作特殊說明，我們都采用逐格的階段劃分．二.一類簡單路徑問題這一章我們會針對一類基于棋盤模型的簡單回路和簡單路徑問題的解法作一個探討．簡單路徑，即除了起點和終點可能相同外，其余頂點均不相同的路徑，而簡單回路為起點和終點相同的簡單路徑．Formula1是一個典型的棋盤模型的簡單回路問題，這一章我們繼續以這個題為例來說明．首先我們分析一下簡單回路問題有什么特點：仔細觀察上面的圖，可以發現輪廓線上方是由假設干條互不相交的路徑構成的，而每條路徑的兩個端口恰好對應了輪廓線上的兩個插頭!一條路徑上的所有格子對應的是一個連通塊，而每條路徑的兩個端口對應的兩個插頭是連通的而且不與其他任何一個插頭連通．在上一章我們提到了逐格遞推轉移的時候的三種情況：新建一個連通分量，合并兩個連通分量，保持原來的連通分量，它們分別等價于兩個插頭成為了一條新的路徑的兩端，兩條路徑的兩個端口連接起來形成一條更長的路徑或一條路徑的兩個端口連接起來形成一個回路以及延長原來的路徑．通過上面的分析我們知道了簡單回路問題一定滿足任何時候輪廓線上每一個連通分量恰好有2個插頭，那么這些插頭之間有什么性質呢?【性質】輪廓線上從左到右4個插頭a,b,c,d，如果a,c連通，并且與b不連通，那么b,d一定不連通．dcdcab這個性質對所有的棋盤模型的問題都適用．“兩兩匹配〞，“不會交叉〞這樣的性質，我們很容易聯想到括號匹配．將輪廓線上每一個連通分量中左邊那個插頭標記為左括號，右邊那個插頭標記為右括號，由于插頭之間不會交叉，那么左括號一定可以與右括號一一對應．這樣我們就可以使用3進制——0表示無插頭，1表示左括號插頭，2表示右括號插頭記錄下所有的輪廓線信息．不妨用#表示無插頭，那么上面的三幅圖分別對應的是(())#()，(()#)()，(()###)，即，我們稱這種狀態的表示方法為括號表示法．依然分三類情況來討論狀態的轉移：為了表達方便，不妨稱(i,j-1)的右插頭為p，(i-1,j)的下插頭為q，(i,j)的下插頭為，右插頭為，那么每次轉移相當于輪廓線上插頭p的信息修改成的信息，插頭q的信息修改成的信息，設W(x)=0,1,2表示插頭x的狀態．情況1新建一個連通分量，這種情況下W(p)=0，W(q)=0，，兩個插頭構建了一條新的路徑，相當于為左括號，為右括號，即←1，←2，計算新的狀態的時間為O(1)．情況2合并兩個連通分量，這種情況下W(p)>0，W(q)>0，←0，←0，根據p,q為左括號還是右括號分四類情況討論：W(p)=1，W(q)=1．那么需要將q這個左括號與之對應的右括號v修改成左括號，即W(v)←1．W(p)=2，W(q)=2．那么需要將p這個右括號與之對應的左括號v修改成右括號，即W(v)←2．qqpv()qp(v)W(p)=1，W(q)=2，那么p和q是相對應的左括號和右括號，連接p,q相當于將一條路徑的兩端連接起來形成一個回路，這種情況下只能出現在最后一個非障礙格子．W(p)=2，W(q)=1，那么p和q連接起來后，p對應的左括號和q對應的右括號恰好匹配，不需要修改其他的插頭的狀態．ppqpq()O(nO(1)．情況3保持原來的連通分量，W(p)，W(q)中恰好一個為0，，中也恰好一個為0．那么無論，中哪個插頭存在，都相當于是p,q中那個存在的插頭的延續，括號性質一樣，因此←W(p)+W(q)，←0或者←W(p)+W(q)，←0．計算新的狀態的時間復雜度為O(1)．通過上面的分析可以看出，括號表示法利用了簡單回路問題的“一個連通分量內只有2個插頭〞的特殊性質巧妙地用3進制狀態存儲下完整的連通信息，插頭的連通性標號相對獨立，不再需要通過O(n)掃描大范圍修改連通性標號．實現的時候，我們可以用4進制代替3進制而提高程序運算效率，下面對最小表示法與括號表示法的程序效率進行比擬：表3．不同的狀態表示的程序效率的比擬測試數據最小表示法7Based最小表示法8Based括號表示法3Based括號表示法4Basedm=10,n=10無障礙棋盤31ms15ms0ms0msm=11,n=11(1,1)為障礙187ms109ms46ms31msm=12,n=12無障礙873ms499ms265ms140ms可以看出，括號表示法的優勢非常明顯，加上它的思路清晰自然，實現也更加簡單，因此對于解決這樣一類簡單回路問題是非常有價值的．類似的問題還有：NWERC2004Pipes，Hnoi2004Postman，Hnoi2007Park，還有一類非回路問題也可以通過棋盤改造后用簡單回路問題的方法解決，比方POJ1739Tony’sTour：給一個m*n棋盤，有的格子是障礙，要求從左下角走到右下角，每個格子恰好經過一次，問方案總數．(m,n≤8)只需要將棋盤改造一下，問題就等價于Formula1了．#..改造成.#####.....##..#介紹完簡單回路問題的解法，那么一般的簡單路徑問題又如何解決呢?【例2】Formula2改編自Formula1改編自Formula1問題描述給你一個m*n的棋盤，有的格子是障礙，要求從一個非障礙格子出發經過每個非障礙格子恰好一次，問方案總數．m,n≤10．如圖，一個2*2的無障礙棋盤，共有4條滿足要求的路徑．算法分析確立狀態：按照從上到下，從左到右依次考慮每一個格子，設表示轉移完(i,j)這個格子，輪廓線狀態為S的方案總數．如果用一般的最小表示法，不僅需要記錄每個插頭的連通情況，還需要額外記錄每個插頭是否連接了路徑的一端，狀態表示相當復雜．依然從括號表示法這個角度來思考如何來存儲輪廓線的狀態：這個問題跟簡單回路問題最大的區別為：不是所有的插頭都兩兩匹配，有的插頭連接的路徑的另一端不是一個插頭而是整條路徑的一端，我們稱這樣的插頭為獨立插頭．不妨將原來的3進制狀態修改成4進制——0表示無插頭，1表示左括號插頭，2表示右括號插頭，3表示獨立插頭，這樣我們就可以用4進制完整地記錄下輪廓線的信息，圖中狀態表示為(1203)4．狀態轉移：依然設(i,j-1)的右插頭為p，(i-1,j)的下插頭為q，(i,j)的下插頭為，右插頭為．局部轉移同簡單回路問題完全一樣，這里不再贅述，下面分三類情況討論與獨立插頭有關的轉移：情況1W(p)=0，W(q)=0．當前格子可能成為路徑的一端，即右插頭或下插頭是獨立插頭，因此←3，←0或者←3，←0．情況2W(p)>0，W(q)>0，那么←0，←0情況2.1W(p)=3，W(q)=3，將插頭p和q連接起來就相當于形成了一條完整的路徑，這種情況只能出現在最后一個非障礙格子．情況2.2W(p)，W(q)中有一個為3，如果p為獨立插頭，那么無論q是左括號插頭還是右括號插頭，與q相匹配的插頭v成為了獨立插頭，因此，W(v)←3．如果q為獨立插頭，類似處理．情況3W(p)，W(q)中有一個>0，即p,q中有一個插頭存在．情況3.1如果這個插頭為獨立插頭，假設在最后一個非障礙格子，這個插頭可以成為路徑的一端，否那么可以用右插頭或下插頭來延續這個獨立插頭．情況3.2如果這個插頭是左括號或右括號，那么我們以將這個插頭“封住〞，使它成為路徑的一端，需要將這個插頭所匹配的另一個插頭的狀態修改成為獨立插頭．情況2.2,3.2需要計算某個左括號或右括號與之匹配的括號，計算新的狀態的時間復雜度為O(n)，其余情況計算新的狀態的時間復雜度為O(1)．特別需要注意，任何時候輪廓線上獨立插頭的個數不可以超過2個．至此問題完整解決，m=n=10的無障礙棋盤，擴展的狀態總數為3493315，完全可以承受．上面兩類題目我們用括號表示法取得了很不錯的效果，但是它存在一定的局限性，即插頭必須滿足兩兩匹配．那么對于更加一般的問題，一個連通分量內出現大于2個插頭，上述的括號表示方法顯得束手無策．下面將介紹一種括號表示法的變形，它可以適用于出現連通塊內大于2個插頭的問題，我們稱之為廣義的括號表示法：假設一個連通分量從左到右有多個插頭，不妨將最左邊的插頭標記為“(〞，最右邊的插頭標記為“)〞，中間的插頭全部標記為“)(〞，那么能夠匹配的括號對應的插頭連通．如果問題中可能出現一個連通分量只有一個插頭，那么這個插頭標記為“()〞，這樣插頭之間的連通性可用括號序列完整地記錄下來，比方對于一個連通性狀態為{1,2,2,3,4,3,2,1}，我們可以用(-(-)(-(-()-)-)-)記錄．這種廣義的括號表示方法需要用4進制甚至5進制存儲狀態，而且直接對狀態連通性進行修改情況非常多，最好還是將狀態進行解碼，修改后再重新編碼．下文我們將會運用廣義的括號表示法解決一些具體的問題．小結本章針對一類簡單路徑問題，提出了一種新的狀態表示方法——括號表示法，最后提出了廣義的括號表示方法．相比普通的最小表示法，括號表示法巧妙地把連通塊與括號匹配一一對應，使得狀態更加簡單明了，雖然不會減少擴展的狀態總數，但是轉移開銷的常數要小很多，是一個不錯的方法．三.一類棋盤染色問題有一類這樣的問題——給你一個m*n的棋盤，要求給每個格子染上一種顏色(共k種顏色)，每種顏色的格子相互連通(4連通)．本章主要對這類問題的解法進行探討，我們從一個例題說起：【例3】Black&WhiteSource:Uva10572Source:Uva10572問題描述一個m*n的棋盤，有的格子已經染上黑色或白色，現在要求將所有的未染色格子染上黑色或白色，使得滿足以下2個限制：所有的黑色的格子是連通的，所有的白色格子也是連通的．不會有一個2*2的子矩陣的4個格子的顏色全部相同．問方案總數．(m,n≤8)如下列圖，m=2，n=3，灰色格子為未染色格子，共有9種染色方案．算法分析這是一個典型的棋盤染色問題，著色規那么有：1)只有黑白兩種顏色，即k=2，并且同色的格子互相連通．2)沒有同色的2*2的格子．對于簡單路徑問題來說，相鄰的格子是否連通取決于它們之間的插頭是否存在，狀態記錄輪廓線上每個插頭是否存在以及插頭之間的連通性；而棋盤染色問題相鄰的格子是否連通取決于它們的顏色是否相同，這就需要記錄輪廓線上方n個格子的顏色以及格子之間的連通性．確立狀態設當前轉移完Q(i,j)這個格子，對以后的決策產生影響的信息有：輪廓線上方n個格子的染色情況以及它們的連通性，由第2條著色規那么“沒有同色的2*2的格子〞可知P(i-1,j)的顏色會影響到(i,j+1)著色，因此我們還需要額外記錄格子的顏色．動態規劃的狀態為：表示轉移完(i,j)，輪廓線上從左到右n個格子的染色情況為S0(0≤S0<2n)，連通性狀態為S1，格子的顏色為cp(0或1)的方案總數．狀態的精簡如果相鄰的2個格子不屬于同一個連通塊，那么它們必然不同色，因此只需要記錄(i,1)和(i-1,j+1)兩個格子的顏色，利用S1就可以推出n個格子的顏色．這個精簡不會減少狀態的總數，仍然需要一個變量來記錄兩個格子的顏色，因此意義并不大，這里只是提一下．狀態轉移枚舉當前格子(i,j)的顏色，計算新的狀態：S0和cp都很容易O(1)計算出來．考慮計算S1：輪廓線的變化相當于將記錄(i-1,j)的連通性改成記錄(i,j)的連通性．根據當前格子與上面的格子和左邊的格子是否同色分四類情況討論．應當注意的是如果(i,j)和(i-1,j)不同色，并且(i-1,j)在輪廓線上為一個單獨的一個連通塊，那么(i-1,j)以后都不可能與其他格子連通，即剩余的格子都必須染上與(i-1,j)相反的顏色，需要特殊判斷．轉移的時間復雜度為O(n)．計算新狀態的S1程序框架如下：將前一個狀態的S1解碼，連通性存入c[1],c[2],…,c[n]．If(i,j)與(i-1,j)不同色并且(i-1,j)為一個單獨的連通塊Then特殊判斷ElseIf(i,j)與(i-1,j)和(i,j-1)均同色ThenFork←1tonIfc[k]=c[j]Then c[k]←c[j-1]//合并兩個連通塊EndIfElseIf(i,j)與(i-1,j)和(i,j-1)均不同色Thenc[j]←最大可能出現的連通塊標號//(i,j)新建一個連通塊．ElseIf(i,j)與(i,j-1)同色與(i-1,j)不同色Thenc[j]←c[j-1]//(i,j)的連通性標號跟(i,j-1)相同．EndIfEndIfEndIfEndIf對c[]O(n)掃描，修改成最小表示，利用c[]編碼計算出新的S1．對于m=n=8的一個全部未染色的棋盤，擴展出來的狀態總數為122395，轉移需要時間為O(n)，因此總的時間復雜度為O(TotalState*ns．至此問題完整解決．類似可以解決的問題還有2007年重慶市選拔賽Rect和IPSC2007DeliciousCake．擴展上面提到的是4連通問題，如果要求8連通呢?4連通問題是兩個格子至少有一條邊重合為連通，而8連通問題是兩個格子至少有一個頂點重合為連通，因此需要記錄所有至少有一個頂點在輪廓線上的格子的連通和染色情況，即包括(i-1,j)在內的n+1個格子．一個優化的方向擴展的狀態中無效狀態的總數很大程度上決定了算法的效率．比方Black&White中如果出現右圖的狀態，那么無論之后如何決策，都不可能滿足同色的格子互相連通的性質，因此它是一個無效狀態．對于任何一個k染色棋盤問題，如果從左到右有4個相互不嵌套“嵌套〞的概念可以用廣義的括號匹配的表示方法來理解的連通塊a,b,c,d，a,c同色,b,d同色且與a,c不同色，那么這個狀態為無效狀態．“嵌套〞的概念可以用廣義的括號匹配的表示方法來理解小結本章介紹了解決一類棋盤染色問題的一般思路．無論染色規那么多么復雜，我們只要在根本狀態即“輪廓線上方與其相連的格子的連通性以及染色情況〞的根底上，根據題目的需要在狀態中增加對以后的決策可能產生影響的信息，問題都可以迎刃而解了．四.一類基于非棋盤模型的問題本章將會介紹一類基于非棋盤模型的連通性狀態壓縮動態規劃問題，它雖然不具有棋盤模型的特殊結構，但是解法的核心思想又跟棋盤模型的問題有著異曲同工之處．【例4】生成樹計數Source:Noi2007Day2生成樹計數,CountSource:Noi2007Day2生成樹計數,Count問題描述給你一個n個點的無向連通圖，其邊集為：任何兩個不同的點i,j(1≤i,j≤n)，如果|i-j|≤k，那么有一條無向邊<i,j>．n和k，求這個圖的生成樹個數．n≤1015，2≤k≤5．算法分析這個題給我們的第一印象是：n非常大，k卻非常小．生成樹最重要的兩個性質：無環，連通．那么如果按照1,2,…,n的順序依次考慮每一個點與前面的哪些點相連，并且保證任何時候都不會出現環，最后統計所有的點全部在一個連通分量內的方案總數即為最終的答案．在棋盤模型的問題中，我們提出了輪廓線這個概念，任何時候只有輪廓線上方與其直接相連的格子對以后的決策會產生影響．類似地我們分析一下這個問題，當我們確定了1~i的所有點的連邊情況后，哪些信息對以后的決策會產生影響：1~i–k這些點與i之后的點一定沒有邊相連，那么對i以后的點的決策不會產生直接的影響，因此我們需要記錄的僅僅是i-k+1~i這k個點的連通信息!如下列圖，我們不妨也稱藍線為輪廓線，因為只有輪廓線上的點的信息會對輪廓線右邊的點的決策產生直接的影響．這樣我們就很容易確立狀態：設表示考慮完前i個點的連邊情況后，i-k+1..i這k個點的連通情況為S.轉移狀態：O(2k)依次枚舉點i與i-1，…，i-k這k個點是否相連．轉移的時候需要注意：i-1,…,i-k這k個點，任何一個連通塊，i最多只能與其中的一個點相連，這樣可以防止環的出現．如果i-k在輪廓線上為一個單獨的連通塊，那么i必然與i-k相連，這樣可以防止出現孤立的連通塊．比方對于一個k=5的狀態來說，如果點i與i-2和i-1相連，那么新的狀態為．這樣我們就可以在O(2k*k)的時間復雜度內完成狀態的轉移．算法實現：設Tk表示k個點的本質不同的連通情況的個數，搜索可知T5=52．動態規劃的時間復雜度為O(n*Tk*2k*k)，依然太大．可以發現當i≥k，狀態是否可以轉移到只與有關，這樣我們就可以用矩陣乘法實現動態規劃加速，由于這不是本文的重點，這里不再詳細介紹．最終的時間復雜度為O(Tk3*log2n)，對于k=5,Tk=52的數據規模來說已經完全可以承受了，至此問題完整解決．此題中的無向圖非常特殊，每個點只和距離它不超過k的點有邊相連，并且k非常小．對于棋盤模型的問題，可以抽象成一個特殊的無向圖——m*n個點，每個點只與它上下左右四個點有邊相連．那么對于一個與連通性有關的無向圖問題，無向圖具備怎樣的特點才可以用基于狀態壓縮的動態規劃來解決?分析以上幾個問題，不難發現它們有一個共同點：給無向圖中的點找一個序，在這個序中有邊相連的兩個點的距離不超過p(p很小)，這樣我們就可以以當前決策完序中前i個，最后p個點的連通性為狀態作動態規劃．棋盤模型的問題中序即為從上到下，從左到右或從左到右，從上到下，p為m或n，因此棋盤模型的問題m和n中至少有一個數會非常小．小結本章寫得比擬簡略，但是依然能夠給我們很多的啟示．處理這樣的一類非棋盤模型的問題，一般的思路是尋找某一個序依次考慮每個點的決策，并分析哪些信息對以后的決策會產生影響，找到問題中的“輪廓線〞，以輪廓線的信息來確立動態規劃的狀態．通常來說，輪廓線上的信息比擬少，這也是能夠作狀態壓縮動態規劃的根底，像此題中k≤5這樣的條件往往能成為解決問題的突破口．五.一類最優性問題的剪枝技巧基于連通性狀態壓縮的動態規劃問題的算法的效率主要取決于狀態的總數和轉移的開銷，減少狀態總數和降低轉移開銷成為了優化的核心內容．前面的章節我們提到了一些優化的技巧，這一章我們選取了一個非常有趣的題目RocketMania來介紹針對這樣的一類最優性問題，如何通過剪枝使狀態總數大大減少而提高算法效率．【例5】RocketManiaSource:Zju2125,OnlineContestofFantasyGameSource:Zju2125,OnlineContestofFantasyGame問題描述這個題目的背景是夢想游戲的“中國煙花〞：給你一個9*6的棋盤，棋盤的左邊有9根火柴，右邊有9個火箭．棋盤中的每一個格子可能是一個空格子也可能是一段管道，管道的類型有4種：L型—型T型十型一個火箭能夠被發射當且僅當存在一條由管道組成的從一根點燃的火柴到這個火箭的路徑．給你棋盤的初始狀態以及X，你的目標是旋轉每個格子內的管道0，90，180或270度，使得當點燃左邊第X根火柴后，被發射的火箭個數盡可能多．算法分析確立狀態：按照從左到右，從上到下的順序依次考慮每一個格子，我們需要記錄每個插頭是否已經點燃以及它們之間的連通情況．因此狀態為表示轉移完(i,j)，輪廓線上10個插頭的連通性為S(把每個插頭是否存在記錄在S中),10個插頭是否被點燃的2進制數fired的狀態能否到達．那么最后的答案為所有可以到達的狀態中Ones[fired]的最大值，其中Ones[x]表示二進制數x的1的個數．狀態轉移：依次枚舉每一個格子的旋轉方式(最多4種)，根據當前格子是否可以與上面的格子和左邊的格子通過插頭連接起來分情況討論，O(m)掃描計算出新的狀態．前面的題目我們已經很詳細地介紹過棋盤模型的問題的轉移方法，這里不再贅述．如果直接按照上面的思路作動態規劃，Sample也需要運行>60s，實在令人無法滿意．優化，勢在必行．如何通過剪枝優化來減少擴展的狀態總數，盡可能舍去無效狀態成為了現在所面臨的問題：剪枝通常可以分為兩類：一．可行性剪枝，即將無論之后如何決策，都不可能滿足題目要求的狀態剪掉；二．最優性剪枝，即對于最優性問題，將不可能成為最優解的狀態給剪掉．我們從這兩個角度入手來考慮問題：剪枝一：如果輪廓線上所有的插頭全部都未被點燃，那么最后所有的火箭都不可能發射，所以這個狀態可以舍去．這個剪枝看上去非常顯然，對于大局部數據卻可以剪掉近乎一半的狀態．p剪枝二：如果輪廓線上有一個插頭p，它沒有被火柴點燃且沒有其它的插頭與它連通，那么這個插頭可以認為是“無效〞插頭．因為即使這個插頭所在的路徑以后會被點燃而可以發射某個火箭，那么一定存在另一條路徑可以不經過這個插頭而發射火箭，如圖．這種情況下將插頭設置為不存在．這是最重要的一個剪枝，大局部數據的狀態總數可以縮小七八倍，甚至十幾倍．p剪枝三：這是一個最優性問題，我們考慮最優性剪枝：對于一個格子(i,j)的兩個狀態，，如果第一個狀態的每一個存在的插頭在第二個狀態中不僅存在而且都被點燃，那么無論以后如何決策，第二個狀態點燃的火箭個數不會少于第一個狀態，這樣我們就可以果斷地舍去第一個狀態．對于每一個(i,j)，選擇Ones[Fired]最多的一個狀態Best，如果一個狀態一定不比Best好，就可以舍去．剪枝四：從邊界情況入手，邊界狀態非常