狀態(tài)壓縮問(wèn)題

1、狀態(tài)壓縮問(wèn)題謝豐澤簡(jiǎn)介什么是狀態(tài)壓縮？ 有些問(wèn)題，時(shí)刻需要知道問(wèn)題的當(dāng)前狀態(tài)，所以需要的每一個(gè)狀態(tài)進(jìn)行保存，而在計(jì)算機(jī)中，簡(jiǎn)潔快速的二進(jìn)制受到大家表示狀態(tài)時(shí)的青睞，它不僅應(yīng)用于我們常提的DP及搜索，在其他算法解決問(wèn)題是也能起到不同凡響的作用。借助狀態(tài)壓縮可以很好地做到節(jié)約時(shí)間以及節(jié)約空間，避免被卡常數(shù)。八皇后問(wèn)題八數(shù)碼問(wèn)題哈密頓回路搜索-動(dòng)歸題目第一PPT模板網(wǎng)-WWW.1PPT.COMPPT模板下載： 行業(yè)PPT模板： 節(jié)日PPT模板： PPT素材下載： PPT圖表下載： 優(yōu)秀PPT下載： PPT教程： Word教程： Excel教程： 資料下載： PPT課件下載： 范文下載： 試卷下載：

2、教案下載： PPT論壇： 狀態(tài)壓縮預(yù)備知識(shí)名稱名稱C/C+樣式樣式簡(jiǎn)記法則簡(jiǎn)記法則按位與按位與&全一則一全一則一,否則為零否則為零按位或按位或|有一則一有一則一,否則為零否則為零按位取反按位取反是零則一是零則一,是一則零是一則零按位異或按位異或不同則一不同則一,相同則零相同則零左移位左移位aak等價(jià)于等價(jià)于a/2k 作為對(duì)下文的準(zhǔn)備,簡(jiǎn)要介紹一下C+樣式的位運(yùn)算。其優(yōu)先級(jí)：&|第一PPT模板網(wǎng)-WWW.1PPT.COM狀態(tài)壓縮預(yù)備知識(shí)int 取值范圍-232232-1long long 取值范圍-264264-1部分?jǐn)?shù)據(jù)需要加unsigned 一般而言，數(shù)據(jù)會(huì)比較良心，你看數(shù)據(jù)

3、范圍，一旦出現(xiàn)例如小于64的數(shù)，8,32，以及64就試著往狀態(tài)壓縮想，想到不寫錯(cuò)基本此題AC第一PPT模板網(wǎng)-WWW.1PPT.COM特殊應(yīng)用：and: 用以取出一個(gè)數(shù)的某些二進(jìn)制位,配合右移可以快取出一個(gè)數(shù)在二進(jìn)制中指定數(shù)位的值。or ： 將一個(gè)數(shù)的某些位設(shè)為1not： 間接構(gòu)造一些數(shù),如0=232-1(int) xor： 不使用中間變量交換兩個(gè)數(shù)： a=ab;b=ba;a=ab;第一PPT模板網(wǎng)-WWW.1PPT.COM狀態(tài)壓縮引例請(qǐng)求解八皇后問(wèn)題。嚴(yán)禁打樣例 一般做法：使用一個(gè)8*8的數(shù)組存儲(chǔ)當(dāng)前的狀態(tài),然后進(jìn)行搜索。這個(gè)就不再多說(shuō)。但是！8*8=64,喜聞樂(lè)見(jiàn)的64位！ 搜索時(shí),數(shù)組里

