分类目录归档:数学

量子计算机能快速求解推箱子关卡吗?

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=3757 量子计算机常被大众媒体描述得十分神奇,甚至有科学家也添油加醋,如 David Deutsch 的 The Fabric of Reality 一书。用量子计算机能设计出快速求解推箱子关卡的算法吗?我在读了David Deutsch的书后,对此问题颇感兴趣。这个月,阅读了不少相关文献,找到了答案。答案是否定的。 首先,制造出通用的量子计算机仍然有极大的工程技术困难。 第二,再看看理论上,量子算法能干什么。最有名的量子算法就是Peter Shor的整数分解算法,这一算法使得基于大数分解比较困难的公钥加密算法岌岌可危。Shor的算法是1994年提出(Shor因此获得哥德尔奖Godel Prize),历史也没有太长。想要知道这一算法与传统计算机算法有何不同,可读Scott Aaronson的博文 《Shor, I’ll do it》。Scott Aaronson生于1981年,才36岁,是德州大学奥斯汀分校的教授,在理论计算机科学特别是计算复杂度理论方面有非常高的造诣。他博文中对Shor算法的核心解释得深入浅出。关键是整数分解还是有某种规律,量子算法恰恰能更好地利用这一规律,一定程度上避免了暴力穷举。 要注意的是,整数分解并非特别难的问题。在基于传统计算机(图灵机)的计算复杂度理论中,整数分解被认为不属于P,但也只是比P问题略难一些,介于P和NP-Complete之间,且更靠近P。因此,量子算法能快速分解大数也只是情理之中。 知道量子算法是怎么做的,能做什么,就更好地理解量子算法不能做什么。Scott Aaronson博客的站名banner位置有这么一段话,澄清大众对量子计算的误解: If you take just one piece of information from this blog: Quantum computers would … 继续阅读

发表在 推箱子, 数学, 算法, 计算机 | 留下评论

