入門動態(tài)規(guī)劃狀態(tài)壓縮

1、主講：主講：ftfish (ftfish (周偉周偉 天津大學(xué)天津大學(xué)20072007級級) )郵箱：郵箱：zhouwei- (zhouwei- (三個減號三個減號) )手機(jī)：手機(jī)： Q Q Q Q ：155 175 157155 175 157 信息學(xué)發(fā)展勢頭迅猛，信息學(xué)奧賽的題目來源遍及各行各業(yè)，經(jīng)常有一些在實(shí)際應(yīng)用中很有價值的問題被引入信息學(xué)并得到有效解決。 然而有一些問題卻被認(rèn)為很可能不存在有效的(多項(xiàng)式級的)算法，這里以對幾個例題的剖析，簡述狀態(tài)壓縮思想及其應(yīng)用。名稱名稱C/C+樣式樣式Pascal樣式樣式簡記法則簡記法則按位與按位與&and全一則一，否則為零全一則一，否則為零按位或

2、按位或|or有一則一，否則為零有一則一，否則為零按位取反按位取反not是零則一，是一則零是零則一，是一則零按位異或按位異或xor不同則一，相同則零不同則一，相同則零左移位左移位shlashrak等價于等價于a/2k作為對下文的準(zhǔn)備，這里先為使用Pascal的OIers簡要介紹一下C/C+樣式的位運(yùn)算(bitwise operation)。其優(yōu)先級：notandxoror位運(yùn)算的特殊應(yīng)用位運(yùn)算的特殊應(yīng)用and：用以取出一個數(shù)的某些二進(jìn)制位用以取出一個數(shù)的某些二進(jìn)制位取出一個數(shù)二進(jìn)制中的最后一個取出一個數(shù)二進(jìn)制中的最后一個1(lowbit)：x&-xor ：將一個數(shù)的某些位設(shè)為：將一個數(shù)的某些位設(shè)

3、為1not：間接構(gòu)造一些數(shù)：間接構(gòu)造一些數(shù)：0u= =232-1xor：不使用中間變量交換兩個數(shù)：不使用中間變量交換兩個數(shù)：a=ab;b=ba;a=ab;將一個數(shù)的某些位取反將一個數(shù)的某些位取反 在n*n(n20)的方格棋盤上放置n個車(可以攻擊所在行、列)，求使它們不能互相攻擊的方案總數(shù)。 10秒時間思考 這個題目之所以是作為引例而不是例題，是因?yàn)樗鼘?shí)在是個非常簡單的組合學(xué)問題 我們一行一行放置，則第一行有n種選擇，第二行n-1，最后一行只有1種選擇，根據(jù)乘法原理，答案就是n! 這里既然以它作為狀態(tài)壓縮的引例，當(dāng)然不會是為了介紹組合數(shù)學(xué)。我們下面來看另外一種解法：狀態(tài)壓縮遞推(States

4、Compressing Recursion,SCR) 我們?nèi)匀灰恍幸恍蟹胖谩?取棋子的放置情況作為狀態(tài)，某一列如果已經(jīng)放置棋子則為1，否則為0。這樣，一個狀態(tài)就可以用一個最多20位的二進(jìn)制數(shù)表示。 例如n=5,第1、3、4列已經(jīng)放置，則這個狀態(tài)可以表示為01101(從右到左)。設(shè)fs為達(dá)到狀態(tài)s的方案數(shù)，則可以嘗試建立f的遞推關(guān)系。 考慮n=5,s=01101 因?yàn)槲覀兪且恍幸恍蟹胖玫?，所以?dāng)達(dá)到s時已經(jīng)放到了第三行。又因?yàn)橐恍心芮覂H能放置一個車，所以我們知道狀態(tài)s一定來自： 前兩行在第3、4列放置了棋子(不考慮順序，下同)，第三行在第1列放置； 前兩行在第1、4列放置了棋子，第三行在第3列放

