分类目录归档:数学

天问一号第一次中途修正

  本文地址:http://sokoban.ws/blog/?p=4710 作者:杨超 上一篇博文讨论了我国天问一号火星探测器从发射到箭器分离的轨迹。 分离后,天问一号就基本只在太阳(和地球等)的引力作用下飞行。有不少业余和半职业的天文爱好者和无线电爱好者都从太空中捕捉到了天问一号,由此还计算出天问一号的轨道根数。不过由于火星探测器比起近地小行星小多了,随着天问一号离地球越来越远,业余人员很难再观测到。 人造航天飞行器被业余天文爱好者观察到是常见的事情。我国的嫦娥二号完成原定任务后,从日地拉格朗日点L2再次变轨,执行在距离地球约700万公里外飞掠小行星的任务时,也曾被不明真相的业余爱好者观测到。 据报道,8月2日7点0分,北京航天飞行控制中心对天问一号执行了第一次轨道中途修正(trajectory correction manoeuvre,简称TCM)。由于长征五号非常精准地把探测器送入了预定轨道,这次修正的主要一个目的考察发动机的在轨工作情况。 天问一号继续着火星之路的漫漫征程。   这次,我国使用重型运载火箭(重型一般指具有把20吨以上送到LEO的能力的火箭)长征五号第一次执行正式任务(之前的长五发射均带有试验性质),把重达五吨的探测器直接送入地火转移轨道,为人类有史以来发向火星的所有探测器中最重的一个。而同期发往火星的阿联酋和美国的探测器因为相对较轻,所以均使用了中型运载火箭。阿联酋用的是日本的H-IIA火箭,美国则是宇宙神五号(Atlas V)火箭。                                                       … 继续阅读

发表在 数学, 火星 | 留下评论