写在推箱子比赛第一百期之际

  本文地址:http://sokoban.ws/blog/?p=3627 作者:杨超 接触推箱子这个游戏已经近20年,发起在线推箱子比赛至今已8年有余。比赛每月一期,现在正进行第100期。由于这个比赛,使得我业余持续地关注推箱子游戏,并且推箱子游戏也持续地给我带来很大的乐趣。趁着第一百期之际,谈谈推箱子是什么,以及推箱子给我所带来的精神上的快乐。 一、推箱子是什么? 推箱子是一种成本极其低的智力消遣活动。早在推箱子出现之前,姜长英在1949年《论消遣》一文就分析过平民化的科学消遣的好处。最近看到《三联生活周刊》特约作者“土摩托”袁越在新浪微博问答中也表达了类似的观点:“……精神追求的成本越来越低了……我觉得这才是人类的未来,因为这是一种低成本满足所有人的唯一方式……”。 所以,以推箱子为爱好的朋友是非常幸福的,这玩意几乎不需要花钱。因为推箱子是一款纯软件产品。只要一个计算机系统足够开放和普遍,它上面一定会出现优秀且免费的推箱子软件,如Windows系统,如安卓系统。即便比较封闭的系统,如掌上游戏机、电子词典、电视机、机顶盒等等,都会出现推箱子。 我们举办网上的推箱子比赛的服务器成本也相当低。两个域名(sokoban.cn 和 sokoban.ws)加上租用服务器虚拟空间,平均每个月只要约28元,只相当吃一顿快餐。这么低的成本就可以把分散在全国乃至全世界各地的顶尖推箱子爱好者聚在一起,举办全世界水平最高的推箱子比赛,可算奇迹了。 这主要还是得益于电子计算机和互联网的快速发展。就最近来说,触屏式的智能手机只用了不到十年,就发展得非常成熟了,几乎取代了台式电脑,成为人们上网的主要设备。就我自己而言,微信等APP已经成为我获取信息的最重要渠道之一。很多跑步活动的信息我都是最先从微信获得,甚至就在微信中完成报名的。 因此,2014年7月,比赛网站也开通了微信订阅号,主要推送比赛开始等相关信息。继《推箱子加加》之后,愉翁又为安卓平台发布了《推箱快手》这款功能强大的APP。而苹果手机因系统较为封闭,虽是智能手机的引领者,却一直未见优秀的推箱子软件出现在该平台。 二、推箱子给我带来的快乐 下面罗列一些在推箱子中得到的快乐,其中很多事情做成了之后当时能高兴好几天。 为了测试各种平台下的推箱子,尝试了不同的操作系统。特别是编译运行了早期Linux平台下的XSokoban。为此至少连续使用了三年Linux的一个发行版Ubuntu作为平时工作生活的主要桌面系统。近三四年又以苹果的macOS X为主要的工作系统,因此对三大桌面系统Windows, macOS, Linux都算是比较熟悉了。甚至连PC-BSD, Solaris等非主流系统都安装试运行过几次。有了在不同的操作系统下的使用经验,对什么是操作系统的理解,比以前只会使用Windows时有了更深的认识。最近anian又告知有一款相当不错的Linux下KDE桌面的推箱子Sokoban SG,尚没有时间和精力测试。 学习并使用了多种编程语言。使用得比较多的语言是C、JavaScript、PHP。比较满意且花的功夫比较多的是用C编写的USokoban,用JavaScript编写的HTML5浏览器平台下的SokoPlayer HTML5,以及用服务器端编程语言PHP编写的比赛网站sokoban.cn以及关卡分享平台sokoban.org等。其它还尝试过写Firefox浏览器插件,用Python也写了一个简单的推箱子等等。后来因跑步和小孩出生,没有太多业余时间写程序了,但有些程序至今还时不时需要维护,如在第99期比赛时,还修正了比赛网站的一个bug:对副关的答案没有做“至少一推”的检验。 学习使用LAMP技术建设网站。LAMP是比较成熟的开源建站技术,租用服务器建站成本和技术难度都不算高。但是工信部对个人建立网站的管理时紧时松,为了比赛顺利进行,我还是在2011年初按工信部规定为比赛网站备了案。一开始只注册了sokoban.ws这个差强人意的域名,后来又注册到sokoban.cn和sokoban.org两个域名真是喜出望外。对整个互联网是如何运转的也有了些更深的认识。 琢磨了一些推箱子相关的算法。写USokoban时,实现了一个简单的解关器,掌握了解关器的一些基本算法。后来为了优化SokoPlayer HTML5推一个箱子的提示和寻径,想到了运用图论中找割点的算法,大大提高了计算的速度。 研究了推箱子及其变种的计算复杂度。计算了一系列具有指数长度答案的关卡所需要的精确步数。搞明白了推箱子问题的计算复杂度为什么是PSPACE完全的,还证明了推箱子的一个新变种也是PSPACE完全的,发表在学术期刊Theoretical Computer Science上面。 此外,关于推箱子的编关和解关,我几乎没有太多研究,还有许多宝藏有待今后挖掘。可见,推箱子是可以作为一生的爱好,不断地给人带来欢乐。  

发表在 推箱子, 数学, 算法, 编程, 计算机 | 留下评论

