2024年4月30日发(作者：)
状态压缩 郑州101中学/天津大学 周伟
状态压缩
Abstract
信息学发展势头迅猛，信息学奥赛的题目来源遍及各行各业，经常有一些在
实际应用中很有价值的问题被引入信息学并得到有效解决。然而有一些问题却被
认为很可能不存在有效的(多项式级的)算法，本文以对几个例题的剖析，简述状
态压缩思想及其应用。
Keywords
状态压缩、Hash、动态规划、递推
Content
Introduction
作为OIers，我们不同程度地知道各式各样的算法。这些算法有的以O(logn)
的复杂度运行，如二分查找、欧几里德GCD算法(连续两次迭代后的余数至多为
原数的一半)、平衡树，有的以O(
n
)运行，例如二级索引、块状链表，再往上
有O(n)、O(n
p
log
q
n)……大部分问题的算法都有一个多项式级别的时间复杂度上
界
1
，我们一般称这类问题
2
为P (deterministic Polynomial-time) 类问题，例如在
有向图中求最短路径。然而存在几类问题，至今仍未被很好地解决，人们怀疑他
们根本没有多项式时间复杂度的算法，NPC(NP-Complete)和NPH(NP-Hard)就是
其中的两类，例如问一个图是否存在哈密顿圈(NPC)、问一个图是否不存在哈密
顿圈(NPH)、求一个完全图中最短的哈密顿圈(即经典的Traveling Salesman
Problem货郎担问题，NPH)、在有向图中求最长(简单)路径(NPH)，对这些问题
尚不知有多项式时间的算法存在。P和NPC都是NP(Non-deterministic
Polynomial-time)的子集，NPC则代表了NP类中最难的一类问题，所有的NP类
问题都可以在多项式时间内归约到NPC问题中去。NPH包含了NPC和其他一
些不属于NP(也更难)的问题， NPC问题的函数版本(相对于判定性版本)一般是
NPH的，例如问一个图是否存在哈密顿圈是NPC的，但求最短的哈密顿圈则是
NPH的，原因在于我们可以在多项式时间内验证一个回路是否真的是哈密顿回
路，却无法在多项式时间内验证其是否是最短的，NP类要求能在多项式时间内
验证问题的一个解是否真的是一个解，所以最优化TSP问题不是NP的，而是
NPH的。存在判定性TSP问题，它要求判定给定的完全图是否存在权和小于某
常数v的哈密顿圈，这个问题的解显然可以在多项式时间内验证，因此它是NP
1
请注意，大O符号表示上界，即O(n)的算法可以被认为是O(n
2
)的，O(n
p
log
q
n)可以被认为是O(n
p+1
)的。
2
在更正式的定义中，下面提到的概念都只对判定性问题或问题的判定版本才存在(NPH除外)。Levin给出
了一个适用于非判定问题的更一般的概念，但他的论文比Cook的晚发表2年。
第 1 页
共 16 页
状态压缩 郑州101中学/天津大学 周伟
的，更精确地说是NPC的。
1
如上所述，对于NPC和NPH问题，至今尚未找到多项式时间复杂度的算法。
然而它们的应用又是如此的广泛，我们不得不努力寻找好的解决方案。毫无疑问，
对于这些问题，使用暴力的搜索是可以得到正确的答案的，但在信息学竞赛那有
限的时间内，很难写出速度可以忍受的暴力搜索。例如对于TSP问题，暴力搜
索的复杂度是O(n!)，如此高的复杂度使得它对于高于10的数据规模就无能为力
了。那么，有没有一种算法，它可以在很短的时间内实现，而其最坏情况下的表
现比搜索好呢？答案是肯定的——状态压缩(States Compression
，
SC)。
作为对下文的准备，这里先为使用Pascal的OIers简要介绍一下C/C++样式
的位运算(bitwise operation)。
一、基本运算符
名称 C/C++样式 Pascal样式 简记法则
and
按位与 全一则一
&
(bitwise AND)
否则为零
or
有一则一 按位或
|
(bitwise OR)
否则为零
not
按位取反 是零则一
~
(bitwise NOT)
是一则零
xor
按位异或 不同则一
^
(bitwise XOR)
相同则零
以上各运算符的优先级从高到低依次为：
~,&,^,|
二、特殊应用
a) and：
i. 用以取出一个数的某些二进制位
ii. 取出一个数二进制中的最后一个1(lowbit)
2
：x&-x
b) or ：用以将一个数的某些位设为1
c) not：用以间接构造一些数：~0u=4294967295=2
32
-1
d) xor：
i. 不使用中间变量交换两个数：a=a^b;b=a^b;a=a^b;
ii. 将一个数的某些位取反
有了这些基础，就可以开始了。
1
不应该混淆P
、
NP
、
NPC
、
NPH的概念。这里只是粗略介绍，详见关于算法分析的书籍(实际上一篇paper
根本讲不完，因为还有co-NP
、
co-NPC
、
#P
、
#PC……后文会给出一个#PC的例子)，这会使新手读者的理
论水平上一个台阶。弄不明白也没关系，基本不影响对本文其他部分的理解^_^
具有同样作用的还有
(x-1)&x^x,
这个的道理更容易理解。lowbit在树状数组(某种数据结构)中可以用
到，这里不再单独介绍，感兴趣的可以参阅各牛的论文，或者加我QQ。建议掌握，否则可能会看不懂我
的部分代码。
2
第 2 页
共 16 页
发布者：admin，转转请注明出处：http://www.yc00.com/news/1714423144a2443550.html
评论列表（0条）