天问一号的飞行轨道

    本文地址:http://sokoban.ws/blog/?p=4647 作者:杨超   2020年7月23日,我国的长征五号火箭用了36分钟把天问一号火星探测器送入地火转移轨道,开启了6个多月的征程,将于明年2月抵达火星。这同时也是我国继探月工程之后,正式开启了行星探测计划。 此前的几天的7月20日,阿联酋的HOPE火星探测器在日本种子岛由日本的H-IIA火箭发射升空。在这之后的7月30日,美国“毅力号”(Perseverance)火星探测器在佛罗里达州卡纳维拉角空军基地41号发射场由Atlas 5号火箭发射升空。 至此,2020年的这次火星探测发射窗口期的全部探测器均已经成功发射。而欧洲的ExoMars火星探测器的发射又一次推迟,只能等到下一个窗口期,即26个月之后的2022年。 这段时间,网上不少科普都解释了为何多国都扎堆在这个窗口期发射火星探测器,主要原因是所谓的霍曼转移轨道(Hohmann Transfer Orbit),比较节省飞达火星所需的燃料。由连续性,在这个时间点前后约一个月多月的时间内,都可以设计出合适的飞行轨道,和理论上最佳的霍曼转移轨道相差不远。 霍曼转移轨道的发射时机是火星与地球的夹角为40度左右。而地球公转的角速度是火星的1.88倍左右,每两年多(即26个月左右)套火星一圈。所以这个40度左右的夹角每26个月才出现一次。 值得指出的是,这个地火转移轨道是指探测器由火箭发射升空后与火箭分离,直至接近火星近火制动好让探测器被火星的引力捕获的这一段过程。这一个过程中,除了中间少数几次的轨道中途修正和深空机动之外,探测器基本上只受到大阳的引力作用(地球和火星的引力都可以忽略不计),其数学模型是相对比较简单的。 而如何用火箭精准地把探测器从地面送入这个地火转移轨道,则要更为困难。所以大家看到发射过程中,发射中心和测控中心的人员都比较紧张。顺利送入轨道后,大家都松了一口气,对这漫长的近七个月的旅途倒没有表示出太多的担心。下一个需要担心的时刻是近火制动。 第一个成功把火星探测器成功送到火星环绕轨道的亚洲国家是印度,于2013年发射,2014年抵达火星。印度人做了一个比较详细的轨道示意图(点击可看大图)。 由此图可以看出,印度的探测器是环绕地球轨道飞行了多圈后,经过多次加速调整,才最后加速离开地球,进入地火转移轨道。主要原因是印度当时的火箭推力不足,不足以把探测器直接推到能够脱离地球的第二宇宙速度。 更早前的1998年,日本也尝试发射火星探测器“のぞみ”号,但是接连发生各种故障,脱离地球轨道时没有正确入轨,经过多次轨道调整,最终也没能进入火星环绕轨道,以失败告终。   我国在2011年也曾尝试向火星发送“萤火一号”探测器,不过是搭乘俄罗斯的火箭,发射失败,最终连地球也未离开。 这次阿联酋也有发布他们的希望号(HOPE)的飞行轨道示意图。但是这个示意图并没有体现火箭发射阶段的飞行轨迹。 用H-IIA火箭把阿联酋的希望号送入轨道的三菱重工有如下的发射计划图,显示了发射轨迹在地球上的投影路径。最终实际发射实际为日本时间7月20日早上6点58分,探测器在约57分钟后和火箭彻底分离。由此可见火箭是绕了地球飞行了大半圈后,从地球背向太阳的一面进入双曲线逃逸轨道,并在后期进一步进入地火转移的大椭圆轨道。 美国毅力号是在美国东部时间早上7点多发射的,发射过程的飞行轨迹和日本相仿,也是绕了地球大半圈。而且从发射到和火箭分离也是总用时约1个小时。下图是毅力号发射公司ULA官网上公开的发射计划。 关于“天问一号”的发射飞行轨迹,我在网上各种官方半官方的网站或媒体上找不到类似于以上图片这么精准的轨迹图。不过根据各种视频文字报道,可以判断出飞行路径和日美两家类似。唯一的区别是于我们发射时间是中午12点多,相对而言,少绕了地球近1/4圈。 根据央视的直播,从监控画面看,器箭分离时,已经在西经126度南纬29度的上空近500公里,快要飞到南美阿根廷上空了,已经绕到地球背面了(背向太阳的一面)。此时检测速度为对地面10.907公里每秒,已经超过了这个高度下的第二宇宙速度,进入了地球逃逸轨道了。 与日美相比,我们这次火星探测器最重,总重达到5吨,但是送达逃逸轨道的时间最短,仅用了36分钟器箭分离。 成功发射后,深空测控也进展地进行。据报道,器箭分离后仅4分钟,我们深空测控网的阿根廷站就捕获了探测器。 天问一号探测器是沿着地球公转轨道切方向略向外,从地球背面飞离地球。因此,直到入夜,即我国国土逐渐因为地球的自转而转到地球背面去时,我们境内地两个深空站才陆续捕获天问一号。发射当天晚上9时37分,东部的佳木斯先捕获到,第二天凌晨1时许,西边的喀什站也捕获到了。 因此,虽然没有找到天问一号的发射轨迹图,我们从各种报道中也容易想象天问一号在太阳系中的飞行轨迹:中午12时许几乎是太阳直射的时候随着火箭起飞,自西向东飞过太平洋,并且略偏南。这是因为7月正是北半球夏天,地球自转轴倾向太阳,而探测器是几乎在黄道平面内飞行。绕到地球背面后,就沿着地球公转轨道的切线飞离地球了(参见下图蓝色线,俯视黄道平面的角度)。   据后续报道,北京时间7月28日凌晨5时左右,天问一号飞离到距离地球150万公里处,离开了地球引力范围。这意味着正式从地球逃逸轨道(双曲线)转接到地火转移轨道(椭圆)。此时天问一号与地日连线的夹角为105度左右(据ProjectPluto上的公布的观察计算数据),也和我们前面分析的飞行轨迹完全吻合。

发表在 数学, 火星 | 留下评论