《堆雪人推箱子》是PSPACE完全的

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=3444 去年2月份,我写了一篇博文介绍了推箱子游戏(Sokoban)的计算复杂度是PSPACE完全的。同年4月份,我又写了一篇博文介绍了一个推箱子变种游戏《堆雪人推箱子(A good snowman is hard to build)》。 写了这两篇博文后,我产生了一个想法,证明堆雪人推箱子(简称Snowman)的计算复杂度也是PSPACE完全的。经过一番努力,我把这个想法写成了一篇论文,投到由荷兰的学术出版集团Elsevier发行的期刊《Theoretical Computer Science》。该论文有三名共同作者,我是通讯作者(corresponding author)。今年(2017年)3月,被正式接收了,并于3月18日在网上发表了。 该论文永久有效的DOI地址:http://dx.doi.org/10.1016/j.tcs.2017.03.011 根据和出版社之间的通常的版权协议,我有权在个人博客分享被接收的手稿(accepted manuscript),但经过重新排版的正式发表的期刊论文(published journal article)的版权归Elsevier出版集团。本篇博文的目的就是提供该论文手稿的下载。 手稿下载:snowman_is_pspace_complete.pdf 就在论文被接受前后,我在位于上海复旦大学校内的上海数学中心举办的一次小型的图论青年学者研讨会(Graph Young Theorists Workshop)上,对这个问题作了一个20分钟报告。My presentation slides for this workshop can be also downloaded from here. 文章被接收的时间恰逢MF8推箱子比赛马上第八周年了,而且只差几期就是第100期的比赛了。又关注推箱子已近二十年了,能发表一篇与推箱子相关的学术论文,我十分高兴。 我早在1999年上大学时通过互联网搜索,看到加拿大阿尔伯特大学的Joseph C. Culberson证明推箱子是PSPACE完全问题的文章。但是那时文章中出现的PSPACE和Turing Machine(图灵机)等术语对我如同天书。 … 继续阅读

发表在 推箱子, 数学, 游戏, 计算机 | 留下评论

LaTeX 排版软件系统

  本文地址:http://sokoban.ws/blog/?p=2927 TeX/LaTeX排版系统是由美国计算机学家Donald Knuth于1978年开发的,这套系统的一个长处在于复杂数学公式的输入,主要用于包括数学、计算机科学、物理等学科的学术论文的书籍的排版。我最早于2003年准备本科毕业论文时开始使用,也断断续续用了有13年了。最近才对这个系统有了更多一些的认识。一个重要的原因是 LaTeX 排版软件系统主要构成都基本属于自由软件,其发行方式更像 Linux 系统。而我大概从Win98时代才开始熟悉计算机使用,对自由软件的那一套方式比较陌生。过去几年进行了一些和推箱子游戏相关的编程,也用过一段时间Ubuntu系统,有助于我重新认识TeX/LaTeX软件系统。 首先要明确几个概念。第一个就是系统的核心:排版引擎。排版系统的引擎就好比编程语言的编译器,有许多不同的实现。包括最早的Knuth的原版TeX,早期TeX/LaTeX引擎一般把源文件(.tex文件)编译为.dvi文章,然后再转换为.ps和.pdf文件。现在感觉更多人使用的是pdfLaTeX引擎,直接把.tex文件编译为.pdf文件。 由于LaTeX系统由包括排版引擎和其他大大小小的扩展宏包等等众多软件包联合组成,所以要得到一个可以直接使用的单一软件,通常是安装某个发行版。最核心的发行版是TeX Live,其他发行版大多在TeX Live基础上再进一步打包。比如我最早使用的就是中国人维护的发行版CTeX,这一发行版对中文的支持较好。最近我又使用了另一个面向Windows系统的发行版MiKTeX,和面向Mac系统的发行版MacTeX。 第三个重要的概念就是专门面向.tex源文件的文本编辑器。一般的发行版都包含有一个tex文本编辑器。此类编辑器一般带有编译按钮,能直接调用排版引擎对源文件进行编译,并打开编译后的dvi或pdf文件。有点类似于编程语言的集成开发编译环境。CTeX发行版集成的是共享软件WinEdt,MiKTeX的默认编辑器是TeXworks,MacTeX则是TeXShop。 当然,要真正使用这套排版系统,还需要略微学习一下LeTeX的一些常用命令。就如学习编程语言一样。 由于TeX系统从一开始就设计得扩展性很强,很多学术出版商都提供不同风格的期刊论文扩展宏包。比如Elsevier出版集团就提供了基于LeTeX之上的elsarticle.cls宏包,供投稿作者使用。并且,Elsevier还要求投稿文章使用BibTeX宏包的方式来处理参考文献。BibTeX的方式是把参考文献用特定格式保存在.bib文件中,供主源文件.tex引用。我之前一直只知道用\begin{thebibliography}命令方式,把参考文献直接写在.tex源文件里面。 用BibTeX的好处就是方便于和其他文献管理软件交换数据。常见的文献管理软件有Mac系统的BibDesk、被Elsevier收购的Mendeley、还有Nature杂志推荐的ReadCube等等。 TeX系统除了善于处理数学公式,也非常善于画图。以前我一直使用PSTricks宏包,但这种方式必须先编译为ps文件,和pdfLaTeX引擎不兼容。所以,最近我又学习了一下和pdfLaTeX兼容的TikZ/PGF宏包,其功能和PSTricks一样强大。于是,2016年8月17日,我编写的《HTML5图论小工具》新增输出TikZ代码功能。  