5、置； 前兩行在第1、3列放置了棋子，第三行在第4列放置。 這三種情況互不相交，且只可能有這三種情況，根據(jù)加法原理，fs應(yīng)該等于這三種情況的和。寫成遞推式就是： 根據(jù)上面的討論思路推廣之，得到引例的解決辦法：其中s的右起第i+1位為1(其實(shí)就是在枚舉s的二進(jìn)制表示中的1)Prog P0read(n);int64 f1.220=0;f0=1;for(int i=1;i0;t-=t&-t)fi+=fi(t&-t);write(f2n-1); 反思這個算法，其正確性毋庸置疑(可以和n!對比驗(yàn)證) 但是算法的時間復(fù)雜度為O(n2n)，空間復(fù)雜度O(2n)，是個指數(shù)級的算法，比循環(huán)計(jì)算n!差了好多，它有什

6、么優(yōu)勢？ （還有一個很的用處，即對新手說：“來看看我這個計(jì)算n!的程序，連這都看不懂就別OI了”）可擴(kuò)展性！可擴(kuò)展性！ 在n*n(n20)的方格棋盤上放置n個車，某些格子不能放，求使它們不能互相攻擊的方案總數(shù)。 30s思考時間 對于這個題目，如果組合數(shù)學(xué)學(xué)得不夠扎實(shí)，應(yīng)該很難一眼看出解法。 本題確實(shí)存在數(shù)學(xué)方法(容斥原理)，但因?yàn)楹鸵瑯拥睦碛?，這里不再贅述。 引例的算法是在枚舉當(dāng)前行(即s中1的個數(shù)，設(shè)為r)的放置位置(即枚舉每個1) 而對于例1，第r行可能存在無法放置的格子，怎么解決？ 事實(shí)上，我們并不需要對引例的算法進(jìn)行太大的改變，只要在枚舉s中的1的時候判斷一下是否是不允許放置的格子

7、即可 然而對于n=20，O(n2n)的復(fù)雜度已經(jīng)不允許我們再進(jìn)行多余的判斷。所以實(shí)現(xiàn)這個算法時應(yīng)該應(yīng)用一些技巧。 我們用ar表示第r行不允許放置的情況，如果第r行某一位不允許放置則ar此位為0，否則為1，這可以在讀入數(shù)據(jù)階段完成 然后對于需要處理的狀態(tài)s，用ts=s&ar來代替s進(jìn)行枚舉，即不枚舉s中的1轉(zhuǎn)而枚舉ts中的1。 因?yàn)閠s保證了不允許放置的位為0，這樣就可以不用其它的判斷來實(shí)現(xiàn)算法 代碼中只增加了計(jì)算a數(shù)組和r的部分，而時間復(fù)雜度沒有變化。 我們直接套用引例的算法就使得看上去更難的例1得到了解決。 雖然這題用容斥原理更快，但容斥原理在這題上只有當(dāng)棋盤為正方形、放入的棋子個數(shù)為n、且

8、棋盤上禁止放置的格子較少時才有較簡單的形式和較快的速度。 如果再對例1進(jìn)行推廣，要在m*n的棋盤上放置k個車，那么容斥原理是無能為力的，而SCR算法只要進(jìn)行很少的改變就可以解決問題。這也體現(xiàn)出了引例中給出的算法的擴(kuò)展?jié)摿Α?有一個n*m的棋盤(n、m80,n*m80)要在棋盤上放k(k20)個棋子，使得任意兩個棋子不相鄰。求合法的方案總數(shù) 5min思考、討論、提問時間 觀察題目給出的規(guī)模，n、m80，這個規(guī)模要想用SC是困難的，280無論在時間還是空間上都無法承受 然而我們還看到n*m80 稍微思考我們可以發(fā)現(xiàn)：9*9=8180，即如果n,m都大于等于9，將不再滿足n*m80這一條件。所以，我

9、們有n或m小于等于8，而28是可以承受的！ 我們假設(shè)mn，n是行數(shù)m是列數(shù)，則每行的狀態(tài)可以用m位的二進(jìn)制數(shù)表示 但是本題和例1又有不同：例1每行每列都只能放置一個棋子，而本題卻只限制每行每列的棋子不相鄰 上例中枚舉當(dāng)前行的放置方案的做法依然可行。我們用數(shù)組s保存一行中所有的num個放置方案，則s數(shù)組可以在預(yù)處理過程中用DFS求出，同時用ci保存第i個狀態(tài)中1的個數(shù)以避免重復(fù)計(jì)算 開始設(shè)計(jì)狀態(tài)。本題狀態(tài)的維數(shù)需要增加，原因在于并不是每一行只放一個棋子，也不是每一行都要求有棋子，原先的表示方法已經(jīng)無法完整表達(dá)一個狀態(tài)。 我們用fi,j,k表示第i行的狀態(tài)為sj且前i行總共放置k個棋子（下面用pn

