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

1、基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題長(zhǎng)沙市雅禮中學(xué) 陳丹琦【摘要】基于狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題是一類以集合信息為狀態(tài)且狀態(tài)總數(shù)為指數(shù)級(jí)的特殊的動(dòng)態(tài)規(guī)劃問題在狀態(tài)壓縮的基礎(chǔ)上，有一類問題的狀態(tài)中必須要記錄若干個(gè)元素的連通情況，我們稱這樣的問題為基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題，本文著重對(duì)這類問題的解法及優(yōu)化進(jìn)行探討和研究 本文主要從動(dòng)態(tài)規(guī)劃的幾個(gè)步驟劃分階段，確立狀態(tài)，狀態(tài)轉(zhuǎn)移以及程序?qū)崿F(xiàn)來介紹這類問題的一般解法，會(huì)特別針對(duì)到目前為止信息學(xué)競(jìng)賽中涌現(xiàn)出來的幾類題型的解法作一個(gè)探討結(jié)合例題，本文還會(huì)介紹作者在減少狀態(tài)總數(shù)和降低轉(zhuǎn)移開銷兩個(gè)方面對(duì)這類問題優(yōu)化的一些心得【關(guān)鍵詞】 狀態(tài)壓縮連通性括號(hào)表示法

2、輪廓線插頭棋盤模型 【目錄】【序言】3【正文】5一. 問題的一般解法5【例1】Formula 15問題描述5算法分析5小結(jié)11二. 一類簡(jiǎn)單路徑問題12【例2】Formula 215問題描述15算法分析15小結(jié)17三. 一類棋盤染色問題17【例3】Black & White17問題描述17算法分析18小結(jié)19四. 一類基于非棋盤模型的問題20【例4】生成樹計(jì)數(shù)20問題描述20算法分析20小結(jié)21五. 一類最優(yōu)性問題的剪枝技巧22【例5】Rocket Mania22問題描述22算法分析22小結(jié)25六.總結(jié)25【參考文獻(xiàn)】26【感謝】26【附錄】26【序言】先看一個(gè)非常經(jīng)典的問題旅行商問題(即TS

3、P問題，Traveling Salesman Problem)：一個(gè)n(15)個(gè)點(diǎn)的帶權(quán)完全圖，求權(quán)和最小的經(jīng)過每個(gè)點(diǎn)恰好一次的封閉回路這個(gè)問題已經(jīng)被證明是NP完全問題，那么對(duì)于這樣一類無(wú)多項(xiàng)式算法的問題，搜索算法是不是解決問題的唯一途徑呢? 答案是否定的不難發(fā)現(xiàn)任何時(shí)候我們只需要知道哪些點(diǎn)已經(jīng)被遍歷過而遍歷點(diǎn)的具體順序?qū)σ院蟮臎Q策是沒有影響的，因此不妨以當(dāng)前所在的位置i，遍歷過的點(diǎn)的集合S為狀態(tài)作動(dòng)態(tài)規(guī)劃： ，其中ji，i，j in S動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為，雖然為指數(shù)級(jí)算法，但是對(duì)于n = 15的數(shù)據(jù)規(guī)模來說已經(jīng)比樸素的的搜索算法高效很多了我們通常把這樣一類以一個(gè)集合內(nèi)的元素信息作為狀態(tài)且

4、狀態(tài)總數(shù)為指數(shù)級(jí)別的動(dòng)態(tài)規(guī)劃稱為基于狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃或集合動(dòng)態(tài)規(guī)劃基于狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題通常具有以下兩個(gè)特點(diǎn)：1數(shù)據(jù)規(guī)模的某一維或幾維非常??；2它需要具備動(dòng)態(tài)規(guī)劃問題的兩個(gè)基本性質(zhì)：最優(yōu)性原理和無(wú)后效性一般的狀態(tài)壓縮問題，壓縮的是一個(gè)小范圍內(nèi)每個(gè)元素的決策，狀態(tài)中元素的信息相對(duì)獨(dú)立而有些問題，僅僅記錄每個(gè)元素的決策是不夠的，不妨再看一個(gè)例子：給你一個(gè)m * n (m, n9) 的矩陣，每個(gè)格子有一個(gè)價(jià)值，要求找一個(gè)連通塊使得該連通塊內(nèi)所有格子的價(jià)值之和最大按從上到下的順序依次考慮每個(gè)格子選還是不選，下圖為一個(gè)極端情況，其中黑色的格子為所選的連通塊只考慮前5行的時(shí)候，所有的黑色格子形成了三

5、個(gè)連通塊，而最后所有的黑色格子形成一個(gè)連通塊如果狀態(tài)中只單純地記錄前一行或前幾行的格子選還是不選，是無(wú)法準(zhǔn)確描述這個(gè)狀態(tài)的，因此壓縮的狀態(tài)中我們需要增加一維，記錄若干個(gè)格子之間的連通情況我們把這一類必須要在狀態(tài)中記錄若干個(gè)元素之間的連通信息的問題稱為基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題本文著重對(duì)這類問題進(jìn)行研究連通是圖論中一個(gè)非常重要的概念，在一個(gè)無(wú)向圖中，如果兩個(gè)頂點(diǎn)之間存在一條路徑，則稱這兩個(gè)點(diǎn)連通而基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題與圖論模型有著密切的關(guān)聯(lián)，比如后文涉及到的哈密爾頓回路、生成樹等等通常這類問題的本身與連通性有關(guān)或者隱藏著連通信息全文共有六個(gè)章節(jié)第一章，問題的一般解法，介紹解決基

6、于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題的一般思路和解題技巧；第二章，一類簡(jiǎn)單路徑問題，介紹一類基于棋盤模型的簡(jiǎn)單路徑問題的狀態(tài)表示的改進(jìn)括號(hào)表示法以及提出廣義的括號(hào)表示法；第三章，一類棋盤染色問題，介紹解決一類棋盤染色問題的一般思路； 第四章，一類基于非棋盤模型的問題，介紹解決一類非棋盤模型的連通性狀態(tài)壓縮問題的一般思路；第五章，一類最優(yōu)性問題的剪枝技巧，本章的重點(diǎn)是優(yōu)化，探討如何通過剪枝來減少擴(kuò)展的狀態(tài)的總數(shù)從而提高算法的效率；第六章，總結(jié)，回顧前文，總結(jié)解題方法【正文】一. 問題的一般解法基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題通常具有一個(gè)比較固定的模式，幾乎所有的題目都是在這個(gè)模式的基礎(chǔ)上變形和擴(kuò)展的本

7、章選取了一個(gè)有代表性的例題來介紹這一類問題的一般解法【例1】Formula 1 Ural1519, Timus Top Coders : Third Challenge問題描述給你一個(gè)m * n的棋盤，有的格子是障礙，問共有多少條回路使得經(jīng)過每個(gè)非障礙格子恰好一次m, n 12 如圖，m = n = 4，(1, 1), (1, 2)是障礙，共有2條滿足要求的回路算法分析【劃分階段】 這是一個(gè)典型的基于棋盤模型的問題，棋盤模型的特殊結(jié)構(gòu)，使得它成為連通性狀態(tài)壓縮動(dòng)態(tài)規(guī)劃問題最常見的“舞臺(tái)”通常來說，棋盤模型有三種劃分階段的方法：逐行，逐列，逐格顧名思義，逐行即從上到下或從下到上依次考慮每一行的狀