发表在 其他, 数学, 计算机 | 留下评论

围棋、推箱子和计算复杂度

  本文地址:http://sokoban.ws/blog/?p=2330 作者:杨超 这个月,2016年3月,Google 的 DeepMind 团队开发的围棋程序 AlphaGo 在韩国首都以 4:1 战胜世界冠军围棋九段李世石。早在近20年前,IBM 的国际象棋程序“深蓝”就已经战胜人类冠军。而围棋棋盘比较大,人们普遍认为人类对计算机程序的优势在围棋项目还可以保持比较长的时间。而这次 Google 团队的胜利,证明了其实开发一个战胜人类的下围棋程序并没有那么难,而是开发这样的程序没有太大的直接收益,哪怕是国际象棋和围棋这样就有悠久历史传统和广泛的群众基础和关注度的棋类。 围棋究竟有多难?我们拿它和推箱子来比较一下。恰好我刚刚完成了用三篇博文来介绍推箱子问题的计算复杂度:推箱子是PSPACE完全问题。 为了从计算复杂度方面和推箱子问题比较,我们需要准确地定义一下什么叫围棋问题。 虽然人们常说围棋的变化很多,但是无论变化有多少,终究是一个有限的数。所有有限步内能分出胜负的、没有隐藏信息、也没有运气成分的二人棋类游戏,一定有一方有必胜策略(或者必和策略)。打个比分说,19路围棋按照中国的贴目规则也许是先手有必胜策略。那么我们所说的围棋问题,就是对于任意的n x n棋盘上下的围棋,如何设计一个算法来确定究竟是先手必胜还是后手必胜?或者等价地说,先手究竟有没有必胜策略?(即这是一个回答“是”或者“否”的问题)通常的19路棋盘围棋是围棋问题的一个实例。要回答这个问题,除了穷举所有的对弈变化之外,人们暂时还没能找到其它规律来判断谁有必胜策略。对围棋而言,穷举所需要的时间随着棋盘 n 的增大,是成指数增长的。事实上,已经有文献证明,按日本规则,围棋问题是EXPTIME完全问题(见[1,2],该文章作者猜测,若按中国规则,围棋问题可能更难,成为指数空间完全问题)。也就是说,在指数时间可解的问题里面,围棋问题是最困难的其中一个。除了围棋,其它一些棋类问题如国际象棋、西洋跳棋(checkers)都被证明是EXPTIME完全问题。其中8×8棋盘的西洋跳棋在使用计算机花了近20年的穷举计算后,在2007年被证明双方都采取完美策略一定是和棋。 所以,从计算复杂度来看,包括围棋在内的许多棋类游戏比推箱子要难一个层次。计算复杂度的几个概念(EXPTIME、PSPACE、NP、P)的关系可用下图表示。虽然还没有从理论上严格证明,但是一般认为,从内到外,这四类问题的计算复杂度是严格地越来越难。 更有甚者,围棋问题的一些子问题,如征子能否成功问题在文献中被证明是PSPACE完全问题[3]。而围棋残局收官问题,则是PSPACE难的[4]。也就是说围棋问题的某些子问题就已经和推箱子问题一样难了。 那么,为什么比推箱子更难的围棋都已经开发出能战胜人类的程序,但是比围棋还容易一些的推箱子,我们却没有看到优秀的推箱子求解程序能够解出较大的、箱子数目较多的关卡呢?我想主要有以下这么一些因素。 首先,开发推箱子求解程序比开发下围棋程序更加无利可图。目前看到的一些求解程序基本都是个人单打独斗编写的,运行在个人电脑上,而且都是作为业余兴趣进行的。尚未看到有软件类企业或者研究团队投入较大资源来开发。作为对比,Google的AlphaGo程序投入了至少20人的开发团队,和李世石对战时动用了上千个CPU和GPU同时计算。 其次,AlphaGo虽然战胜了人类,但是并没有回答我们前面所定义的围棋问题,也就是说并不知道是否先手必胜。战胜人类并不需要穷遍所有变化,比判断19路围棋谁有必胜策略稍微容易一些。而一个推箱子关卡求解程序从某种意义上必须回答出推箱子问题,一般来说,必须穷遍所有路经才能判断一个关卡无解。而找到一个答案,除了穷举剪枝之外也还没有见到有人提出新的算法思路。 比较令人好奇的是,如果投入更多的人力和计算机运算资源,计算机求解推箱子能达到一个什么样的水平呢?能解出多大的关卡?解大关卡能比人解得更快吗? 第83期推箱子比赛,我们也借着这个机会,由麦英兄设计了一关AlphaGo关卡。这一关计算机能解出来吗? [参考文献] 1.  J. M. Robson, The complexity of Go, Proc. IFIP (1983) … 继续阅读

