李曉宇　秦文杰

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

關(guān)鍵詞：v

0、引言：

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

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

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

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

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

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

3.1康拓展開

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

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

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

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

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

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

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

解決該問題的源碼：代碼托管平臺鏈接[5]

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

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

例如對于54321，把32一起移動到最左端得到32541；再把25一起移動到最右端得到34125；再把12一起移動到最左端得到12345。

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

解決該案例的具體代碼實現(xiàn)，請參考代碼托管平臺鏈接[7]

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

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

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

總結(jié)

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

注解：

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

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

[3] 康拓展開和康拓逆展開的算法實現(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é)在線測評系統(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