【翻译】“上帝之数"是20（初稿）

firstjasmines

原文：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程序。

（水平有限，错误之处欢迎指正，如有更好的翻译建议欢迎提出）

firstjasmines

上午看到有人发网址，就试着翻译了一下。翻得不好大家多多指教哈。另外请教排版问题，图片如何插入文中。
另一位朋友的翻译参见：http://bbs.mf8-china.com/viewthread.php?tid=58793&extra=page%3D1

【几个注释】
1，魔方是1974年由Rubik教授发明的，约1980年才开始由Ideal Toys公司带到全世界范围。到1995年1月，Michael Reid证明了“超级翻转”（即角块正确，棱块位置正确但颜色翻转）需要20步才能还原。这是第一个被找到的需要20步才能还原的魔方状态。（后文指出需要20步才能还原的状态出现概率小于十亿分之一，难怪找了15年才找到第一个……）

2，1980年，人们分析了17步或更少的步数组成的有效序列（其实就是不超过17有效步的算法）的数量，并发现这个数量小于魔方的状态总数，显然一个这样的“有效序列”（算法）会对应地生成或还原一种魔方状态，这样17步或17步以内就不能还原全部的魔方状态，因此，18被确定为上帝之数的一个下限。（感谢shifujun指教）

3，“对称性”一段我自己也没有理解清楚，那个折减系数“约48”原文给了一个连接，The real size of cube space（魔方空间的实际大小），貌似很高深，我瞄了两眼也觉得看不懂，但有一点，显然2,217,093,120/55,882,296=39.67……<48，我猜会不会是比如某个“朝向”会跟相应的“镜像”重合，从而这个系数减小之类的……望大虾指点。

4，“合适解”还是“最优解”那段，比较好理解。因为既然需要20步才能还原的状态已经被找到了，上帝之数就不会小于20了。因此他们的做法是对任意状态“找出一个不超过20步的解”而不必“找出最小步解再看它有没有超过20”，这样做的好处就是大大加快了求解速度，表格中的数据显示对任意状态“找出不超过20步的解”的速度要比“找到最优解”的速度快约10000倍。

5，H陪集（cosets of H）基本不懂，请高手指教。

其他问题欢迎提出讨论。

[ 本帖最后由 firstjasmines 于 2010-8-20 22:17 编辑 ]

firstjasmines

这个其实我也不懂，只是上面说，这个12棱原地翻的状态，是第一被发现的被证明需要20步还原的状态。
January, 1995，Michael Reid proves that the ''superflip'' position (corners correct, edges placed but flipped) requires 20 moves.
我觉得，他给的算法只是生成了这个状态，而生成这个状态的算法可能有很多种，他所给的并不是最小还原步算法的逆算法那一个。

firstjasmines

我觉得，他说这个状态“对他们的程序来说是最难解的”，是不是可能跟他们的程序特征有关，可能由于他们的程序的某些特点，恰好就在解这种情况的时候最难算。
我其实是外行，瞎猜的。