发表在 推箱子, 数学, 计算机 | 留下评论

推箱子是PSPACE完全问题

  本文地址:http://sokoban.ws/blog/?p=2254 作者:杨超 本文是两篇博文《 一系列具有递归关系和指数长度答案的推箱子关卡》 和《 判断推箱子关卡是否有解的多项式空间的算法》 的续篇。这三篇博文构成推箱子与PSPACE问题三部曲。 一、什么是PSPACE完全问题(PSPACE-complete problems) 前两篇文章已经提过,PSPACE问题指的是:相对于实例(instance)的大小,存在多项式空间算法的判断性问题(decision problem)。 而PSPACE完全问题是PSPACE问题中最困难的一类。即一个问题A能够被称为PSPACE完全问题,如果问题A满足:对任何其他的PSPACE问题B,都存在一个多项式时间的方法把B的实例转化成A的实例,使得这两个实例在这两个问题中有相同的答案(都是“是”或者都是“否”)。由此定义,只要能给出某个PSPACE完全问题的快速算法,那么这个算法就可以用来解决所有的PSPACE问题。 我们这里所说的推箱子问题(SOKOBAN),指的是给出一个推箱子关卡(即实例),如何判断这个关卡是否有解。 无论从实践到理论,都有证据表明推箱子是非常困难的。 实践中,我们举办了好几年的MF8推箱子网络比赛,尚未见到有人或者组织能够用计算机快速解出我们的比赛主关。 在计算复杂性理论中,推箱子问题也被证明是一个PSPACE完全问题。本文的目的就是简单介绍一下这些证明。要证明推箱子问题(或者其他问题)是PSPACE完全问题,要论证两个方面: 一是推箱子首先是PSPACE问题。因为存在很多问题,其难度甚至超出PSPACE的范围,我们需要说明推箱子没有超出这个范围。这一点的证明较为容易,已经在三部曲的第二篇文中说过了。 二是证明推箱子是PSPACE问题里面最难的。这又有两种常用的方法,第一种方法是按照定义,描述一种方案把任何一个PSPACE问题的实例转化为推箱子实例。第二种方法就是,描述一种方案,把某一个已经被证明的PSPACE完全问题的每个实例转化成推箱子的实例。 无论是用那种方法证明,其技术性都是比较高的,比较依赖于巧妙的构思。 二、PSPACE完全问题的例子 已经有许许多多的问题被证明是PSPACE完全问题。这些问题可以被用来证明其他问题也是PSPACE完全问题。这里介绍两个比较有代表性的。 第一个是TQBF问题(True Quantified Boolean Formula)。这个问题的一个实例就是一个每个变量都带有量词(存在、任意)的布尔逻辑公式。公式中的每个变量只能取值“真”或者“假”。 如:(任意x)(存在y)(存在z) ((x或者y)并且z) 我们需要判断这样的一个公式是否总是“真”的。 第二个是LBA问题,即线性空间自动机(Linear Bounded Automata)。这个问题的一个实例是:给出一个线性空间自动机和一个输入,该自动机是否接受该输入。 这个问题的PSPACE完全性证明非常简单。因此利用此问题证明推箱子问题是PSPACE完全问题,和直接用定义证明推箱子问题是PSPACE完全问题,几乎没有多大区别。 除此之外,推箱子和滑块类游戏也是PSPACE完全问题的有趣例子。 三、推箱子是PSPACE完全问题 Dorit Dor和Uri Zwick在1996年写文章[1]研究了推箱子问题的计算复杂度,但未能证明推箱子是PSPACE完全的。加拿大阿尔伯特大学的Joseph C. Culberson看到该文后,在1997年就证明了推箱子是PSPACE完全问题[2]。 … 继续阅读

