状态压缩在信息学竞赛中的应用.pdf

状态压缩 郑州101中学/天津大学 周伟 状态压缩 Abstract 信息学发展势头迅猛，信息学奥赛的题目来源遍及各行各业，经常有一些在 实际应用中很有价值的问题被引入信息学并得到有效解决。然而有一些问题却被 认为很可能不存在有效的(多项式级的)算法，本文以对几个例题的剖析，简述状 态压缩思想及其应用。 Keywords 状态压缩、集合、Hash、NPC Content Introduction 作为OIers，我们不同程度地知道各式各样的算法。这些算法有的以O(logn) 的复杂度运行，如二分查找、欧几里德GCD算法连续两次迭代后的余数至多为( ) O( ) 原数的一半 、平衡树，有的以 n 运行，例如二级索引、块状链表，再往上 p q 有O(n)、O(nlogn)……大部分问题的算法都有一个多项式级别的时间复杂度上 1 2 界 ，我们一般称这类问题为P类(deterministicPolynomial-time)问题，例如在有 向图中求最短路径。然而存在几类问题，至今仍未被很好地解决，人们怀疑他们 根本没有多项式时间复杂度的算法，它们是 NPC(NP-Complete) 和 NPH(NP-Hard)类，例如问一个图是否存在哈密顿圈(NPC)、问一个图是否不存 在哈密顿圈(NPH)、求一个完全图中最短的哈密顿圈 即经典的( TravelingSalesman Problem货郎担问题，NPH)、在有向图中求最长(简单)路径(NPH)，对这些问题 尚不知有多项式时间的算法存在。P 和 NPC 都是 NP(Non-deterministic Polynomial-time)的子集，NPC则代表了NP类中最难的一类问题，所有的NP类 问题都可以在多项式时间内归约到NPC 问题中去。NPH包含了NPC和其他一 些不属于NP(也更难)的问题(即NPC是NP 与NPH 的交集)， NPC 问题的最优 化版本一般是NPH 的，例如问一个图是否存在哈密顿圈是NPC 的，但求最短的 哈密顿圈则是NPH 的，原因在于我们可以在多项式时间内验证一个回路是否真 的是哈密顿回路，却无法在多项式时间内验证其是否是最短的，NP类要求能在 多项式时间内验证问题的一个解是否真的是一个解，所以最优化TSP 问题不是 NP 的，而是NPH 的。存在判定性TSP 问题，它要求判定给定的完全图是否存 在权和小于某常数v 的哈密顿圈，这个问题的解显然可以在多项式时间内验证， 1 2 p q p+1 O O(n) O(n) O(nlogn) O(n ) 请注意，大 符号表示上界，即 的算法可以被认为是 的， 可以被认为是 的。 2 在更正式的定义中，下面提到的概念都只对判定性问题或问题的判定版本才存在。Levin给出了一个适用 Cook 2 于非判定问题的更一般的概念，但他的论文比 的晚发表 年。 1 12 第 页 共 页 状态压缩 郑州101中学/天津大学 周伟 因此它是NP 的，更精确地说是NPC 的。1 如上所述，对于NPC和NPH 问题，至今尚未找到多项式时间复杂度的算法。 然而它们的应用又是如此的广泛，我们不得不努力寻找好的解决方案。毫无疑问， 对于这些问题，使用暴力的搜索是可以得到正确的答案的，但在信息学竞赛那有 限的时间内，很难写出速度可以忍受的暴力搜索。例如对于TSP 问题，暴力搜