10、代替原題中的k）的方案數(shù)。沿用枚舉當(dāng)前行方案的做法，只要當(dāng)前行的放置方案和上一行的不沖突。微觀地講，就是要兩行的狀態(tài)s1和s2中沒有同為1的位即可，亦即s1&s2=0 然而，雖然我們枚舉了第i行的放置方案，但卻不知道其上一行(第i-1行)的方案 為了解決這個問題，我們不得不連第i-1行的狀態(tài)一起枚舉，則可以寫出遞推式：其中其中s1=0s1=0，即在當(dāng)前行不放置棋子；，即在當(dāng)前行不放置棋子；j j和和p p是需要枚舉的兩個狀態(tài)編號。是需要枚舉的兩個狀態(tài)編號。 本題至此基本解決。當(dāng)然，實(shí)現(xiàn)上仍有少許優(yōu)化空間，例如第i行只和第i-1行有關(guān)，可以用滾動數(shù)組節(jié)省空間。 這個算法時間復(fù)雜度O(n*pn*n

11、um2)，空間復(fù)雜度(滾動數(shù)組)O(pn*num) 運(yùn)用簡單的組合數(shù)學(xué)知識可以求出本題中的num=144，因而對于本題的數(shù)據(jù)規(guī)?？梢院芸斐鼋?給出一個n*m(n100,m10)的棋盤，一些格子不能放置棋子。求最多能在棋盤上放置多少個棋子，使得每一行每一列的任兩個棋子間至少有兩個空格。 題目來源：NOI2001炮兵陣地 TOI 1023；POJ 1185 30s 思考時間 仍然先用DFS搜出一行可能狀態(tài)s，依舊用c保存s中1的個數(shù)，依照例1的預(yù)處理搞定不能放置棋子的格子（應(yīng)該有這種意識） 問題是，這個題目的狀態(tài)怎么選？繼續(xù)像例2那樣似乎不行，原因在于棋子的攻擊范圍加大了 但是我們照葫蘆畫瓢：例2

12、的攻擊范圍只有一格，所以我們的狀態(tài)中只需要有當(dāng)前行的狀態(tài)，再枚舉上一行的狀態(tài)即可進(jìn)行遞推；而本題攻擊范圍是兩格，因此增加一維來表示上一行的狀態(tài)。 用fi,j,k表示第i行狀態(tài)為sj、第i-1行狀態(tài)為sk時前i行至多能放置的棋子數(shù)。則狀態(tài)轉(zhuǎn)移方程很容易寫出：顯然，算法時間復(fù)雜度為O(n*num3)，空間復(fù)雜度(滾動數(shù)組)O(num2)因?yàn)槠遄庸舴秶鸀閮筛?，可以直觀地想像到本題的num不會很大。的確，可以算出本題num60。 此算法還有優(yōu)化空間 我們分別枚舉了三行的狀態(tài)，還需要對這三個狀態(tài)進(jìn)行是否沖突的判斷，這勢必會重復(fù)枚舉到一些沖突的狀態(tài)組合 在DFS出s后，我們可以算出哪些狀態(tài)對可以分別作為