发表在 推箱子, 数学 | 一条评论

用深度优先搜索(DFS)确定图的割点

本文地址:http://sokoban.ws/blog/?p=1000 之前的博文《推箱子游戏的一个箱子推动路径搜索算法 (二)》介绍了图论中寻找割点的算法在推箱子路径搜索中的应用。但是对用DFS寻找割点的原理说得不够清楚明白,本文的目的是试图进一步阐明这个算法,并把示意图画的更漂亮一些。 用DFS遍历一个图的所有顶点时,按访问顺序依次标号为1到n,称之为DFS数。顶点v的DFS数记作D(v)。并得到一棵DFS树(黑色边),称DFS树的边为树边(tree edge),其余的边(红色边)称为回头边(back edge)。如下图,图的边都按搜索过程中向外的方向定向,得到一个有向图。树边都是从DFS数小的顶点指向大的,回头边都是从DFS数大的顶点指向小的。   根据上面由深度优先搜索得到的有向图中,可定义每个顶点的低位数(lowpoint):从该顶点出发,只用最多一条回头边,沿有向边能走到的顶点中DFS数最小值。顶点v的低位数记为L(v)。 低位数取值有两种情况:一是没用上回头边,则能走到的DFS数最小的的顶点就是该点自身,对应的路是一个顶点构成的平凡的路。此时L(v)=D(v)。二是用了回头边,则一定是最后一条边是回头边,走到一个DFS数更小的顶点。此时L(v)<=D(v)。 所以,一般地,总有L(v)<=D(v)。 有了这两个参数,就可以确定割点了:对根节点,即DFS数为1的顶点,其为割点当且仅当在DFS树中有两个或以上子节点;其余所有非根节点v是割点的充分必要条件是:v存在一个子节点u(在DFS树中的子节点)满足u的低位数大于等于v的DFS数,即L(u)>=D(v)。 下图标出的顶点的低位数(圈外数字,没标圈外数字的顶点低位数和DFS数相等),绿色顶点为割点。 注:若用 DFS的深度(depth)来替代上面算法中的DFS数,并用深度来计算低位数,则算法一样能有效地找出割点。 [参考文献] 1. Shimon Even, Graph Algorithms (2nd Edition). Cambridge University Press. 2012. p52-54 [文中的图使用http://draw.io制作]

发表在 数学, 算法 | 留下评论

判断推箱子关卡是否有解的多项式空间的算法

作者:杨超 本文地址: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 $高估了所有可能的局面数,但从数量级上是基本一致的),其中有一个局面是初始局面,有一个是目标局面。所以,如果一个关卡是可解的,一定在$ … 继续阅读

发表在 推箱子, 数学 | 留下评论

图上的熄灯游戏