8、態(tài)，并轉(zhuǎn)移到下一行；逐列即從左到右或從右到左依次考慮每一列的狀態(tài)，并轉(zhuǎn)移到下一列；逐格即按一定的順序(如從上到下，從左到右)依次考慮每一格的狀態(tài)，并轉(zhuǎn)移到下一個(gè)格子對(duì)于本題來說，逐行遞推和逐列遞推基本類似 有的題目, 逐行遞推和逐列遞推的狀態(tài)表示有較大的區(qū)別, 比如本文后面會(huì)講到的Rocket Mania一題，接下來我們會(huì)對(duì)逐行遞推和逐格遞推的狀態(tài)確立，狀態(tài)轉(zhuǎn)移以及程序?qū)崿F(xiàn)一一介紹【確立狀態(tài)】 先提出一個(gè)非常重要的概念“插頭”對(duì)于一個(gè)4連通的問題來說，它通常有上下左右4個(gè)插頭，一個(gè)方向的插頭存在表示這個(gè)格子在這個(gè)方向可以與外面相連本題要求回路的個(gè)數(shù)，觀察可以發(fā)現(xiàn)所有的非障礙格子一定是從一個(gè)格子

9、進(jìn)來，另一個(gè)格子出去，即4個(gè)插頭恰好有2個(gè)插頭存在，共6種情況逐行遞推 不妨按照從上到下的順序依次考慮每一行分析第i 行的哪些信息對(duì)第i + 1行有影響：我們需要記錄第i行的每個(gè)格子是否有下插頭，這決定了第i+1行的每個(gè)格子是否有上插頭僅僅記錄插頭是否存在是不夠的，可能導(dǎo)致出現(xiàn)多個(gè)回路 (如右圖)，而本題要求一個(gè)回路，也就隱含著最后所有的非障礙格子通過插頭連接成了一個(gè)連通塊，因此還需要記錄第i行的n個(gè)格子的連通情況 插頭：0011 插頭：1111 插頭：1001 從左到右, 0表示無(wú)插頭, 1表示有插頭連通性：(3,4) 連通性：(1,2) (3,4) 連通性：(1,2,3,4) 括號(hào)內(nèi)的數(shù)表

10、示的是格子的列編號(hào), 一個(gè)括號(hào)內(nèi)的格子屬于一個(gè)連通塊我們稱圖中的藍(lán)線為輪廓線，任何時(shí)候只有輪廓線上方與其直接相連的格子和插頭才會(huì)對(duì)輪廓線以下的格子產(chǎn)生直接的影響通過上面的分析，可以寫出動(dòng)態(tài)規(guī)劃的狀態(tài)：表示前i行，第i行的n個(gè)格子是否具有下插頭的一個(gè)n位的二進(jìn)制數(shù)為，第i行的n個(gè)格子之間的連通性為的方案總數(shù)如何表示n個(gè)格子的連通性呢? 通常給每一個(gè)格子標(biāo)記一個(gè)正數(shù)，屬于同一個(gè)的連通塊的格子標(biāo)記相同的數(shù)比如1,1,2,2和2,2,1,1都表示第1,2個(gè)格子屬于一個(gè)連通塊，第3,4個(gè)格子屬于一個(gè)連通塊為了避免出現(xiàn)同一個(gè)連通信息有不同的表示，一般會(huì)使用最小表示法一種最小表示法為：所有的障礙格子標(biāo)記為0

11、，第一個(gè)非障礙格子以及與它連通的所有格子標(biāo)記為1，然后再找第一個(gè)未標(biāo)記的非障礙格子以及與它連通的格子標(biāo)記為2，重復(fù)這個(gè)過程，直到所有的格子都標(biāo)記完畢比如連通信息(1,2,5),(3,6),(4)表示為1,1,2,3,1,2還有一種最小表示法，即一個(gè)連通塊內(nèi)所有的格子都標(biāo)記成該連通塊最左邊格子的列編號(hào)，比如上面這個(gè)例子，我們表示為1,1,3,4,1,3兩種表示方法在轉(zhuǎn)移的時(shí)候略有不同，本文后面將會(huì)提到因?yàn)榈谝环N表示法更加直觀, 本文如果不作特殊說明, 默認(rèn)使用第一種最小表示法如上圖三個(gè)狀態(tài)我們可以依次表示為，狀態(tài)表示的優(yōu)化 通過觀察可以發(fā)現(xiàn)如果輪廓線上方的n個(gè)格子中某個(gè)格子沒有下插頭，那么它就不

12、會(huì)再與輪廓線以下的格子直接相連，它的連通性對(duì)輪廓線以下的格子不會(huì)再有影響，也就成為了“冗余”信息不妨將記錄格子的連通性改成記錄插頭的連通性，如果這個(gè)插頭存在，那么就標(biāo)記這個(gè)插頭對(duì)應(yīng)的格子的連通標(biāo)號(hào)，如果這個(gè)插頭不存在，那么標(biāo)記為0這樣狀態(tài)就從精簡(jiǎn)為，上圖三個(gè)狀態(tài)表示為，優(yōu)化后不僅狀態(tài)表示更加簡(jiǎn)單，而且狀態(tài)總數(shù)將會(huì)大大減少逐格遞推 按照從上到下，從左到右的順序依次考慮每一格分析轉(zhuǎn)移完(i, j)這個(gè)格子后哪些信息對(duì)后面的決策有影響：同樣我們可以刻畫出輪廓線，即輪廓線上方是已決策格子，下方是未決策格子由圖可知與輪廓線直接相連的格子有n個(gè)，直接相連的插頭有n+1個(gè)，包括n個(gè)格子的下插頭以及(i, j

13、)的右插頭為了保持輪廓線的“連貫性”，不妨從左到右依次給n個(gè)格子標(biāo)號(hào)，n+1個(gè)插頭標(biāo)號(hào)類似地，我們需要記錄與輪廓線直接相連的n+1個(gè)插頭是否存在以及n個(gè)格子的連通情況通過上面的分析，很容易寫出動(dòng)態(tài)規(guī)劃的狀態(tài)：表示當(dāng)前轉(zhuǎn)移完(i, j)這個(gè)格子，n+1個(gè)插頭是否存在表示成一個(gè)n+1位的二進(jìn)制數(shù)S0，以及n個(gè)格子的連通性為S1的方案總數(shù) 逐行遞推的時(shí)候我們提到了狀態(tài)的優(yōu)化，同樣地，我們也可以把格子的連通性記錄在插頭上，新的狀態(tài)為，上圖3個(gè)狀態(tài)依次為，【轉(zhuǎn)移狀態(tài)】狀態(tài)的轉(zhuǎn)移開銷主要包含兩個(gè)方面：每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)，計(jì)算新的狀態(tài)的時(shí)間逐行遞推假設(shè)從第i行轉(zhuǎn)移到第i+1行，我們需要枚舉第i+1行的每個(gè)

