状态压缩问题

1、状态压缩问题谢丰泽简介什么是状态压缩？ 有些问题，时刻需要知道问题的当前状态，所以需要的每一个状态进行保存，而在计算机中，简洁快速的二进制受到大家表示状态时的青睐，它不仅应用于我们常提的DP及搜索，在其他算法解决问题是也能起到不同凡响的作用。借助状态压缩可以很好地做到节约时间以及节约空间，避免被卡常数。八皇后问题八数码问题哈密顿回路搜索-动归题目第一PPT模板网-WWW.1PPT.COMPPT模板下载： 行业PPT模板： 节日PPT模板： PPT素材下载： PPT图表下载： 优秀PPT下载： PPT教程： Word教程： Excel教程： 资料下载： PPT课件下载： 范文下载： 试卷下载：

2、教案下载： PPT论坛： 状态压缩预备知识名称名称C/C+样式样式简记法则简记法则按位与按位与&全一则一全一则一,否则为零否则为零按位或按位或|有一则一有一则一,否则为零否则为零按位取反按位取反是零则一是零则一,是一则零是一则零按位异或按位异或不同则一不同则一,相同则零相同则零左移位左移位aak等价于等价于a/2k 作为对下文的准备,简要介绍一下C+样式的位运算。其优先级：&|第一PPT模板网-WWW.1PPT.COM状态压缩预备知识int 取值范围-232232-1long long 取值范围-264264-1部分数据需要加unsigned 一般而言，数据会比较良心，你看数据

3、范围，一旦出现例如小于64的数，8,32，以及64就试着往状态压缩想，想到不写错基本此题AC第一PPT模板网-WWW.1PPT.COM特殊应用：and: 用以取出一个数的某些二进制位,配合右移可以快取出一个数在二进制中指定数位的值。or ： 将一个数的某些位设为1not： 间接构造一些数,如0=232-1(int) xor： 不使用中间变量交换两个数： a=ab;b=ba;a=ab;第一PPT模板网-WWW.1PPT.COM状态压缩引例请求解八皇后问题。严禁打样例 一般做法：使用一个8*8的数组存储当前的状态,然后进行搜索。这个就不再多说。但是！8*8=64,喜闻乐见的64位！ 搜索时,数组里

4、面存的无非就是存当前位置有没有皇后,使用一个LL去存储当前的状态,然后通过存的状态去搜索即可,状态的修改通过位移以及位运算符进行修改即可,大大节约空间和时间（这也是节约能源啊）！第一PPT模板网-WWW.1PPT.COM状态压缩引例关于一些具体实践的问题：初始化一个棋盘，默认全空，即全0，连续64个0(二进制下）假设棋盘放了皇后，放置成这样：则用二进制表示为1(9个0)1(53个0)如果要在某个位置放一个皇后，表达式为p=p|(1xx)例如，在(7,6)处放置一个皇后，xx为8*(8-7)+(8-6),也就是将一个二维坐标转为1维然后存入一个数组中。在棋盘某处移除一个皇后，表达式为p=p(1x

5、x)。思考：棋盘某处移除一个皇后：第一PPT模板网-WWW.1PPT.COM状态压缩例1 给你多组超大整数,每组2个求和。 朴素做法：开2个数组去存每一位整数,按照10进制模拟加法。 然而,良心的数据经过精确计算,可以完美地卡你的常数,包括内存和时间,常规方法（也就是一个整数位置只存1位的方法）只能够拿40分。1234567890例如,整数1234567890放入数组中的方法。第一PPT模板网-WWW.1PPT.COM状态压缩例1 数组中许多空间被白白浪费了,比如最小的char,可以存上2位（099）,然而你只用了1位（09）空间,时间就这样被白白地浪费了,MLE,TLE就是这么构成的。 也许

6、,我们应该抛弃十进制,选用更高的进制去计算。 美妙的事情：int的取值范围上线为2147483647,并且2*1,000,000,000232-1,也许可以采用十亿进制进行计算。采用十亿进制将整数1234567890放入数组中：1234567890第一PPT模板网-WWW.1PPT.COM状态压缩例2 求解八数码问题，给出1个目标矩阵和初始矩阵，要求使用状态压缩求解，请设计出一个适用于八数码问题求解的数据结构。二进制？ 首先分析，八数码，有8个数字，加上空格用0补上，刚好9个数字，将这9个数字串起来存入一个int中即可（体现出int取值范围的无比优越）。不过，这里的操作会相对复杂一些，具体详见

7、本人代码。第一PPT模板网-WWW.1PPT.COM状态压缩之矩阵状压 给你们一个迷宫，请走迷宫，格式：0代表可通路，1代表墙，请走该迷宫。有多组数据。 良心的数据会卡常数，常规方法会MLE。 常规存储的方法：对于每一个0或者1，对应地使用数组中的1个变量存储，32个位置就要用数组中对应的32个变量存储。然而会MLE。 改进方法如图：原方法改进方法使用1个int存储棋盘中32个位置的信息。第一PPT模板网-WWW.1PPT.COM 题目要将3年都讲不完（因为我讲题的速度比不过长臂猿出题的速度。第一PPT模板网-WWW.1PPT.COM 状态压缩是一种思想，理论上在任何有“状态”的算法中都可以应用。 这里只是对其应用进行了简单的阐述。 经过应用的磨练，总有一天状态压缩会进入每个oier的潜意识中。