日归档：2012 年 08 月 26 日

作者：杨超 本文地址：http://sokoban.ws/blog/?p=630 之前写过一篇博文介绍了一系列具有递归关系和指数长度答案的推箱子关卡。本文给出判断推箱子关卡是否有解的多项式空间的算法。这两篇博文结合起来，可以对计算复杂性理论里面的PSPACE问题的概念有比较直观的理解。推箱子游戏是一个非常好的PSPACE问题的例子。 一、P, NP和PSPACE 先定义推箱子问题。本文中说的推箱子问题，是指如下的一个判断性的问题：给出一个推箱子关卡，这个关卡是否有解？注意这里只判断是否有解，也就是说只要回答“是“或“否“，如果回答“是“，也不需要给出一个具体可行的lurd答案。 判断一个推箱子关卡是否有解，是一个PSPACE完全(PSPACE-complete)问题。PSPACE-complete问题是计算复杂性理论里面的一个术语。PSPACE-complete 所讨论的是推箱子问题的空间复杂度。简单地说，空间就可以理解为计算机的内存。我们假设一个推箱子关卡宽度为w，高度为h，则我们称这个推箱子关卡的大小为n=w*h。显然，一个关卡越大，我们用程序去计算关卡是否可解时，需要的内存就越多。PSPACE-complete 有两层意思。第一层意思是推箱子问题存在多项式空间的算法，也就是说存在一个算法A，这个算法对大小为n的推箱子关卡，最多使用$ n^k $(k是某一个与关卡无关的常数)的大小的内存就能回答出这个关卡是否可解。当然，所用的时间没有限定。第二层意思是推箱子问题是所有多项式空间可解的问题里面最难的一类。PSPACE表示所有多项式空间可解问题的全体，PSPACE-complete是PSPACE 的一个子集，是里面最难的那些问题的全体。这里“最难“是有严格的数学定义的，在此我们直观地认为从空间复杂度考虑最难就可以了。 计算复杂性理论的完整的理论体系建立于20世纪的70年代(1970年代)。而推箱子最早被证明是PSPACE-complete问题是在上世纪90年代末。就像我们前面解释的那样，证明推箱子问题是PSPACE-complete问题有两个要点。一是要说明推箱子是多项式空间可解的。二就是说明推箱子问题是多项式可空间可解问题里面最难的。其中第一点比较容易，本文的目的是给出一个判断推箱子关卡是否有解的多项式空间的算法。注意，这个算法只是理论上有意义，不适宜用来实际求解。在实践中，大多推箱子求解程序使用大量的内存，往往是随推箱子关卡大小呈指数增长。 在具体讨论算法之前，先说些题外话。前些年，媒体曾热炒过“庞加莱猜想”，这是Clay数学研究所(Clay Mathematics Institute)于2000年悬赏100万美元的七个尚未解决的数学问题之一，每个100万美元。其中“庞加莱猜想”最近已经被解决了。2010年，这个百万大奖授予俄罗斯数学家佩雷尔曼(Grigoriy Perelman)。但佩雷尔曼拒绝接受这个奖项和奖金。 在其他六个尚未解决的价值百万美元的问题中，有一个是属于理论计算机科学里面的问题，更具体地说是关于计算复杂性理论的问题：即 P vs NP问题。 我们用P来表示所有能用多项式时间(注意是时间，不是空间，区别于PSPACE)算法解决的判断问题全体。用NP表示所有所有能用“非确定性(Non-deterministic)”多项式时间算法的判断问题全体。可以证明，任何一个P问题都一定是NP问题，也就是说P是NP的子集。但是现在尚未确定的是，究竟P是NP的真子集，还是P=NP?这就是所谓的P vs NP问题，七个百万问题之一。 P和 NP都是从时间复杂度上考虑的，而PSPACE是从空间复杂度上考虑的。大家很自然会问，有没有NPSPACE问题？也就是说是否有“非确定性“多项式空间算法问题的全体呢？有的。但是作为著名的Savitch定理的一个推论，可以证明PSPACE=NPSPACE。即两者实际上是同一个集合，因此一般只提PSPACE。 Savitch定理是由Walter Savitch 于1970年证明的。我搜索了一下他的主页，发现他主页(http://cseweb.ucsd.edu/users/savitch/) 上照片似乎是在中国照的，大家可以去看看。这里提到Savitch定理的一个重要原因是下面介绍的算法是基于Savitch定理(参看[1])的证明设计的。 （图片来自Walter Savitch的个人主页） 可以证明，凡NP问题都是PSPACE问题，NP是PSPACE的子集。那么究竟NP是PSPACE的真子集，还是NP=PSPACE？这也是一个悬而未决的问题。多数数学家和理论计算机学家都倾向于认为P，NP和PSPACE三者，前一个都是后一个的真子集，也就是可用下图示意： 二、判断推箱子关卡是否有解的多项式空间的算法 下面开始讨论算法。 我们知道一个大小为n的关卡，实际有效的格子实际上是小于n的，但我们不妨设就是n。每个格子要么是箱子，要么是人，要么什么也没有，所以所能形成的不同的局面不会超过$ 3^n $种（事实上$ 3^n $高估了所有可能的局面数，但从数量级上是基本一致的），其中有一个局面是初始局面，有一个是目标局面。所以，如果一个关卡是可解的，一定在$ … 继续阅读 →