-
最近文章
近期评论
- [坑]POI补完计划#1 | qiancl 在 推箱子游戏的一个箱子推动路径搜索算法 (二) 上的评论
- [坑]POI补完计划#1 – qiancl 在 推箱子游戏的一个箱子推动路径搜索算法 上的评论
- HZF 在 推箱子是PSPACE完全问题 上的评论
- sokoban 在 马拉松简史 上的评论
- 跑步世界 在 马拉松简史 上的评论
文章归档
- 2021 年一月
- 2020 年十一月
- 2020 年十月
- 2020 年九月
- 2020 年八月
- 2020 年七月
- 2020 年四月
- 2020 年三月
- 2020 年一月
- 2019 年十二月
- 2019 年十一月
- 2019 年十月
- 2019 年八月
- 2019 年五月
- 2019 年四月
- 2019 年二月
- 2019 年一月
- 2018 年十二月
- 2018 年十月
- 2018 年七月
- 2018 年五月
- 2018 年四月
- 2018 年三月
- 2018 年一月
- 2017 年十二月
- 2017 年十一月
- 2017 年十月
- 2017 年九月
- 2017 年八月
- 2017 年七月
- 2017 年六月
- 2017 年五月
- 2017 年四月
- 2017 年三月
- 2017 年二月
- 2017 年一月
- 2016 年十二月
- 2016 年十一月
- 2016 年十月
- 2016 年九月
- 2016 年八月
- 2016 年七月
- 2016 年六月
- 2016 年五月
- 2016 年四月
- 2016 年三月
- 2016 年二月
- 2016 年一月
- 2015 年十二月
- 2015 年十一月
- 2015 年十月
- 2015 年八月
- 2015 年六月
- 2015 年五月
- 2015 年四月
- 2015 年三月
- 2015 年二月
- 2015 年一月
- 2014 年十二月
- 2014 年十一月
- 2014 年十月
- 2014 年九月
- 2014 年八月
- 2014 年七月
- 2014 年六月
- 2014 年五月
- 2014 年四月
- 2014 年三月
- 2014 年二月
- 2014 年一月
- 2013 年十二月
- 2013 年九月
- 2013 年七月
- 2013 年六月
- 2013 年四月
- 2013 年二月
- 2012 年十二月
- 2012 年十一月
- 2012 年十月
- 2012 年八月
- 2012 年七月
- 2012 年五月
- 2012 年四月
- 2012 年二月
- 2011 年十一月
- 2011 年九月
- 2011 年八月
- 2011 年七月
分类目录
博客链接
功能
月归档:十月 2017
跑步总结:第八个半年
本文地址:http://sokoban.ws/blog/?p=3868 最近六个月跑量如下: 2017年5月:36公里(珠海4周+广州10k+别克10k) 2017年6月:30公里(珠海5周) 2017年7月:0公里 2017年8月:5公里(环合肥翡翠湖) 2017年9月:0公里 2017年10月:25公里(下班跑回家1.5k共5次+校园中轴线3k+英东体育场5k共3次) 半年合计:96公里 体重变化如下: 经过一个学期珠海跑步,6月底体重降到60公斤以下。7月底59公斤左右;8月底60+公斤;国庆长假后一度63+公斤;10月底62+公斤。 手表 两个GPS手表已经坏了多时,今年的跑步几乎全部都是使用手机APP虎扑跑步来记录。 于是,10月又买了个100多元的EZON石英表,福建产,只具备一般的跑表功能。另有电波校时功能,能接受商丘授时中心的信号,在23层楼顶测试手动校时成功(石英表已经极其准了,校时一次就可以长时间关闭每天自动电波校时功能)。之前使用过卡西欧的日本电波表,才知道原来我们也有民用电波授时。
关卡无限大的推箱子
作者:杨超 本文地址: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甚至指出,若限制只有有限个箱子没有归位(其余可数个箱子一开始都处于目标点),问题仍然是不可判定的,或者说是不可计算的。 这从另外一个方面也体现了推箱子有多难。