二维码推箱子关卡 – 纠错码的别出心裁的应用

  本文地址:http://sokoban.ws/blog/?p=4392 为了庆祝比赛十周年,20603先生在122期为比赛设计的《十年树木》关卡。我在博文中借此谈了一下“十年树木,百年树人”的出处。 而在之前的121期,20603先生则为比赛设计了两个二维码关卡《推箱之家》和《推箱驿站》,并为此设计专门的皮肤。此两关若使用专门为二维码设计的皮肤,可以直接扫一扫打开比赛网站。 赛后,20603先生又放出了用于关卡设计的原始二维码,并指出了最后的关卡对原始的二维码作了改动。主关的原始二维码如下: 之所以可以改动二维码,其原因是二维码利用了一种可纠错编码 Reed-Solomon 码来进行编码。 仔细对比了一下主关的二维码,有6个位置黑白发生变化(其中有一个大概会被扫码器无视): 另外五处刚好改变了5个格子(黑变白,或白变黑)。 根据二维码的标准,21×21规格的二维码一共有26个字节(Byte 一个字节8位,即8个黑白格),如下图: 邹兄设计的主关所用二维码采取的是有19个字节是记录真正的数据(实际上此二维码的内容,即网址 http://sokoban.ws 一共17个字节,加上字符串长度等额外信息,刚好用完19个字节)。 另外7个字节是用于纠错,能够发现和纠正3个字节的错误。二维码用的是 Reed-Solomon 纠错码。 按照上图26个字节的分布,几个黑白改动的地方分别属于3个字节,刚好达到这个(26,19)纠错码的纠错能力极限,还是能够正确地扫码打开我们的比赛主页。 给定了二维码设计推箱子关卡,这是难度非常高的“命题作文”,为了达到必要的难度,邹兄不得不改动二维码。但是二维码是用 Reed-Solomon 纠错码编码的,能够容许少数改动(错误)而还能正确解码。这算得上纠错码理论在推箱子中得到应用的一个非常妙的例子吧。 此外,在邹先生的提议下,我们颁发了比赛十周年纪念奖。邹先生为此又额外设计或发布了几个二维码关卡,其中一个用于作为荣誉证书的“章”,另外两个印刷成不干胶贴纸,随证书发放给十周年奖的获奖者。      

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

《花之谜题》的计算复杂度

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=4244 “P是否等于NP?”是Clay数学研究所(Clay Mathematics Institute,缩写CMI)2000年评出的七个奖金100万美元公开数学问题中的一个。Clay数学研究所的官网对每个问题都有正式的描述,其中对“P=NP?”问题的描述中,以扫雷游戏作为NP完全问题的代表,作了一些深入浅出的介绍,见下面官网截图。可见,一些益智小游戏和被数学家认为最重要的数学问题也有密切联系。 由于长期对推箱子游戏的喜爱,从而对推箱子类游戏的计算复杂度也很感兴趣。一般有点意思的推箱子类游戏对应的判定问题的计算复杂度,大多是NP完全或PSPACE完全的。对于具体一个推箱子类游戏,要完全确定其计算复杂度,有时也不见得容易。其中涉及的一个特别的因素是游戏的答案长度:是否总有多项式长度的答案?还是存在例子使得答案长度达到指数级别? 《花之谜题》(Hanano Puzzle)是一个令人爱不释手的游戏,我之前有两篇博文都分别介绍过。这个游戏特别之处在于一方面具有引力,另一方面可以通过开花抵抗引力向上推。 最近,我和合作者在 Elsevier 出版集团旗下的学术期刊 Information Processing Letters 上发表了一篇文章,研究了这个游戏的计算复杂度。有兴趣的朋友可以在此下载该文章的被接收的手稿: Hanano Puzzle is NP-hard 正式发表的版本可以在 Elsevier 官网下载: https://authors.elsevier.com/a/1YRTa4ZKAYBpN(此链接于2019年3月13日前都可以免费下载)正式版本的排版更为赏心悦目一些,学术出版集团 Elsevier 还是在学术出版过程中创造了不少价值。

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