14、格子的狀態(tài)(共6種情況)，對(duì)于任何一個(gè)非障礙格子，它是否有上插頭和左插頭已知，因此最多只有2種情況，狀態(tài)的轉(zhuǎn)移數(shù)2n枚舉完第i+1行每個(gè)格子的狀態(tài)后，需要計(jì)算第i+1行n個(gè)格子之間的連通性的最小表示，通?？梢允褂貌⒉榧腇ather數(shù)組對(duì)其重新標(biāo)號(hào)或者重新執(zhí)行一次BFS/DFS，時(shí)間復(fù)雜度為O(n)，最后將格子的連通性轉(zhuǎn)移到插頭的連通性上特別需要注意的是在轉(zhuǎn)移的過程中，為了避免出現(xiàn)多個(gè)連通塊，除了最后一行，任何時(shí)候一個(gè)連通分量?jī)?nèi)至少有一個(gè)格子有下插頭逐格遞推仔細(xì)觀察下面這個(gè)圖，當(dāng)轉(zhuǎn)移到時(shí)，輪廓線上n個(gè)格子只有(i-1, j)被改成(i, j)，n+1個(gè)插頭只有2個(gè)插頭被改動(dòng)，即(i, j-1)

15、的右插頭修改成(i, j)的下插頭和(i-1，j)的下插頭修改成(i, j)的右插頭轉(zhuǎn)移的時(shí)候枚舉(i, j)的狀態(tài)分情況討論一般棋盤模型的逐格遞推轉(zhuǎn)移有3類情況：新建一個(gè)連通分量，合并兩個(gè)連通分量，以及保持原來的連通分量下面針對(duì)本題進(jìn)行分析：Condition ICondition IIICondition II情況1 新建一個(gè)連通分量，這種情況出現(xiàn)在(i, j)有右插頭和下插頭新建的兩個(gè)插頭連通且不與其它插頭連通，這種情況下需要將這兩個(gè)插頭連通分量標(biāo)號(hào)標(biāo)記成一個(gè)未標(biāo)記過的正數(shù)，重新O(n)掃描保證新的狀態(tài)滿足最小表示情況2 合并兩個(gè)連通分量，這種情況出現(xiàn)在(i, j)有上插頭和左插頭如果兩

16、個(gè)插頭不連通，那么將兩個(gè)插頭所處的連通分量合并，標(biāo)記相同的連通塊標(biāo)號(hào)，O(n)掃描保證最小表示；如果已經(jīng)連通，相當(dāng)于出現(xiàn)了一個(gè)回路，這種情況只能出現(xiàn)在最后一個(gè)非障礙格子 情況3 保持原來的連通分量，這種情況出現(xiàn)在(i, j)的上插頭和左插頭恰好有一個(gè)，下插頭和右插頭也恰好有一個(gè)下插頭或右插頭相當(dāng)于是左插頭或上插頭的延續(xù)，連通塊標(biāo)號(hào)相同，并且不會(huì)影響到其他的插頭的連通塊標(biāo)號(hào)，計(jì)算新的狀態(tài)的時(shí)間為O(1)注意當(dāng)從一行的最后一個(gè)格子轉(zhuǎn)移到下一行的第一個(gè)格子的時(shí)候，輪廓線需要特殊處理值得一提的是，上面三種情況計(jì)算新的狀態(tài)的時(shí)間分別為O(n), O(n), O(1)，如果使用前面提到的第二種最小表示方法

17、，情況1只需要O(1)，但是情況3可能需要O(n)重新掃描比較一下逐行遞推和逐格遞推的狀態(tài)的轉(zhuǎn)移，逐行遞推的每一個(gè)轉(zhuǎn)移的狀態(tài)總數(shù)為指數(shù)級(jí)，而逐格遞推為O(1)，每次計(jì)算新的狀態(tài)的時(shí)間兩者最壞情況都為O(n)，但是逐行遞推的常數(shù)要比逐格遞推大，從轉(zhuǎn)移開銷這個(gè)角度來看，逐格遞推的優(yōu)勢(shì)是毋庸置疑的【程序?qū)崿F(xiàn)】逐行遞推和逐格遞推的程序?qū)崿F(xiàn)基本一致，下面以逐格遞推為例來說明首先必須解決的一個(gè)問題是，對(duì)于像這樣的一個(gè)狀態(tài)我們?cè)撊绾未鎯?chǔ)，可以開一個(gè)長(zhǎng)度為n+1的數(shù)組來存取n+1個(gè)插頭的連通性，但是數(shù)組判重并不方便，而且空間較大不妨將n+1個(gè)元素進(jìn)行編碼，用一個(gè)或幾個(gè)整數(shù)來存儲(chǔ)，當(dāng)我們需要取一個(gè)狀態(tài)出來對(duì)它進(jìn)

18、行修改的時(shí)候再進(jìn)行解碼編碼最簡(jiǎn)單的方法就是表示成一個(gè)n+1位的p進(jìn)制數(shù)，p可以取能夠達(dá)到的最大的連通塊標(biāo)號(hào)加1 因?yàn)檫€要把0留出來存沒有插頭的情況，對(duì)本題來說，最多出現(xiàn)個(gè)連通塊，不妨取p = 7在不會(huì)超過數(shù)據(jù)類型的范圍的前提下，建議將p改成2的冪，因?yàn)槲贿\(yùn)算比普通的運(yùn)算要快很多，本題最好采用8進(jìn)制來存儲(chǔ)如需大范圍修改連通塊標(biāo)號(hào)，最好將狀態(tài)O(n) 解碼到一個(gè)數(shù)組中，修改后再O(n)計(jì)算出新的p進(jìn)制數(shù)，而對(duì)于只需要局部修改幾個(gè)標(biāo)號(hào)的情況下，可以直接用(x div pi-1) mod p來獲取第i位的狀態(tài)，用直接對(duì)第i位進(jìn)行修改最后我們探討一下實(shí)現(xiàn)的方法，一般有兩種方法：1對(duì)所有可能出現(xiàn)的狀態(tài)進(jìn)行

19、編碼，枚舉編碼方式：預(yù)處理將所有可能的連通性狀態(tài)搜索出來，依次編號(hào)1, 2, 3, ,Tot，那么狀態(tài)為表示轉(zhuǎn)移完(i, j)后輪廓線狀態(tài)編號(hào)為k的方案總數(shù)將所有狀態(tài)存入Hash表中，使得每個(gè)狀態(tài)與編號(hào)一一對(duì)應(yīng)，程序框架如下：For i 1 to mFor j 1 to nFor k 1 to Tot For x (i, j, Statek) 的所有轉(zhuǎn)移后的狀態(tài) 狀態(tài)x的編號(hào)，為的后繼格子 End For2記憶化寬度優(yōu)先搜索：將初始狀態(tài)放入隊(duì)列中，每次取隊(duì)首元素進(jìn)行擴(kuò)展，并用Hash對(duì)擴(kuò)展出來的新的狀態(tài)判重程序框架如下： Queue.Push(所有初始狀態(tài)) While not Empty(Q

20、ueue) p Queue.Pop() For x p的所有轉(zhuǎn)移后的狀態(tài)If x之前擴(kuò)展過 Then Sum x Sumx + SumpElse Queue.Push(x)Sumx Sump End If End ForEnd While比較上述兩種實(shí)現(xiàn)方法，直接編碼的方法實(shí)現(xiàn)簡(jiǎn)單，結(jié)構(gòu)清晰，但是有一個(gè)很大的缺點(diǎn)：無(wú)效狀態(tài)可能很多，導(dǎo)致了很多次空循環(huán)，而大大影響了程序的效率下面是一組實(shí)驗(yàn)的比較數(shù)據(jù)：表1直接編碼與寬度優(yōu)先搜索擴(kuò)展?fàn)顟B(tài)總數(shù)比較測(cè)試數(shù)據(jù)寬度優(yōu)先搜索擴(kuò)展?fàn)顟B(tài)總數(shù)直接編碼TotTot * m * n無(wú)效狀態(tài)比率m = 9, n = 9(1,1)為障礙309302.5%m = 10, n

