状态压缩思想在计算机程序设计中的简单应用

李晓宇　秦文杰

摘 要：随着问题规模增大，可能解的范围会跟着增大，甚至是指数级增长。亦或是在求解时问题状态难以表示。这时就需要考虑状态压缩了。讲解了什么是状态压缩思想，介绍了状态压缩在计算机程序设计的联系，通过几个案例体会如何把状态压缩思想应用到计算机程序设计中，分析了状态压缩在计算机程序设计中的的优势与不足。理解状态压缩的思想，并将其灵活应用于计算机解决实际问题。

关键词：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