13、兩行的狀態(tài)，這樣在DP時就不需要進(jìn)行盲目的枚舉，理論上效率會更高。但因?yàn)閚um本身很小，所以這樣修改沒有顯著地減少運(yùn)行時間 值得一提的是，本題筆者的算法雖然在理論上并不是最優(yōu)（有種應(yīng)用三進(jìn)制的方法），但由于位運(yùn)算的使用，截至07年8月17日，筆者的程序在PKU OJ上長度最短，速度第二快。 但是很不幸，公元2007年8月18日，天津大學(xué)06級的某同學(xué)去掉本算法的一些關(guān)鍵判斷，達(dá)到了更短的長度，但其速度慢了3倍 這個題目是國內(nèi)比賽中較早出現(xiàn)的狀態(tài)壓縮題。它告訴我們狀態(tài)壓縮不僅可以像前幾個例題那樣求方案數(shù)，而且可以求最優(yōu)方案，即狀態(tài)壓縮思想既可以應(yīng)用到遞推上(SCR)，又可以應(yīng)用到DP上(SCDP

14、)，更說明其有廣泛的應(yīng)用空間。 看了這么多棋盤模型應(yīng)用狀態(tài)壓縮的實(shí)例，可能會讓人產(chǎn)生錯覺，以為狀態(tài)壓縮只在棋盤上放棋子的題目中有用。我們暫時轉(zhuǎn)移視線，來看看狀態(tài)壓縮在其他地方的應(yīng)用覆蓋模型。 給出n*m(1n、m11)的方格棋盤，用1*2的長方形骨牌不重疊地覆蓋這個棋盤，求覆蓋滿的方案數(shù)。 經(jīng)典問題 TOJ 1343; POJ 2411Have a break ! 這也是個經(jīng)典的組合數(shù)學(xué)問題：多米諾骨牌完美覆蓋問題(或所謂二聚物問題)。有很多關(guān)于這個問題的結(jié)論，甚至還有個專門的公式:2211)1+n*j(cos4)1+m*i(4cos22mnij誰看得懂、記得住？ 顯然，如果n、m都是奇數(shù)則無

15、解(由棋盤面積的奇偶性知)，否則必然有至少一個解(很容易構(gòu)造出) 因此假設(shè)n、m至少有一個偶數(shù)，且mn 我們依然像前面的例題一樣把每行的放置方案DFS出來，逐行計(jì)算 用fi,s表示把前i-1行覆蓋滿、第i行覆蓋狀態(tài)為s的覆蓋方案數(shù) 因?yàn)樵诘趇行上放置的骨牌最多也只能影響到第i-1行，則容易得遞推式： 首先討論DFS的一些細(xì)節(jié)。 對于當(dāng)前行每一個位置，我們有3種放置方法： 豎直覆蓋，占據(jù)當(dāng)前格和上一行同一列的格； 水平覆蓋，占據(jù)當(dāng)前格和該行下一格； 不放置骨牌，直接空格。 如何根據(jù)這些枚舉出每個(s1,s2)呢？下面介紹兩種方法。 DFS共5個參數(shù)，分別為：p(當(dāng)前列號)，s1、s2(當(dāng)前行和上

16、一行的覆蓋情況)，b1、b2(上一列的放置對當(dāng)前列兩行的影響，影響為1否則為0)。初始時s1=s2=b1=b2=0。 p=p+1，s1=s1*2+1，s2=s2*2（注意：第i行的放置方案用到第i-1行的某格時，s2中該格應(yīng)為0?。?，b1=b2=0； p=p+1，s1=s1*2+1，s2=s2*2+1，b1=1，b2=0； p=p+1，s1=s1*2，s2=s2*2+1，b1=b2=0。 當(dāng)p移出邊界且b1=b2=0時記錄此方案。 觀察第一種方法，發(fā)現(xiàn)b2始終為0，知這種方法有一定的冗余。換個更自然的方法，去掉參數(shù)b1、b2。 p=p+1，s1=s1*2+1，s2=s2*2； p=p+2，s1

17、=s1*4+3，s2=s2*4+3； p=p+1，s1=s1*2，s2=s2*2+1。 當(dāng)p移出邊界時記錄此方案。 這樣，我們通過改變p的移動距離成功簡化了DFS過程，而且這種方法更加自然。 DFS過程有了，實(shí)現(xiàn)方法卻還有值得討論的地方 前面的例題中，我們?yōu)槭裁纯偸前逊胖梅桨窪FS預(yù)處理保存起來？是因?yàn)椴缓戏ǖ臓顟B(tài)太多，每次都重新DFS太浪費(fèi)時間。 然而回到這個題目，特別是當(dāng)采用第二種時，我們的DFS過程中甚至只有一個判斷(遞歸邊界)，說明根本沒有多少不合法的方案，也就沒有必要把所有方案保存下來，對于每行都重新DFS即可 這個算法時間復(fù)雜度為多少呢？因?yàn)镈FS時以兩行為對象，每行2m，共進(jìn)行n