21、 = 10無(wú)障礙7980076.8%m = 11, n = 11(1,1)為障礙3332641551182.2%m = 12, n = 12無(wú)障礙4183577.9%可以看出直接編碼擴(kuò)展的無(wú)效狀態(tài)的比率非常高，對(duì)于障礙較多的棋盤其對(duì)比更加明顯，因此通常來說寬度優(yōu)先搜索擴(kuò)展比直接編碼實(shí)現(xiàn)效率要高Hash判重的優(yōu)化：使用一個(gè)HashSize較小的Hash表，每轉(zhuǎn)移一個(gè)(i, j)清空一次，每次判斷狀態(tài)x是否擴(kuò)展過的程序效率比用一個(gè)HashSize較大的Hash表每次判斷狀態(tài)(i, j, x)高很多類似地，在不需要記錄路徑的情況下，也可以使用滾動(dòng)的擴(kuò)展隊(duì)列來代替一個(gè)大的擴(kuò)展隊(duì)列最后我們比較一下，不同

22、的實(shí)現(xiàn)方法對(duì)程序效率的影響 測(cè)試環(huán)境: Intel Core2 Duo T7100, 1.8GHz, 1G內(nèi)存：Program 1 ：8-Based，枚舉編碼方式Program 2 ：8-Based，隊(duì)列擴(kuò)展，HashSize = 3999997Program 3 ：8-Based，隊(duì)列擴(kuò)展，HashSize = 4001，Hash表每次清空Program 4 ：7-Based，隊(duì)列擴(kuò)展，HashSize = 4001，Hash表每次清空表2不同的實(shí)現(xiàn)方法的程序效率的比較測(cè)試數(shù)據(jù)Program 1Program 2Program 3Program 4m = 10, n = 10無(wú)障礙棋盤46m

23、s31ms15ms31msm = 11, n = 11(1,1)為障礙140ms499ms109ms187msm = 12, n = 12無(wú)障礙624ms1840ms499ms873ms小結(jié)本章從劃分階段，確立狀態(tài)，狀態(tài)轉(zhuǎn)移以及程序?qū)崿F(xiàn)四個(gè)方面介紹了基于連通性狀態(tài)壓縮動(dòng)態(tài)規(guī)劃問題的一般解法，并在每個(gè)方面歸納了一些不同的方法，最后對(duì)不同的算法的效率進(jìn)行比較在平時(shí)的解題過程中我們要學(xué)會(huì)針對(duì)題目的特點(diǎn)和數(shù)據(jù)規(guī)?！皩?duì)癥下藥”，選擇最合適的方法而達(dá)到最好的效果由于逐格遞推的轉(zhuǎn)移開銷比逐行遞推小很多，下文如果不作特殊說明，我們都采用逐格的階段劃分二. 一類簡(jiǎn)單路徑問題這一章我們會(huì)針對(duì)一類基于棋盤模型的簡(jiǎn)單

24、回路和簡(jiǎn)單路徑問題的解法作一個(gè)探討簡(jiǎn)單路徑，即除了起點(diǎn)和終點(diǎn)可能相同外，其余頂點(diǎn)均不相同的路徑，而簡(jiǎn)單回路為起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑Formula 1是一個(gè)典型的棋盤模型的簡(jiǎn)單回路問題，這一章我們繼續(xù)以這個(gè)題為例來說明首先我們分析一下簡(jiǎn)單回路問題有什么特點(diǎn)：仔細(xì)觀察上面的圖，可以發(fā)現(xiàn)輪廓線上方是由若干條互不相交的路徑構(gòu)成的，而每條路徑的兩個(gè)端口恰好對(duì)應(yīng)了輪廓線上的兩個(gè)插頭! 一條路徑上的所有格子對(duì)應(yīng)的是一個(gè)連通塊，而每條路徑的兩個(gè)端口對(duì)應(yīng)的兩個(gè)插頭是連通的而且不與其他任何一個(gè)插頭連通在上一章我們提到了逐格遞推轉(zhuǎn)移的時(shí)候的三種情況：新建一個(gè)連通分量，合并兩個(gè)連通分量，保持原來的連通分量，它們分別

25、等價(jià)于兩個(gè)插頭成為了一條新的路徑的兩端，兩條路徑的兩個(gè)端口連接起來形成一條更長(zhǎng)的路徑或一條路徑的兩個(gè)端口連接起來形成一個(gè)回路以及延長(zhǎng)原來的路徑通過上面的分析我們知道了簡(jiǎn)單回路問題一定滿足任何時(shí)候輪廓線上每一個(gè)連通分量恰好有2個(gè)插頭，那么這些插頭之間有什么性質(zhì)呢?【性質(zhì)】輪廓線上從左到右4個(gè)插頭a, b, c, d，如果a, c連通，并且與b不連通，那么b, d一定不連通dcab證明：反證法，如果a, c連通，b, d連通，那么輪廓線上方一定至少存在一條a到c的路徑和一條b到d的路徑如圖，兩條路徑一定會(huì)有交點(diǎn)，不妨設(shè)兩條路徑相交于格子P，那么P既與a, c連通，又與b, d連通，可以推出a, c

26、與b, d連通，矛盾，得證這個(gè)性質(zhì)對(duì)所有的棋盤模型的問題都適用“兩兩匹配”，“不會(huì)交叉”這樣的性質(zhì)，我們很容易聯(lián)想到括號(hào)匹配將輪廓線上每一個(gè)連通分量中左邊那個(gè)插頭標(biāo)記為左括號(hào)，右邊那個(gè)插頭標(biāo)記為右括號(hào)，由于插頭之間不會(huì)交叉，那么左括號(hào)一定可以與右括號(hào)一一對(duì)應(yīng)這樣我們就可以使用3進(jìn)制0表示無(wú)插頭，1表示左括號(hào)插頭，2表示右括號(hào)插頭記錄下所有的輪廓線信息不妨用#表示無(wú)插頭，那么上面的三幅圖分別對(duì)應(yīng)的是()#()，()#)()，()#)，即，我們稱這種狀態(tài)的表示方法為括號(hào)表示法依然分三類情況來討論狀態(tài)的轉(zhuǎn)移：為了敘述方便，不妨稱(i,j-1)的右插頭為p，(i-1, j)的下插頭為q，(i, j)的

