文章
Slash Boxes
评论

魔方最少还原步数降至23步

matrix 发表于 2008年6月06日 14时00分 星期五   Printer-friendly   Email story
来自上帝算法部门
数学 经典游戏 科学
3月份我们曾报道，Tomas Rokick正在开发一个非常高效的方法研究魔方最少的还原步骤，他证明任何魔方都可以在25步内还原。现在根据Tomas Rokick个人主页的更新，他宣布任意结构的魔方都可以在23步内解决。他之前进行运算的工作站为8G内存和1.6GHz Q6600 CPU，现在已经升级为一台超级计算机，索尼图形图像运作公司（Sony Pictures Imageworks）提供给他使用（当然是在电影制作空闲时间内）。在这个曾经制作了《蜘蛛侠3》和《冲浪企鹅》的工作室的帮助下，新的计算结果暗示任意结构的魔方可能的解决步数是21，22或23步。

相关文章

数学家证明魔方可在25步内还原 8 条评论 [+]
Rubik's Cube的中文名叫魔方，是匈牙利的Rubik教授在1974年发明的智力玩具。去年两位东北大学学生用了一点手上的空闲时间证明任何结构的魔方都能在26步内还原。现在Tomas Rokicki，在斯坦福大学受过训练的数学家更胜一筹，他证明没有一种结构的魔方需要26步才能还原，因此他将还原最少步骤降至25步(论文预印本)。Rokicki的证明完全依靠计算机科学，他使用立方体的对称来研究集合内的转换，这允许他将“立方体空间”分割成20亿个集合，每个集合包含200亿个项。他发现许多集合与其它集合本质上是相同的，因此可以去除。为了完成整个计算，他需要一个8G内存的工作站，1.6GHz频率的Q6600 CPU运行1500小时。这个过程目前还未完成，Rokicki已经着手下一步：24步内还原，这么推测下来，想必23正在向他招手。魔方的极限在何处？已知有些组合能用20步解决，但也还知道没有一种组合是能用21步解决的。20可能是个界限。
This discussion has been archived. No new comments can be posted.
魔方最少还原步数降至23步 | 登录/创建一个账号 | 顶部 | 3 条评论 | 搜索讨论
显示选项 门槛:
声明: 下面的评论属于其发表者所有，不代表本站的观点和立场，我们不负责他们说什么。