狀態壓縮思想在計算機程序設計中的簡單應用

李曉宇　秦文杰

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

關鍵詞：v

0、引言：

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

1、什么是狀態壓縮思想

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

2、狀態壓縮思想與計算機程序設計的聯系

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

3、狀態壓縮思想在計算機程序設計中的應用

3.1康拓展開

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

利用康拓展開可以解決經典的八數碼問題的狀態表示

康拓展開和康拓逆展開算法實現鏈接[3]

3.2 Flip Game[4] 翻轉棋子

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

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

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

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

3.3 hihocoder Offer收割19th 數組重排3 [6]

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

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

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

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

4、狀態壓縮方法在計算機程序設計中的不足與優勢

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

不足：當問題規模增大時，使用狀態壓縮可能也無法完全表示所有的狀態。例如用康拓展開表示N元序列的狀態時，當序列多一個元素，問題狀態空間將乘以（N + 1），這個狀態增加是非常快的。需要使用其他方法解決問題，或者找到更優的狀態表示方法。

總結

在計算機程序設計中，狀態壓縮將問題的表象狀態抽象成了簡潔的形式化狀態，便于計算機處理。狀態壓縮是一種思想。實現狀態壓縮的方法很多。不同的問題往往需要考慮不同的狀態表示及轉換方法。在解決問題時，注意總結經驗。

注解：

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

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

[3] 康拓展開和康拓逆展開的算法實現，百度百科鏈接

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

[4] Flip Game 翻轉棋子，北京大學在線測評系統 第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 數組重排3 題目鏈接（需登錄查看）

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

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

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