27、下插頭為，右插頭為，那么每次轉(zhuǎn)移相當(dāng)于輪廓線上插頭p的信息修改成的信息，插頭q的信息修改成的信息，設(shè)W(x) = 0, 1, 2表示插頭x的狀態(tài)情況1 新建一個(gè)連通分量，這種情況下W(p) = 0，W(q) = 0，兩個(gè)插頭構(gòu)建了一條新的路徑，相當(dāng)于為左括號(hào)，為右括號(hào)，即 1， 2，計(jì)算新的狀態(tài)的時(shí)間為O(1)情況2 合并兩個(gè)連通分量，這種情況下W(p) 0，W(q) 0， 0， 0，根據(jù)p, q為左括號(hào)還是右括號(hào)分四類情況討論： 情況2.1 W(p) = 1，W(q) = 1那么需要將q這個(gè)左括號(hào)與之對(duì)應(yīng)的右括號(hào)v修改成左括號(hào)，即W(v) 1 情況2.2 W(p) = 2，W(q) = 2那

28、么需要將p這個(gè)右括號(hào)與之對(duì)應(yīng)的左括號(hào)v修改成右括號(hào)，即W(v) 2qpv( ) 情況2.1圖qp( v) 情況2.2圖 情況2.3 W(p) = 1，W(q) = 2，那么p和q是相對(duì)應(yīng)的左括號(hào)和右括號(hào)，連接p, q相當(dāng)于將一條路徑的兩端連接起來形成一個(gè)回路，這種情況下只能出現(xiàn)在最后一個(gè)非障礙格子情況2.4 W(p) = 2，W(q) = 1，那么p和q連接起來后，p對(duì)應(yīng)的左括號(hào)和q對(duì)應(yīng)的右括號(hào)恰好匹配，不需要修改其他的插頭的狀態(tài)pq情況2.3圖pq()情況2.4圖情況2.1, 2.2需要計(jì)算某個(gè)左括號(hào)或右括號(hào)與之匹配的括號(hào)，這個(gè)時(shí)候需要對(duì)三進(jìn)制狀態(tài)解碼，利用類似模擬棧的方法因此情況2.1,

29、2.2計(jì)算新的狀態(tài)的時(shí)間復(fù)雜度為O(n)，2.3, 2.4時(shí)間復(fù)雜度為O(1)情況3 保持原來的連通分量，W(p)，W(q)中恰好一個(gè)為0，中也恰好一個(gè)為0那么無(wú)論，中哪個(gè)插頭存在，都相當(dāng)于是p, q中那個(gè)存在的插頭的延續(xù)，括號(hào)性質(zhì)一樣，因此 W(p) + W(q)， 0或者 W(p) + W(q)， 0計(jì)算新的狀態(tài)的時(shí)間復(fù)雜度為O(1)通過上面的分析可以看出，括號(hào)表示法利用了簡(jiǎn)單回路問題的“一個(gè)連通分量?jī)?nèi)只有2個(gè)插頭”的特殊性質(zhì)巧妙地用3進(jìn)制狀態(tài)存儲(chǔ)下完整的連通信息，插頭的連通性標(biāo)號(hào)相對(duì)獨(dú)立，不再需要通過O(n)掃描大范圍修改連通性標(biāo)號(hào)實(shí)現(xiàn)的時(shí)候，我們可以用4進(jìn)制代替3進(jìn)制而提高程序運(yùn)算效率

30、，下面對(duì)最小表示法與括號(hào)表示法的程序效率進(jìn)行比較：表3不同的狀態(tài)表示的程序效率的比較測(cè)試數(shù)據(jù)最小表示法7Based最小表示法 8Based括號(hào)表示法 3Based括號(hào)表示法 4Basedm = 10, n = 10無(wú)障礙棋盤31ms15ms0ms0msm = 11, n = 11(1,1)為障礙187ms109ms46ms31msm = 12, n = 12無(wú)障礙873ms499ms265ms140ms可以看出，括號(hào)表示法的優(yōu)勢(shì)非常明顯，加上它的思路清晰自然，實(shí)現(xiàn)也更加簡(jiǎn)單，因此對(duì)于解決這樣一類簡(jiǎn)單回路問題是非常有價(jià)值的類似的問題還有：NWERC 2004 Pipes，Hnoi2004 Pos

31、tman，Hnoi2007 Park，還有一類非回路問題也可以通過棋盤改造后用簡(jiǎn)單回路問題的方法解決，比如 POJ 1739 Tonys Tour：給一個(gè)m * n棋盤，有的格子是障礙，要求從左下角走到右下角，每個(gè)格子恰好經(jīng)過一次，問方案總數(shù)(m, n 8)只需要將棋盤改造一下，問題就等價(jià)于Formula 1了 .#. 改造成 .#. . .#.#. .介紹完簡(jiǎn)單回路問題的解法，那么一般的簡(jiǎn)單路徑問題又如何解決呢? 【例2】Formula 2 改編自Formula 1問題描述給你一個(gè)m * n的棋盤，有的格子是障礙，要求從一個(gè)非障礙格子出發(fā)經(jīng)過每個(gè)非障礙格子恰好一次，問方案總數(shù)m, n 10

32、如圖，一個(gè)2 * 2的無(wú)障礙棋盤，共有4條滿足要求的路徑算法分析確立狀態(tài)：按照從上到下，從左到右依次考慮每一個(gè)格子，設(shè)表示轉(zhuǎn)移完(i, j)這個(gè)格子，輪廓線狀態(tài)為S的方案總數(shù)如果用一般的最小表示法，不僅需要記錄每個(gè)插頭的連通情況，還需要額外記錄每個(gè)插頭是否連接了路徑的一端，狀態(tài)表示相當(dāng)復(fù)雜依然從括號(hào)表示法這個(gè)角度來思考如何來存儲(chǔ)輪廓線的狀態(tài)：這個(gè)問題跟簡(jiǎn)單回路問題最大的區(qū)別為：不是所有的插頭都兩兩匹配，有的插頭連接的路徑的另一端不是一個(gè)插頭而是整條路徑的一端，我們稱這樣的插頭為獨(dú)立插頭不妨將原來的3進(jìn)制狀態(tài)修改成4進(jìn)制0表示無(wú)插頭，1表示左括號(hào)插頭，2表示右括號(hào)插頭，3表示獨(dú)立插頭，這樣我們就

33、可以用4進(jìn)制完整地記錄下輪廓線的信息，圖中狀態(tài)表示為(1203)4狀態(tài)轉(zhuǎn)移：依然設(shè)(i, j-1)的右插頭為p，(i-1, j)的下插頭為q，(i, j)的下插頭為，右插頭為部分轉(zhuǎn)移同簡(jiǎn)單回路問題完全一樣，這里不再贅述，下面分三類情況討論與獨(dú)立插頭有關(guān)的轉(zhuǎn)移：情況1 W(p) = 0，W(q) = 0當(dāng)前格子可能成為路徑的一端，即右插頭或下插頭是獨(dú)立插頭，因此 3， 0或者 3， 0情況2 W(p) 0，W(q) 0，那么 0， 0情況2.1 W(p) =3，W(q) = 3，將插頭p和q連接起來就相當(dāng)于形成了一條完整的路徑，這種情況只能出現(xiàn)在最后一個(gè)非障礙格子情況2.2 W(p) ，W(q)