作者:杨超 本文地址:http://sokoban.ws/blog/?p=487 一、熄灯游戏 熄灯通常在n*n的格子上玩,每个格子是一盏灯,点击每个格子可以改变格子本身及其上下左右相邻格子的灯的状态。游戏要求把灯从全亮变到全部熄灭。关于熄灯游戏,老杰有一篇博文《熄灯游戏》对此作了非常好的介绍,他的网站还有网页版的熄灯游戏可以在线玩。对熄灯游戏不太熟悉的朋友可以在看老杰的博文之后再继续往下看。 二、推广 老杰的博文提到,对任意的n,初始状态为全亮的熄灯游戏都有解,即可以被全部熄灭。老杰的博文最后还提到熄灯游戏有六边形,3D等形式的推广。 更一般地,熄灯游戏可以推广到任意的图上面。这里所讲的图是若干个顶点和某些顶点对之间的连边构成。如下就是所谓的 Petersen 图,它由10个顶点和15条边构成。熄灯游戏的规则可以不作任何改变应用到一般图上,点击一个顶点,改变该顶点以及和该顶点直接相邻的顶点的状态。 图片来自 Wikipedia, CC-BY-SA协议 并且有趣的是,任意的一个图上以全亮为初始状态的熄灯游戏都有解。这个结论可以用线性代数和线性方程组的求解理论作出证明。但是这个证明需要系统地学习过线性代数才能比较好地理解,一般大学理工科的学生才会学习线性代数课程。下一节,我准备介绍一个纯粹的图论证明,这个证明由 Henrik Eriksson 等人2001年发表在《Advances of Applied Mathematics》杂志上,全文可以在 arXiv 下载。这个证明只用到了数学归纳法,有一定数学修养的高中生都完全有可能自己独立证明出来。这个证明简洁漂亮,很有可能被许多人独立地发现过。 三、证明 本节用数学归纳法证明:任意一个图上以全亮为初始状态的熄灯游戏有解。 对图的顶点个数 n 归纳。n=1 的时候显然有解。 下面进行归纳,假设对n-1个的点的图结论都成立,我们证明n个顶点的图G结论也成立。设这n个顶点的标号为1,2,…,n。为了用归纳假设,我们可以作这样的考虑,把标号为i的顶点删掉(当然这时和顶点i关联的那些边也同时删掉了),那么剩下的还是一个图,但只有n-1个顶点了。根据归纳假设,剩下的这个图是有解的,取定一个解称之为关于i的解,因为图是删掉顶点i得到的。 如果对某个i,关于i的解也是原来n个顶点的图G的解,那么结论对原图G也成立了。所以下面我们只需要考虑这样一种情况:对所有的顶点i,关于i的解都不是原图G的解。具体地说,每个关于i的解作用在原图G上的效果就是顶点i还亮着,其余的顶点都灭了。在这样一种情况下,我们下面分甲乙两种小情况考虑。 甲、n是偶数。此时我们可以把关于1的解,关于2的解,…直到关于n的解依次都在原图G上执行一次。我们分析一下执行的最终效果。对顶点i来说,关于i的解使得顶点i的状态保持不变,而其余n-1个解使顶点i改变状态。因为n是偶数,n-1是奇数,合成的效果就是顶点i的状态改变了奇数次,由亮变为灭了。每个顶点都是这样,所以这n个迭加在一起就是原图G的解了。 乙、n是奇数。这时刚才的方法不管用了,要另辟蹊径。我们取图G中一个度数为偶数的顶点,不妨设为顶点1。本段余下解释为何存在这样一个顶点,熟悉图论的朋友可以跳过直接看下一段。所谓顶点的度数,就是和这个顶点相邻的其它顶点的个数,也就是和这个顶点关联的边的条数,如前面的 Petersen 图每个顶点的度数都是3。一个图的所有顶点的度数加起来一定是偶数,这时因为在计算度数的时候,图的每一条边都会被两个不同的顶点计算了一次,共被计算了两次,于是所有顶点的度数和是边数的两倍,为偶数。还是以刚才的 Petersen 图为例,度数和为30,是边数15的两倍。因为我们的图G的顶点个数n是奇数,若所有顶点度数都是奇数,那么所有顶点的度数和是奇数个奇数相加,还是奇数,这不可能。 把上面取定的顶点1和它的全部邻点构成的集合称为A,那么A一共有奇数个顶点。其余的顶点全体是集合B,且B有偶数个顶点。对原图G,我们执行以下操作,点击一下顶点1,那么A中的点全灭了,B中的点任然保持亮着。之后再对B里面的每个顶点j,执行关于j的解。这里一共有偶数个解,所以A中的点改变状态偶数次,还是灭的状态;B中的点改变奇数次,也由亮变成灭了。于是我们得到原图G的解了。 四、小结 上述证明没有用什么高深的数学,非常简单。但是若是要找出一个具体的解法,还是用线性代数的方法或者结合其它技巧要快一些。老杰的博文提到有人给出 5000*5000 的熄灯问题的解。这相当于一个 … 继续阅读