2018年广东省组合图论会议

  本文地址:http://sokoban.ws/blog/?p=4153 2018年7月6日-8日,2018年广东省组合图论会议在珠海市中山大学珠海校区伍舜德国际学术交流中心举行。 7月6日,会议报到。 7月7日,在伍舜德学术中心2楼6号会议室进行第一天的报告。 西弗吉尼亚大学赖虹建教授作了题为“Some progresses of studies of group connectivity and modulo orientations of graphs”的一小时报告。 华南师范大学周波教授作了题为“Some aspects of spectral graph theory”的报告。 华南师范大学尤利华教授作了题为“Sharp upper and lower bounds for the spectral radius of a nonnegative weakly irreducible tensor and its … 继续阅读

发表在 数学 | 留下评论

读书笔记(十八)Four Colors Suffice

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=4045 我给大一的学生在《离散数学》课程上讲述图的染色理论以及五色定理的证明很多年了,但是对四色猜想得到证明的历史过程没有深入了解过。最近读了Robin Wilson著的《Four Colors Suffice》一书,是2002年出版的较新的讲述这一历史过程的科普性作品,读来十分有趣,利用4天的闲暇时间一口气读完了。 此书既讲述历史,也讲述证明,基本把整个证明的原理讲得非常清楚明白了。而且把我知道的许多图论及相关数学知识在证明四色猜想这个故事背景中串联起来,读来津津有味;也有许多内容是第一次读到,给人带来启发。 下面列举一些我从该书获得的印象比较深刻的知识点: Tempe的错误证明细节,11年后才被发现; Tait的错误猜想(任何三连通三正则平面图有Hamilton圈)如何同四色猜想建立联系; 布鲁克黑文实验室的日本人Yoshio Shimamoto 一度差点以为也得到一个只需一个reducible 构形的简单证明; 四色猜想除了向k的亏格的曲面推广外,还有一个每个国家可以有最多n个不连通区域的推广,都完全解决了; Haken在 unknotting  problem上也作过重要贡献;图的染色多项式有些奇怪特点(不久前去年才在Quanta上看到韩国人June Huh也在chromatic polynomial上作了重要工作);C-reducible和D-reducible的定义搞清楚了; 了解了American J. of Math.这一期刊,以前看fifteen puzzle的历史也看过该期刊的文章; 原则上四色猜想也可以转化成一个方程组问题,虽然可能这组方程并不好解; 首创 discharging 方法的Heesch在平面tiling问题上也有贡献; 当时四色猜想的研究还是很热门的,是不少博士论文的研究题目,有好几组研究者都试图用计算机方法证明;Haken和Appel主要是在先找一组 unavoidable 构形的策略上取胜。 总之,非常好的一本数学通俗读物,当然书里面的很多数学证明也不见得容易读懂。  

发表在 数学, 读书 | 留下评论

关卡无限大的推箱子

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=3853 通常我们玩的推箱子关卡都是有限大小的,一般不超过50×50。因为最近读了不少关于不可判定(undecidable)问题的文章,很自然就问这样一个问题:我们已经知道有限大小的推箱子问题是可判定的,且知道其计算复杂度为PSPACE-complete;若考虑无限大小的推箱子关卡,即关卡占据整个平面,允许有可数无限个(countable)箱子和目标点,那么问题是不是也变成了不可判定的? 比较著名的不可判定问题有: 图灵机的停机问题; 希尔伯特的Entscheidungsproblem问题,即一阶谓词逻辑系统的判定问题; 王浩瓷砖(Wang Tile)问题; 希尔伯特第十问题,即判定丢番图问题是否有解; 计算Busy Beaver数; 元胞自动机(Cellular Automata)的可逆性; ……等等。 现在,我们可以给这个列表又添加一个新问题:无限大小的推箱子问题。这个结论,早在1997年,Culberson证明推箱子是PSPACE完全问题时,就顺带指出了。因为Culberson的证明就是用推箱子关卡来模拟图灵机,从而把LBA问题(线性空间的图灵机)归约为推箱子问题。在往前走一步,自然任何一个潜在无限长纸带的图灵机也可以用占满整个平面的无限大小的推箱子关卡来模拟,从而把停机问题归约为推箱子问题。 这就证明了关卡无限大的推箱子是不可判定的。Culberson甚至指出,若限制只有有限个箱子没有归位(其余可数个箱子一开始都处于目标点),问题仍然是不可判定的,或者说是不可计算的。 这从另外一个方面也体现了推箱子有多难。      

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