34、 中有一個(gè)為3，如果p為獨(dú)立插頭，那么無(wú)論q是左括號(hào)插頭還是右括號(hào)插頭，與q相匹配的插頭v成為了獨(dú)立插頭，因此，W(v) 3如果q為獨(dú)立插頭，類似處理情況3 W(p) ，W(q) 中有一個(gè)0，即p, q中有一個(gè)插頭存在情況3.1 如果這個(gè)插頭為獨(dú)立插頭，若在最后一個(gè)非障礙格子，這個(gè)插頭可以成為路徑的一端，否則可以用右插頭或下插頭來延續(xù)這個(gè)獨(dú)立插頭情況3.2 如果這個(gè)插頭是左括號(hào)或右括號(hào)，那么我們以將這個(gè)插頭“封住”，使它成為路徑的一端，需要將這個(gè)插頭所匹配的另一個(gè)插頭的狀態(tài)修改成為獨(dú)立插頭情況2.2, 3.2需要計(jì)算某個(gè)左括號(hào)或右括號(hào)與之匹配的括號(hào)，計(jì)算新的狀態(tài)的時(shí)間復(fù)雜度為O(n)，其余情況

35、計(jì)算新的狀態(tài)的時(shí)間復(fù)雜度為O(1) 特別需要注意，任何時(shí)候輪廓線上獨(dú)立插頭的個(gè)數(shù)不可以超過2個(gè)至此問題完整解決，m = n = 10的無(wú)障礙棋盤，擴(kuò)展的狀態(tài)總數(shù)為，完全可以承受上面兩類題目我們用括號(hào)表示法取得了很不錯(cuò)的效果，但是它存在一定的局限性，即插頭必須滿足兩兩匹配那么對(duì)于更加一般的問題，一個(gè)連通分量?jī)?nèi)出現(xiàn)大于2個(gè)插頭，上述的括號(hào)表示方法顯得束手無(wú)策下面將介紹一種括號(hào)表示法的變形，它可以適用于出現(xiàn)連通塊內(nèi)大于2個(gè)插頭的問題，我們稱之為廣義的括號(hào)表示法：假設(shè)一個(gè)連通分量從左到右有多個(gè)插頭，不妨將最左邊的插頭標(biāo)記為“(”，最右邊的插頭標(biāo)記為“)”，中間的插頭全部標(biāo)記為“)(”，那么能夠匹配的括

36、號(hào)對(duì)應(yīng)的插頭連通如果問題中可能出現(xiàn)一個(gè)連通分量只有一個(gè)插頭，那么這個(gè)插頭標(biāo)記為“( )”，這樣插頭之間的連通性可用括號(hào)序列完整地記錄下來，比如對(duì)于一個(gè)連通性狀態(tài)為1,2,2,3,4,3,2,1，我們可以用(-(-)(-(-()-)-)-)記錄這種廣義的括號(hào)表示方法需要用4進(jìn)制甚至5進(jìn)制存儲(chǔ)狀態(tài)，而且直接對(duì)狀態(tài)連通性進(jìn)行修改情況非常多，最好還是將狀態(tài)進(jìn)行解碼，修改后再重新編碼下文我們將會(huì)運(yùn)用廣義的括號(hào)表示法解決一些具體的問題 小結(jié)本章針對(duì)一類簡(jiǎn)單路徑問題，提出了一種新的狀態(tài)表示方法括號(hào)表示法，最后提出了廣義的括號(hào)表示方法相比普通的最小表示法，括號(hào)表示法巧妙地把連通塊與括號(hào)匹配一一對(duì)應(yīng)，使得狀態(tài)更

37、加簡(jiǎn)單明了，雖然不會(huì)減少擴(kuò)展的狀態(tài)總數(shù)，但是轉(zhuǎn)移開銷的常數(shù)要小很多，是一個(gè)不錯(cuò)的方法 三. 一類棋盤染色問題有一類這樣的問題給你一個(gè)m * n的棋盤，要求給每個(gè)格子染上一種顏色(共k種顏色)，每種顏色的格子相互連通 (4連通)本章主要對(duì)這類問題的解法進(jìn)行探討，我們從一個(gè)例題說起：【例3】Black & White Source : Uva10572問題描述一個(gè)m * n的棋盤，有的格子已經(jīng)染上黑色或白色，現(xiàn)在要求將所有的未染色格子染上黑色或白色，使得滿足以下2個(gè)限制：1) 所有的黑色的格子是連通的，所有的白色格子也是連通的2) 不會(huì)有一個(gè)2 * 2的子矩陣的4個(gè)格子的顏色全部相同問方案總數(shù)(m

38、, n 8) 如下圖，m = 2，n = 3，灰色格子為未染色格子，共有9種染色方案 算法分析這是一個(gè)典型的棋盤染色問題，著色規(guī)則有：1) 只有黑白兩種顏色，即k = 2，并且同色的格子互相連通2) 沒有同色的2 * 2的格子對(duì)于簡(jiǎn)單路徑問題來說，相鄰的格子是否連通取決于它們之間的插頭是否存在，狀態(tài)記錄輪廓線上每個(gè)插頭是否存在以及插頭之間的連通性；而棋盤染色問題相鄰的格子是否連通取決于它們的顏色是否相同，這就需要記錄輪廓線上方n個(gè)格子的顏色以及格子之間的連通性確立狀態(tài)設(shè)當(dāng)前轉(zhuǎn)移完Q(i, j)這個(gè)格子，對(duì)以后的決策產(chǎn)生影響的信息有：輪廓線上方n個(gè)格子的染色情況以及它們的連通性，由第2條著色規(guī)則

39、“沒有同色的2 * 2的格子”可知P(i-1, j)的顏色會(huì)影響到(i, j+1)著色，因此我們還需要額外記錄格子的顏色動(dòng)態(tài)規(guī)劃的狀態(tài)為：表示轉(zhuǎn)移完(i, j)，輪廓線上從左到右n個(gè)格子的染色情況為S0 (0 S0 2n)，連通性狀態(tài)為S1，格子的顏色為cp(0或1)的方案總數(shù)狀態(tài)的精簡(jiǎn)如果相鄰的2個(gè)格子不屬于同一個(gè)連通塊，那么它們必然不同色，因此只需要記錄(i, 1)和(i-1, j+1)兩個(gè)格子的顏色，利用S1就可以推出n個(gè)格子的顏色這個(gè)精簡(jiǎn)不會(huì)減少狀態(tài)的總數(shù)，仍然需要一個(gè)變量來記錄兩個(gè)格子的顏色，因此意義并不大，這里只是提一下狀態(tài)轉(zhuǎn)移枚舉當(dāng)前格子(i, j)的顏色，計(jì)算新的狀態(tài)：S0和c

40、p都很容易O(1)計(jì)算出來考慮計(jì)算S1：輪廓線的變化相當(dāng)于將記錄(i-1, j)的連通性改成記錄(i, j)的連通性根據(jù)當(dāng)前格子與上面的格子和左邊的格子是否同色分四類情況討論應(yīng)當(dāng)注意的是如果(i, j)和(i-1, j)不同色，并且(i-1, j)在輪廓線上為一個(gè)單獨(dú)的一個(gè)連通塊，那么(i-1, j)以后都不可能與其他格子連通，即剩余的格子都必須染上與(i-1, j)相反的顏色，需要特殊判斷轉(zhuǎn)移的時(shí)間復(fù)雜度為O(n)計(jì)算新狀態(tài)的S1程序框架如下：將前一個(gè)狀態(tài)的S1解碼，連通性存入c1,c2,cnIf (i, j) 與 (i-1, j) 不同色并且 (i-1, j) 為一個(gè)單獨(dú)的連通塊Then特