18、次DFS，所以是O(n*4m)？ 這會使人誤以為本算法無法通過1n、m11的測試數(shù)據(jù)，而實(shí)際上本算法可以瞬間給出m=10,n=11時的解 為了計(jì)算精確的復(fù)雜度，必須先算出DFS得到的方案數(shù)。 考慮當(dāng)前行的放置情況。 如果每格只有兩個選擇，則應(yīng)該有2m種放置方案；如果每格有這3個選擇，且中p只移動一格，則應(yīng)該有3m種放置方案。 然而現(xiàn)在的事實(shí)是：每格有這3個選擇，但中p移動2格，所以可以知道方案數(shù)應(yīng)該在2m和3m之間 考慮第i列，則其必然是： 第i-1列采用達(dá)到； 第i-2列采用達(dá)到。 設(shè)hi表示前i列的方案數(shù)，則得到hi的計(jì)算式： 注意到式子的第二項(xiàng)是多個絕對值小于1的數(shù)的乘積，其對整個hm的

19、影響甚小，故略去，得到方案數(shù)hm0.85*2.414m，符合2mhm3m的預(yù)想。 因?yàn)榭偣策M(jìn)行了n次DFS，每次復(fù)雜度為O(hm)，所以算法總時間復(fù)雜度為O(n*hm)=O(n*0.85*2.414m)，對m=10,n=11不超時也就不足為奇了。應(yīng)用滾動數(shù)組，空間復(fù)雜度為O(2m)。 給出n*m(1n、m9)的方格棋盤，用1*2的矩形的骨牌和L形的(2*2的去掉一個角)骨牌不重疊地覆蓋，求覆蓋滿的方案數(shù)。 SGU.131Hardwood Floor 觀察題目條件，只不過是比上例多了一種L形的骨牌。又因?yàn)楸绢}中兩種骨牌的最大長度和上例一樣，所以本題的狀態(tài)表示與轉(zhuǎn)移方程與上例完全一樣。 上例中有兩

20、種DFS方案，其中第二種實(shí)現(xiàn)起來較第一種簡單。但在本題中，新增的L形骨牌讓第二種DFS難以實(shí)現(xiàn)，故回到第一種DFS。覆蓋情況 條件 參數(shù) s 變化 參數(shù) b 變化 1 0 0 0 0 無 s1 =s1 *2+b1 s2=s2*2 +1 -b2 b1 =0 b2=0 2 0 0 1 1 b1 =0 s1 =s1 *2 +1 s2=s2*2 +1 -b2 b1 = 1 b2=0 3 1 0 1 0 b1 =0 b2=0 s1 =s1 *2 +1 s2=s2*2 b1 =0 b2=0 4 1 0 1 1 b1 =0 b2=0 s1 =s1 *2 +1 s2=s2*2 b1 = 1 b2=0 5 0

21、1 1 1 b1 =0 s1 =s1 *2 +1 s2=s2*2 +1 -b2 b1 = 1 b2= 1 6 1 1 0 1 b2=0 s1 =s1 *2+b1 s2=s2*2 b1 = 1 b2= 1 7 1 1 1 0 b1 =0 b2=0 s1 =s1 *2 +1 s2=s2*2 b1 =0 b2= 1 容易看出，在本題中此種DFS方式實(shí)現(xiàn)很簡單，只要耐心認(rèn)真實(shí)現(xiàn)各種情況。 因?yàn)長形骨牌不太規(guī)則，筆者沒能找到方案數(shù)的一維遞推公式，因此無法給出復(fù)雜度的解析式。但當(dāng)m=9時，算法共生成放置方案79248個，則對于n=m=9,算法的復(fù)雜度為O(9*79248)，可以瞬間出解 和上例一樣，本題也沒有必要保存所有放置方案，同時也避免MLE 棋盤是SCR、SCDP算法很好的用武之地。 上面的例子的很多擴(kuò)展都可以用SC來解決。 例如新的骨牌形狀：2*3、1*k（k較?。┑?應(yīng)用的方式一般為把行或列當(dāng)成階段，把每行的放置方案當(dāng)狀態(tài)，通過枚舉所有放置方案進(jìn)行轉(zhuǎn)移。 上面通過對幾個經(jīng)典的應(yīng)用狀態(tài)壓縮的題目的詳解，從應(yīng)用的角度描述了狀態(tài)壓縮的一般思路。那么如何理解其本質(zhì)呢？ 縱觀上文討論的題目，幾乎都是普普通通的一個遞推公式或者狀態(tài)