发表在 数学, 游戏 | 留下评论

一系列具有递归关系和指数长度答案的推箱子关卡

作者:杨超 本文地址:http://sokoban.ws/blog/?p=430 一 推箱子的其中一个很重要的魅力来源于推箱子求解问题在计算复杂性理论里是一个 PSPACE 完全问题。在这里不对什么是 PSPACE 完全问题作出解释,但是推箱子的一部分美妙之处可以认为正是来源于它的计算复杂度达到了 PSPACE 完全问题的级别。具体表现就是可以设计出很多不同模式的关卡,而且我们目前所涉及到的模式只是一小部分,还有很广阔的空间等待我们去探索。另外一个表现就是存在一系列具有指数长度答案(相对与关卡的大小)的关卡,这一类关卡就是推箱子关卡众多模式里面非常有趣的一类,也是本文要讨论的对象。 二 2009年6月8日,我曾在魔方吧论坛发贴子介绍了一类指数长度答案的关卡。无独有偶,约一个月后的2009年7月5日,Matrix67的一片博客文章也介绍了这一关卡。我的贴子和 Matrix67 的博文介绍的关卡都是基于2000年国外的一个关于推箱子问题的解答。 对这个关卡的具体分析这里就不再重复了,简单的说它就是由一个个的“房间”构成,上图是三个房间的情况。要过关,最左侧一个房间要进入2次,但要进入左一房间1次,就要进入左二房间2次,所以左二房间一共要进入4次。同理,左三房间就要进入8次。一般的,若有n个房间的话,第n个要进入2^n次,于是答案长度便成指数增长了。 这个关卡设计巧妙,让人感受到推箱子的美。下面我们要介绍一个更美的更简洁紧凑,但同样也是具有指数长度的答案的系列关卡。 三 这个更漂亮的系列关卡也是在推箱子玩家里面流传了很长时间了,有很多变化形式,其中最经典的可能是如下图所示。 这是 Aymeric du Peloux 2001年设计的 Picokosmos 第17关。David Holland 在2002年曾分析过这个关卡。Dries De Clercq 在这个基础上作了名为 Fibo 系列的变形关卡。上图所示的经典形式不只是一个关卡,而是一系列关卡,关卡可以纵向任意伸长(同时箱子也增加),只要保持箱子总数是偶数个就行了(奇数的时候关卡无解)。若用n表示箱子的数目,随着n增大,答案步数以n的指数函数增长。 没有玩过这一关的朋友可以点击此链接在线玩。先提前警告,虽然只有8个箱子,要解出来不太容易。 我是2009年在魔方吧发了前面提到的贴子之后,才注意到这个关卡,当时没有看到 David Holland 的分析文章,独立地研究了这一系列关卡的步数。下一节将简要的介绍一下我的计算方法。 四 上一节提到,这一系列关卡只对偶数个箱子有解。为了便于建立递推关系,我对箱子位置作了以下微妙调整,使得对奇数也有效。主要有两处改动:一是最下方一个箱子连同目标移动了一格;二是最上方一侧的箱子移下一格(哪一侧由奇偶性确定)。如下面所示,分别是4到8个箱子的情形(注意本节的图和上一节的图左右反了)。 本关在线游戏链接 … 继续阅读

发表在 推箱子, 数学 | 留下评论