41、殊判斷 ElseIf (i, j) 與 (i-1, j) 和 (i, j-1) 均同色Then For k 1 to n If ck = cj Then ck cj-1 / 合并兩個(gè)連通塊 EndIfElse If (i, j) 與 (i-1, j) 和 (i, j-1) 均不同色Then cj 最大可能出現(xiàn)的連通塊標(biāo)號(hào) / (i, j) 新建一個(gè)連通塊Else If (i, j) 與 (i, j-1) 同色與 (i-1, j) 不同色 Then cj cj-1 / (i, j) 的連通性標(biāo)號(hào)跟 (i, j-1)相同 EndIf EndIf EndIf EndIf對(duì)c O(n)掃描，修改成最小

42、表示，利用c編碼計(jì)算出新的S1對(duì)于m = n = 8的一個(gè)全部未染色的棋盤，擴(kuò)展出來的狀態(tài)總數(shù)為122395，轉(zhuǎn)移需要時(shí)間為O(n)，因此總的時(shí)間復(fù)雜度為O(TotalState * n) = 979160，運(yùn)行時(shí)間0.1s至此問題完整解決類似可以解決的問題還有2007年重慶市選拔賽 Rect和IPSC 2007 Delicious Cake擴(kuò)展 上面提到的是4連通問題，如果要求8連通呢?4連通問題是兩個(gè)格子至少有一條邊重合為連通，而8連通問題是兩個(gè)格子至少有一個(gè)頂點(diǎn)重合為連通，因此需要記錄所有至少有一個(gè)頂點(diǎn)在輪廓線上的格子的連通和染色情況，即包括(i-1, j)在內(nèi)的n+1個(gè)格子一個(gè)優(yōu)化的方

43、向擴(kuò)展的狀態(tài)中無(wú)效狀態(tài)的總數(shù)很大程度上決定了算法的效率比如Black & White中如果出現(xiàn)右圖的狀態(tài)，那么無(wú)論之后如何決策，都不可能滿足同色的格子互相連通的性質(zhì)，因此它是一個(gè)無(wú)效狀態(tài)對(duì)于任何一個(gè)k染色棋盤問題，如果從左到右有4個(gè)相互不嵌套“嵌套”的概念可以用廣義的括號(hào)匹配的表示方法來理解的連通塊a,b,c,d，a, c同色, b, d同色且與a, c不同色，那么這個(gè)狀態(tài)為無(wú)效狀態(tài)小結(jié)本章介紹了解決一類棋盤染色問題的一般思路無(wú)論染色規(guī)則多么復(fù)雜，我們只要在基本狀態(tài)即“輪廓線上方與其相連的格子的連通性以及染色情況”的基礎(chǔ)上，根據(jù)題目的需要在狀態(tài)中增加對(duì)以后的決策可能產(chǎn)生影響的信息，問題都可以迎

44、刃而解了 四. 一類基于非棋盤模型的問題本章將會(huì)介紹一類基于非棋盤模型的連通性狀態(tài)壓縮動(dòng)態(tài)規(guī)劃問題，它雖然不具有棋盤模型的特殊結(jié)構(gòu)，但是解法的核心思想又跟棋盤模型的問題有著異曲同工之處 【例4】生成樹計(jì)數(shù) Source : Noi2007 Day2 生成樹計(jì)數(shù), Count問題描述給你一個(gè)n個(gè)點(diǎn)的無(wú)向連通圖，其邊集為：任何兩個(gè)不同的點(diǎn)i, j(1 i, j n)，如果|i - j| k，那么有一條無(wú)向邊已知n和k，求這個(gè)圖的生成樹個(gè)數(shù) n 1015，2 k 5算法分析這個(gè)題給我們的第一印象是：n非常大，k卻非常小 生成樹最重要的兩個(gè)性質(zhì)：無(wú)環(huán)，連通那么如果按照1,2,n的順序依次考慮每一個(gè)點(diǎn)與

45、前面的哪些點(diǎn)相連，并且保證任何時(shí)候都不會(huì)出現(xiàn)環(huán)，最后統(tǒng)計(jì)所有的點(diǎn)全部在一個(gè)連通分量?jī)?nèi)的方案總數(shù)即為最終的答案在棋盤模型的問題中，我們提出了輪廓線這個(gè)概念，任何時(shí)候只有輪廓線上方與其直接相連的格子對(duì)以后的決策會(huì)產(chǎn)生影響類似地我們分析一下這個(gè)問題，當(dāng)我們確定了1i的所有點(diǎn)的連邊情況后，哪些信息對(duì)以后的決策會(huì)產(chǎn)生影響：1ik這些點(diǎn)與i之后的點(diǎn)一定沒有邊相連，那么對(duì)i以后的點(diǎn)的決策不會(huì)產(chǎn)生直接的影響，因此我們需要記錄的僅僅是i-k+1i這k個(gè)點(diǎn)的連通信息!如下圖，我們不妨也稱藍(lán)線為輪廓線，因?yàn)橹挥休喞€上的點(diǎn)的信息會(huì)對(duì)輪廓線右邊的點(diǎn)的決策產(chǎn)生直接的影響這樣我們就很容易確立狀態(tài)：設(shè)表示考慮完前i個(gè)點(diǎn)的連

46、邊情況后，i-k+1 . i這k個(gè)點(diǎn)的連通情況為S.轉(zhuǎn)移狀態(tài)：O(2k)依次枚舉點(diǎn)i與i-1，i-k這k個(gè)點(diǎn)是否相連轉(zhuǎn)移的時(shí)候需要注意：i-1, , i-k這k個(gè)點(diǎn)，任何一個(gè)連通塊，i最多只能與其中的一個(gè)點(diǎn)相連，這樣可以避免環(huán)的出現(xiàn)如果i-k在輪廓線上為一個(gè)單獨(dú)的連通塊，那么i必然與i-k相連，這樣可以避免出現(xiàn)孤立的連通塊比如對(duì)于一個(gè)k = 5的狀態(tài)來說，如果點(diǎn)i與i-2和i-1相連，那么新的狀態(tài)為這樣我們就可以在O(2k*k)的時(shí)間復(fù)雜度內(nèi)完成狀態(tài)的轉(zhuǎn)移算法實(shí)現(xiàn)：設(shè)Tk表示k個(gè)點(diǎn)的本質(zhì)不同的連通情況的個(gè)數(shù)，搜索可知T5=52動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為O(n * Tk * 2k * k)，依然太大

