狀態(tài)壓縮思想在計(jì)算機(jī)程序設(shè)計(jì)中的簡單應(yīng)用

李曉宇　秦文杰

摘 要：隨著問題規(guī)模增大，可能解的范圍會(huì)跟著增大，甚至是指數(shù)級(jí)增長。亦或是在求解時(shí)問題狀態(tài)難以表示。這時(shí)就需要考慮狀態(tài)壓縮了。講解了什么是狀態(tài)壓縮思想，介紹了狀態(tài)壓縮在計(jì)算機(jī)程序設(shè)計(jì)的聯(lián)系，通過幾個(gè)案例體會(huì)如何把狀態(tài)壓縮思想應(yīng)用到計(jì)算機(jī)程序設(shè)計(jì)中，分析了狀態(tài)壓縮在計(jì)算機(jī)程序設(shè)計(jì)中的的優(yōu)勢(shì)與不足。理解狀態(tài)壓縮的思想，并將其靈活應(yīng)用于計(jì)算機(jī)解決實(shí)際問題。

關(guān)鍵詞：v

0、引言：

隨著計(jì)算機(jī)的快速發(fā)展，人們發(fā)現(xiàn)越來越多的問題可用計(jì)算機(jī)快速準(zhǔn)確方便地解決。一般，計(jì)算機(jī)解決問題主要靠計(jì)算搜索。若無法直接去計(jì)算求解，可用計(jì)算機(jī)以每秒計(jì)算百萬次的速度在可能的解空間中搜索。但是，問題規(guī)模較大時(shí)，需要消耗大量的計(jì)算機(jī)資源，如：內(nèi)存，時(shí)間。而且有的問題狀態(tài)難以用簡潔的數(shù)據(jù)結(jié)構(gòu)描述，這時(shí)判斷狀態(tài)是否是更優(yōu)解也就更加麻煩。于是，狀態(tài)壓縮思想也就產(chǎn)生了。狀態(tài)壓縮可用于降低計(jì)算機(jī)內(nèi)存消耗，減小判斷解是否更優(yōu)的復(fù)雜度和時(shí)間。

1、什么是狀態(tài)壓縮思想

根據(jù)對(duì)問題狀態(tài)的理解，思維上對(duì)問題進(jìn)行抽象。把一個(gè)問題的狀態(tài)用另一種在效果上等價(jià)的更加簡化的狀態(tài)來代替。通常，新的狀態(tài)表示更加簡單，可能是脫離了問題實(shí)際意義的一種數(shù)學(xué)表示法。問題原始狀態(tài)必須和新的狀態(tài)一一對(duì)應(yīng)，新的狀態(tài)可以轉(zhuǎn)化為原始問題狀態(tài)。

2、狀態(tài)壓縮思想與計(jì)算機(jī)程序設(shè)計(jì)的聯(lián)系

在使用計(jì)算機(jī)解決實(shí)際問題時(shí)，必須把實(shí)際問題轉(zhuǎn)化成計(jì)算機(jī)可以理解并進(jìn)行計(jì)算求解的形式。若直接把問題狀態(tài)簡單地轉(zhuǎn)化為某種數(shù)據(jù)結(jié)構(gòu)，很可能效率更低甚至是資源耗費(fèi)過大。這時(shí)就需要在數(shù)據(jù)結(jié)構(gòu)上進(jìn)行抽象表示。能用數(shù)字表示的，就不用復(fù)合數(shù)據(jù)結(jié)構(gòu)去表示；能用位表示的，就可以提高效率，節(jié)省時(shí)間空間。狀態(tài)壓縮思想，盡量使問題轉(zhuǎn)太表示更加簡單，更加容易操作。

3、狀態(tài)壓縮思想在計(jì)算機(jī)程序設(shè)計(jì)中的應(yīng)用

3.1康拓展開

康拓展開可以得到一個(gè)排列在全排列中的次序。例如，一個(gè)序列有n個(gè)互不相同的元素組成，那么這n個(gè)元素就用（n?。?個(gè)排列情況（若n較大，則轉(zhuǎn)態(tài)空間急劇增大）。隨機(jī)給出這n個(gè)元素的一個(gè)排列，就可以求出這個(gè)排列在全排列中的位置，次序。這個(gè)次序是一個(gè)整數(shù)，就可以用這個(gè)整數(shù)代替這個(gè)序列。于是，一維序就映射為了一個(gè)整數(shù)，大大降低了存儲(chǔ)這個(gè)序列狀態(tài)表示所需的空間。而且，n 個(gè)元素序列對(duì)應(yīng)n個(gè)整數(shù)，可以把一個(gè)整數(shù)還原為一個(gè)由n個(gè)元素組成的一個(gè)排列狀態(tài)。

利用康拓展開可以解決經(jīng)典的八數(shù)碼問題的狀態(tài)表示

康拓展開和康拓逆展開算法實(shí)現(xiàn)鏈接[3]

3.2 Flip Game[4] 翻轉(zhuǎn)棋子

翻轉(zhuǎn)棋子問題描述：在一個(gè)4x4的棋盤上擺滿了16個(gè)黑白棋子。每次可以翻轉(zhuǎn)某個(gè)棋子及其相鄰的棋子。翻轉(zhuǎn)規(guī)則：白色變黑色，黑色變白色。若可以將這盤16個(gè)棋子翻轉(zhuǎn)為純色（全白或全黑），則游戲勝利（翻轉(zhuǎn)次數(shù)不限）。