王浩瓷砖(Wang Tile)

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=3795 王浩(Hao Wang)是著名的美籍华人数学家、逻辑学家、哲学家。他1921年生于山东济南,1943年毕业于西南联合大学,1948年在美国哈佛大学获得哲学博士学位,1995年在美国纽约逝世。王浩是哥德尔(Kurt Gödel)的好朋友。创立了NP完全理论、证明了SAT是第一个NP完全问题的著名计算机学家Stephen Cook,则是王浩的学生。 王浩(1921-1995) 为了研究一阶谓词逻辑的可判定性问题(即希尔伯特的Entscheidungsproblem问题),1961年,王浩提出了瓷砖问题,后来被他的学生Robert Berger称为王浩瓷砖(Wang Tile)问题。任意给定一组有限个正方形的瓷砖,每个瓷砖的每条边都用一种颜色标记。用这组瓷砖去铺整个平面,每种瓷砖都有无限的供给。要求铺设时,任意两块瓷砖相邻的边的颜色要相同。并且,只允许瓷砖平移,不能够旋转或者镜面反射。王浩问:能否用这组瓷砖平铺整个无限的平面? 如下图是一组13个正方形的王浩瓷砖。 如下图那样平铺。 自王浩在1961年提出瓷砖问题,直到今天还引出许多研究。可以说这是一个非常有趣而深刻的问题。 一开始,王浩猜测,任意给定一组瓷砖,要么可以铺满整个平面,并且一定有一种周期的平铺方案;要么不能平铺整个平面。如果这个猜测是对的,那就意味着存在一个确定性的算法去判别每一组王浩瓷砖是否可以铺满整个平面。 王浩还发现了王浩瓷砖可以用来模拟图灵机。由此,王浩证明了,若对王浩瓷砖问题作出一些限制,如原点必须铺某一块瓷砖,或是坐标轴上的瓷砖预先铺设好等等,则王浩瓷砖问题是不可判定的(undecidable)。即不存在确定的算法去回答平铺是否能够实现。 从可计算性和计算复杂度看来,王浩瓷砖问题远远难于PSPACE完全的推箱子问题(Sokoban)。因为王浩瓷砖问题是不可计算的。而推箱子问题是可计算的,而且在可计算的问题里面,推箱子问题也远还不是最难的。 不久,1964年,王浩的学生Robert Berger在其博士论文The Undecidability of the Domino Problem中证明了即使没有对原点或是坐标轴的限制,王浩瓷砖问题(无限制的王浩瓷砖问题又被称为domino problem)也还是不可判定的。Robert Berger的博士论文还发表在1965年的Memoirs of the American Mathematical Society。 为了证明domino problem是不可判定的,Robert Berger也构造出第一组只有非周期铺满方案(aperiodic tiling)平面的王浩瓷砖。但是,这组瓷砖由惊人的20426个瓷砖组成。这也否定了王浩认为总是存在周期性的铺满方案的猜测。 也就是说,不可判定的证明主要基于两个核心事实:一是只能非周期铺满平面的王浩瓷砖组(an aperiodic set of Wang … 继续阅读

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

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

  作者:杨超 本文地址: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上面。 此外,关于推箱子的编关和解关,我几乎没有太多研究,还有许多宝藏有待今后挖掘。可见,推箱子是可以作为一生的爱好,不断地给人带来欢乐。  

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