47、可以發(fā)現(xiàn)當(dāng)i k，狀態(tài)是否可以轉(zhuǎn)移到只與有關(guān)，這樣我們就可以用矩陣乘法實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃加速，由于這不是本文的重點(diǎn)，這里不再詳細(xì)介紹最終的時(shí)間復(fù)雜度為O(Tk3*log2n)，對(duì)于k = 5, Tk = 52的數(shù)據(jù)規(guī)模來說已經(jīng)完全可以承受了，至此問題完整解決本題中的無(wú)向圖非常特殊，每個(gè)點(diǎn)只和距離它不超過k的點(diǎn)有邊相連，并且k非常小對(duì)于棋盤模型的問題，可以抽象成一個(gè)特殊的無(wú)向圖m * n個(gè)點(diǎn)，每個(gè)點(diǎn)只與它上下左右四個(gè)點(diǎn)有邊相連那么對(duì)于一個(gè)與連通性有關(guān)的無(wú)向圖問題，無(wú)向圖具備怎樣的特點(diǎn)才可以用基于狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃來解決?分析以上幾個(gè)問題，不難發(fā)現(xiàn)它們有一個(gè)共同點(diǎn)：給無(wú)向圖中的點(diǎn)找一個(gè)序，在這個(gè)序中有邊

48、相連的兩個(gè)點(diǎn)的距離不超過p(p很小)，這樣我們就可以以當(dāng)前決策完序中前i個(gè)，最后p個(gè)點(diǎn)的連通性為狀態(tài)作動(dòng)態(tài)規(guī)劃棋盤模型的問題中序即為從上到下，從左到右或從左到右，從上到下，p為m或n，因此棋盤模型的問題m和n中至少有一個(gè)數(shù)會(huì)非常小小結(jié)本章寫得比較簡(jiǎn)略，但是依然能夠給我們很多的啟示處理這樣的一類非棋盤模型的問題，一般的思路是尋找某一個(gè)序依次考慮每個(gè)點(diǎn)的決策，并分析哪些信息對(duì)以后的決策會(huì)產(chǎn)生影響，找到問題中的“輪廓線”，以輪廓線的信息來確立動(dòng)態(tài)規(guī)劃的狀態(tài)通常來說，輪廓線上的信息比較少，這也是能夠作狀態(tài)壓縮動(dòng)態(tài)規(guī)劃的基礎(chǔ)，像本題中k5這樣的條件往往能成為解決問題的突破口 五. 一類最優(yōu)性問題的剪枝技

49、巧基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題的算法的效率主要取決于狀態(tài)的總數(shù)和轉(zhuǎn)移的開銷，減少狀態(tài)總數(shù)和降低轉(zhuǎn)移開銷成為了優(yōu)化的核心內(nèi)容前面的章節(jié)我們提到了一些優(yōu)化的技巧，這一章我們選取了一個(gè)非常有趣的題目Rocket Mania來介紹針對(duì)這樣的一類最優(yōu)性問題，如何通過剪枝使?fàn)顟B(tài)總數(shù)大大減少而提高算法效率【例5】Rocket Mania Source : Zju 2125, Online Contest of Fantasy Game問題描述這個(gè)題目的背景是幻想游戲的“中國(guó)煙花”：給你一個(gè)9 * 6的棋盤，棋盤的左邊有9根火柴，右邊有9個(gè)火箭棋盤中的每一個(gè)格子可能是一個(gè)空格子也可能是一段管道，管道的類型

50、有4種： L型 型 T型 十型一個(gè)火箭能夠被發(fā)射當(dāng)且僅當(dāng)存在一條由管道組成的從一根點(diǎn)燃的火柴到這個(gè)火箭的路徑給你棋盤的初始狀態(tài)以及X，你的目標(biāo)是旋轉(zhuǎn)每個(gè)格子內(nèi)的管道0，90，180或270度，使得當(dāng)點(diǎn)燃左邊第X根火柴后，被發(fā)射的火箭個(gè)數(shù)盡可能多算法分析確立狀態(tài)：按照從左到右，從上到下的順序依次考慮每一個(gè)格子，我們需要記錄每個(gè)插頭是否已經(jīng)點(diǎn)燃以及它們之間的連通情況因此狀態(tài)為表示轉(zhuǎn)移完(i, j)，輪廓線上10個(gè)插頭的連通性為S(把每個(gè)插頭是否存在記錄在S中), 10個(gè)插頭是否被點(diǎn)燃的2進(jìn)制數(shù)fired的狀態(tài)能否達(dá)到 那么最后的答案為所有可以達(dá)到的狀態(tài)中 Onesfired的最大值，其中Onesx

51、表示二進(jìn)制數(shù)x的1的個(gè)數(shù)狀態(tài)轉(zhuǎn)移：依次枚舉每一個(gè)格子的旋轉(zhuǎn)方式(最多4種)，根據(jù)當(dāng)前格子是否可以與上面的格子和左邊的格子通過插頭連接起來分情況討論，O(m)掃描計(jì)算出新的狀態(tài)前面的題目我們已經(jīng)很詳細(xì)地介紹過棋盤模型的問題的轉(zhuǎn)移方法，這里不再贅述如果直接按照上面的思路作動(dòng)態(tài)規(guī)劃，Sample也需要運(yùn)行 60s，實(shí)在令人無(wú)法滿意優(yōu)化，勢(shì)在必行如何通過剪枝優(yōu)化來減少擴(kuò)展的狀態(tài)總數(shù)，盡可能舍去無(wú)效狀態(tài)成為了現(xiàn)在所面臨的問題：剪枝通?？梢苑譃閮深悾阂豢尚行约糁Γ磳o(wú)論之后如何決策，都不可能滿足題目要求的狀態(tài)剪掉；二最優(yōu)性剪枝，即對(duì)于最優(yōu)性問題，將不可能成為最優(yōu)解的狀態(tài)給剪掉我們從這兩個(gè)角度入手來考慮問

52、題：剪枝一：如果輪廓線上所有的插頭全部都未被點(diǎn)燃，那么最后所有的火箭都不可能發(fā)射，所以這個(gè)狀態(tài)可以舍去這個(gè)剪枝看上去非常顯然，對(duì)于大部分?jǐn)?shù)據(jù)卻可以剪掉近乎一半的狀態(tài)p剪枝二：如果輪廓線上有一個(gè)插頭p，它沒有被火柴點(diǎn)燃且沒有其它的插頭與它連通，那么這個(gè)插頭可以認(rèn)為是“無(wú)效”插頭因?yàn)榧词惯@個(gè)插頭所在的路徑以后會(huì)被點(diǎn)燃而可以發(fā)射某個(gè)火箭，那么一定存在另一條路徑可以不經(jīng)過這個(gè)插頭而發(fā)射火箭，如圖這種情況下將插頭設(shè)置為不存在這是最重要的一個(gè)剪枝，大部分?jǐn)?shù)據(jù)的狀態(tài)總數(shù)可以縮小七八倍，甚至十幾倍剪枝三：這是一個(gè)最優(yōu)性問題，我們考慮最優(yōu)性剪枝：對(duì)于一個(gè)格子(i, j)的兩個(gè)狀態(tài)，如果第一個(gè)狀態(tài)的每一個(gè)存在的插頭在第二個(gè)狀態(tài)中不僅存在而且都被點(diǎn)燃，那么無(wú)論以后如何決策，第二個(gè)狀態(tài)點(diǎn)燃的火箭個(gè)數(shù)不會(huì)少于第一