- 最后登录
- 2018-9-27
- 在线时间
- 102 小时
- 阅读权限
- 20
- 注册时间
- 2010-7-20
- 积分
- 236
- 帖子
- 133
- 精华
- 1
- UID
- 1267641
- 性别
- 保密
- 积分
- 236
- 帖子
- 133
- 精华
- 1
- UID
- 1267641
- 性别
- 保密
|
原文:http://www.cube20.org/
上帝之数是20
(超级大翻转,第一种被证明需要20步才能还原的状态。)
魔方的任意状态都可以通过20步或更少的步骤还原。
通过由Google捐赠的大约35中央处理器年(CPU-year)的空闲计算机时间,一个研究小组已经从根本上求解了魔方的所有状态,并表明没有一种状态需要超过20步。
每个魔方求解者都要使用一种算法,算法就是指求解魔方的一系列的步骤。一个算法可以使先用一系列的步骤解好顶面,然后再用另一系列的步骤解决中间棱块,等等。有很多种不同的算法,复杂程度不同,所需的求解步数也不同,但是常人所能记忆的典型的算法需要40多步。
人们猜想上帝会用一种更为有效的算法,一种总是使用最短的移动序列的算法。这就是所谓的“上帝的算法”。在这种算法中最不利的情况所需要的移动步数被称为“上帝之数”。最终,上帝之数被证明是20
在魔方引入之后,人们花了15年的时间找到了第一种可被证明需要20步才能解的魔方状态。在那之后又过了约15年,我们证明了20步可以满足所有的魔方状态。
“上帝之数”的历史
到1980年,通过分析17或更少步数的有效的独立的移动序列的数量、并证明这样的序列数比魔方的状态数要少,18被确定为上帝之数的一个下限。而第一个上限,从早期的解法册子中的算法看,很可能是80左右。这个表格总结了之后的研究成果。
我们是如何做的
我们是如何将43,252,003,274,489,856,000种魔方的状态全部解决的?
1.我们将这些状态分解成2,217,093,120个子集,每个子集包括19,508,428,800状态。
2.我们通过采用对称性和集合覆盖的方法,将需要求解的子集数缩减至55,882,296。
3.我们并没有对每一种状态寻求最优解,而只是寻求不超过20步的解。
4.我们编写了可以在约20秒内完成一个单独子集的求解的程序。
5.我们用了约35中央处理器年来寻找所有的55,882,296个子集内每个状态的解。
分解
我们把问题分成2,217,093,120个较小的问题,每个小问题包含了19,508,428,800种不同的状态。每个子问题都小到可以适应现代个人计算机的内存,我们这种分解的方法能让我们对每个子集迅速求解。
对称性
如果你拿起一个打乱的魔方,然后把它上面翻转到下面,你实际上并没有使魔方变得更为复杂难解,求解所花的步骤仍是一样的。你只需要解一个,然后把解法上下翻转就可以解决另一个了,而不需要把这两种状态一一求解。魔方在空间上可以有24个不同的朝向,还有一个因子是两个魔方互为镜像,这样在需要求解的状态的数量中包含了一个“大约为48(http://www.math.rwth-aachen.de/~ ... _of_cube_space.html)”的折减系数。采用类似的对称性论证,并通过寻找一种大型“集合覆盖”问题的解法,我们最终能够将需要求解的子集的数量从2,217,093,120缩减为55,882,296。
“合适解”还是“最优解”
某状态的最优解是指所需要的最少步骤。既然我们已经发现了一种需要20步才能解的状态,那么我们就不必对所有状态都去寻求最优解,而只需要对每个序列找到一种20步或更少的解法就可以了。这就使问题容易了很多。左边的表格表明了一台性能良好的台式机求解随机状态的效率。
快速的陪集求解程序
结合数学技巧和精心的编程,我们就能够以左表中的速度在一台台式机上求解一个完整的H陪集,既可以求最优解,也可以求不超过20步的解。
大量的计算机
最终,我们将 55,882,296个H陪集分配在由Google提供的大量计算机上,并在短短的几周之内完成了计算。Google并没有公布他们的计算机系统的信息,但是执行这次计算需要花费一台配置良好的台式机(英特尔Nehalem架构,四核,2.8GHz主频)11亿秒(或35中央处理器年)的时间。
最难解的状态是什么
我们知道存在需要20步才能求解的状态已经有15年的时间了。我们证明的是,不存在需要更多求解步的状态。
需要20步才能求解的状态即是罕见的,又是大量存在的。这种状态出现的概率小于十亿分之一,但是很可能存在超过一亿种这样的状态。我们现在还不清楚这种状态的确切数目。右表给出了需要不同步数还原的魔方状态数。对于需要16步或更多的情况,给出的数字只是一个估计。我们的研究已经证明了前面的0至14步的情况,15步的情况是最新的成果。我们希望这项成果的独立证明由另一位研究者在本月内完成。
迄今为止,我们已经找到了大约一千二百万种需要20步才能解决的状态。下面的状态是对于我们的程序来说最难的状态。
联系方式
我们的小组包括:来自肯特州立大学的数学家Morley Davidson,来自山景城的Google工程师John Dethridge,来自德国达姆施塔特市的数学教师Herbert Kociemba,以及来自加利福尼亚州的帕罗奥多市的程序师Tomas Rokicki。联系邮件可以发送至至rokicki@gmail.com 或 davidson@math.kent.edu.
Rubik's Cube是Seven Towns公司的注册商标。
感谢Werner Randelshofer上使用在本页魔法Java程序。
(水平有限,错误之处欢迎指正,如有更好的翻译建议欢迎提出) |
-
总评分: 经验 + 30
查看全部评分
|