這個(gè)問題可以用搜索，棋盤的狀態(tài)總共就用65536（1 << 16 = 2^16）種，肯定是可以判斷出是否可以翻轉(zhuǎn)為純色的。那么問題的關(guān)鍵就是，如何表示這盤棋子的狀態(tài)？若簡單地用一個(gè)二維數(shù)組表示這個(gè)棋盤狀態(tài)，那么需要65536個(gè)矩陣，而且判斷是否已搜索過某個(gè)狀態(tài)需要的時(shí)間是判斷矩陣是否相同。

若運(yùn)用狀態(tài)壓縮的思想，抽象問題。把黑白棋看做0或1。則一盤棋就由16個(gè)1或0組成。將這16個(gè)01排列一塊，就是一個(gè)整數(shù)。這就巧妙地把一個(gè)二維棋盤狀態(tài)轉(zhuǎn)化成了一個(gè)數(shù)字，大大降低了內(nèi)存的消耗。而且判斷兩個(gè)數(shù)字是否相等，遠(yuǎn)快于判斷矩陣是否相同。

解決該問題的源碼：代碼托管平臺(tái)鏈接[5]

3.3 hihocoder Offer收割19th 數(shù)組重排3 [6]

給定一個(gè){1..N}的排列A1， A2， ... AN，每一次操作可以將相鄰的兩個(gè)數(shù)一起移動(dòng)（保持兩個(gè)數(shù)相鄰且前后順序不變）到任意位置。詢問至少經(jīng)過多少次操作，可以使得原序列變?yōu)?， 2， ...， N（N最大為8）。

例如對(duì)于54321，把32一起移動(dòng)到最左端得到32541；再把25一起移動(dòng)到最右端得到34125；再把12一起移動(dòng)到最左端得到12345。

解決這個(gè)問題時(shí)，需要注意范圍，N最大為8，就不能直接簡單用整數(shù)作為排列的狀態(tài)了，因?yàn)?7654321很大，需要花費(fèi)的空間太大。需要注意到，每個(gè)位上的數(shù)字最大為8，3個(gè)bit位就可以存下了。所以對(duì)于這樣的每位都不大于8的8位數(shù)整數(shù)，需要（3個(gè)bit * 8）24個(gè)bit位，需要16777216（1700萬）個(gè)整數(shù)來表示所有狀態(tài)。 這就在整數(shù)的基礎(chǔ)上，從微觀的位上考慮，進(jìn)一步壓縮抽象問題的狀態(tài)。當(dāng)進(jìn)行狀態(tài)轉(zhuǎn)換時(shí)，可以用位操作實(shí)現(xiàn)。截取幾個(gè)字節(jié)中的某些位時(shí)，可以用移位和位操作與或。對(duì)于這個(gè)案例，處理好狀態(tài)抽象表示和轉(zhuǎn)換后，就是搜索是否可以翻轉(zhuǎn)為純色棋盤了。

解決該案例的具體代碼實(shí)現(xiàn)，請(qǐng)參考代碼托管平臺(tái)鏈接[7]

4、狀態(tài)壓縮方法在計(jì)算機(jī)程序設(shè)計(jì)中的不足與優(yōu)勢(shì)

優(yōu)勢(shì)：狀態(tài)壓縮解決了計(jì)算機(jī)在處理問題時(shí)，問題狀態(tài)的表示及優(yōu)化；提高了程序的速度，節(jié)省了內(nèi)存消耗。便于使用搜索策略，在解空間中快速尋找更優(yōu)解。

不足：當(dāng)問題規(guī)模增大時(shí)，使用狀態(tài)壓縮可能也無法完全表示所有的狀態(tài)。例如用康拓展開表示N元序列的狀態(tài)時(shí)，當(dāng)序列多一個(gè)元素，問題狀態(tài)空間將乘以（N + 1），這個(gè)狀態(tài)增加是非?？斓?。需要使用其他方法解決問題，或者找到更優(yōu)的狀態(tài)表示方法。

總結(jié)

在計(jì)算機(jī)程序設(shè)計(jì)中，狀態(tài)壓縮將問題的表象狀態(tài)抽象成了簡潔的形式化狀態(tài)，便于計(jì)算機(jī)處理。狀態(tài)壓縮是一種思想。實(shí)現(xiàn)狀態(tài)壓縮的方法很多。不同的問題往往需要考慮不同的狀態(tài)表示及轉(zhuǎn)換方法。在解決問題時(shí)，注意總結(jié)經(jīng)驗(yàn)。

注解：

[1] 李曉宇 鄭州大學(xué)信息工程學(xué)院老師

[2] 秦文杰 鄭州大學(xué)信息工程學(xué)院軟件工程系2015級(jí)2班的一個(gè)學(xué)生，學(xué)號(hào)20152480225

[3] 康拓展開和康拓逆展開的算法實(shí)現(xiàn)，百度百科鏈接

https：//baike.baidu.com/item/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80/7968428？fr=aladdin

[4] Flip Game 翻轉(zhuǎn)棋子，北京大學(xué)在線測評(píng)系統(tǒng) 第1753題。鏈接

http：//poj.org/problem？id=1753

[5] 解決Flip Game問題的源碼（C++語言）鏈接

https：//github.com/zzuwenjie/coding18/blob/master/OJ/poj1753.cpp

[6] Hihcoder Offer收割19th 數(shù)組重排3 題目鏈接（需登錄查看）

https：//hihocoder.com/problemset/problem/1539

[7] Hihocoder Offer收割19th 數(shù)組重排3，解題源碼鏈接

https：//github.com/zzuwenjie/coding18/blob/master/OJ/hihocoder19_1539.cpp