4、面存的無(wú)非就是存當(dāng)前位置有沒(méi)有皇后,使用一個(gè)LL去存儲(chǔ)當(dāng)前的狀態(tài),然后通過(guò)存的狀態(tài)去搜索即可,狀態(tài)的修改通過(guò)位移以及位運(yùn)算符進(jìn)行修改即可,大大節(jié)約空間和時(shí)間（這也是節(jié)約能源啊）！第一PPT模板網(wǎng)-WWW.1PPT.COM狀態(tài)壓縮引例關(guān)于一些具體實(shí)踐的問(wèn)題：初始化一個(gè)棋盤，默認(rèn)全空，即全0，連續(xù)64個(gè)0(二進(jìn)制下）假設(shè)棋盤放了皇后，放置成這樣：則用二進(jìn)制表示為1(9個(gè)0)1(53個(gè)0)如果要在某個(gè)位置放一個(gè)皇后，表達(dá)式為p=p|(1xx)例如，在(7,6)處放置一個(gè)皇后，xx為8*(8-7)+(8-6),也就是將一個(gè)二維坐標(biāo)轉(zhuǎn)為1維然后存入一個(gè)數(shù)組中。在棋盤某處移除一個(gè)皇后，表達(dá)式為p=p(1x

5、x)。思考：棋盤某處移除一個(gè)皇后：第一PPT模板網(wǎng)-WWW.1PPT.COM狀態(tài)壓縮例1 給你多組超大整數(shù),每組2個(gè)求和。 樸素做法：開(kāi)2個(gè)數(shù)組去存每一位整數(shù),按照10進(jìn)制模擬加法。 然而,良心的數(shù)據(jù)經(jīng)過(guò)精確計(jì)算,可以完美地卡你的常數(shù),包括內(nèi)存和時(shí)間,常規(guī)方法（也就是一個(gè)整數(shù)位置只存1位的方法）只能夠拿40分。1234567890例如,整數(shù)1234567890放入數(shù)組中的方法。第一PPT模板網(wǎng)-WWW.1PPT.COM狀態(tài)壓縮例1 數(shù)組中許多空間被白白浪費(fèi)了,比如最小的char,可以存上2位（099）,然而你只用了1位（09）空間,時(shí)間就這樣被白白地浪費(fèi)了,MLE,TLE就是這么構(gòu)成的。 也許

6、,我們應(yīng)該拋棄十進(jìn)制,選用更高的進(jìn)制去計(jì)算。 美妙的事情：int的取值范圍上線為2147483647,并且2*1,000,000,000232-1,也許可以采用十億進(jìn)制進(jìn)行計(jì)算。采用十億進(jìn)制將整數(shù)1234567890放入數(shù)組中：1234567890第一PPT模板網(wǎng)-WWW.1PPT.COM狀態(tài)壓縮例2 求解八數(shù)碼問(wèn)題，給出1個(gè)目標(biāo)矩陣和初始矩陣，要求使用狀態(tài)壓縮求解，請(qǐng)?jiān)O(shè)計(jì)出一個(gè)適用于八數(shù)碼問(wèn)題求解的數(shù)據(jù)結(jié)構(gòu)。二進(jìn)制？ 首先分析，八數(shù)碼，有8個(gè)數(shù)字，加上空格用0補(bǔ)上，剛好9個(gè)數(shù)字，將這9個(gè)數(shù)字串起來(lái)存入一個(gè)int中即可（體現(xiàn)出int取值范圍的無(wú)比優(yōu)越）。不過(guò)，這里的操作會(huì)相對(duì)復(fù)雜一些，具體詳見(jiàn)

7、本人代碼。第一PPT模板網(wǎng)-WWW.1PPT.COM狀態(tài)壓縮之矩陣狀壓 給你們一個(gè)迷宮，請(qǐng)走迷宮，格式：0代表可通路，1代表墻，請(qǐng)走該迷宮。有多組數(shù)據(jù)。 良心的數(shù)據(jù)會(huì)卡常數(shù)，常規(guī)方法會(huì)MLE。 常規(guī)存儲(chǔ)的方法：對(duì)于每一個(gè)0或者1，對(duì)應(yīng)地使用數(shù)組中的1個(gè)變量存儲(chǔ)，32個(gè)位置就要用數(shù)組中對(duì)應(yīng)的32個(gè)變量存儲(chǔ)。然而會(huì)MLE。 改進(jìn)方法如圖：原方法改進(jìn)方法使用1個(gè)int存儲(chǔ)棋盤中32個(gè)位置的信息。第一PPT模板網(wǎng)-WWW.1PPT.COM 題目要將3年都講不完（因?yàn)槲抑v題的速度比不過(guò)長(zhǎng)臂猿出題的速度。第一PPT模板網(wǎng)-WWW.1PPT.COM 狀態(tài)壓縮是一種思想，理論上在任何有“狀態(tài)”的算法中都可以應(yīng)用。 這里只是對(duì)其應(yīng)用進(jìn)行了簡(jiǎn)單的闡述。 經(jīng)過(guò)應(yīng)用的磨練，總有一天狀態(tài)壓縮會(huì)進(jìn)入每個(gè)oier的潛意識(shí)中。