【翻译】“上帝之数"是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程序。

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

铯_猪哥恐鸣

黑白子 发表于 2015-3-18 21:37
循环公式构造的状态为什么具有相同的环结构？理论上能否解释？

因为它们是互为共轭，可参考：http://zh.wikipedia.org/wiki/%E5%85%B1%E8%BD%AD%E7%B1%BB

黑白子

循环公式构造的状态为什么具有相同的环结构？理论上能否解释？

黑白子

原来循环公式做出的状态不一定相同。

pengw

58楼说:
"公式 P = R U D R2 B R' L B2 U2 F2 D R2 F' B' R U2 L B2 R
  
　= (R U D R2 B R' L B) (B U2 F2 D R2 F' B' R U2 L B2 R)  ，分割 B2
  
　　公式 Q = (B U2 F2 D R2 F' B' R U2 L B2 R) (R U D R2 B R' L B)  
   
　= B U2 F2 D R2 F' B' R U2 L B2 R2 U D R2 B R' L B ，归并 R R 为 R2
  
    此时 公式 Q 称为 公式 P 的 一个 循环公式 。"

公式P与公式Q在复原状态下做出来的状态根本就是二种状态,就算G大帅不认为90/步是改变状态的最小单位,归并后的Q公式难到真比P公式更短且复原了魔方?哈哈哈

[ 本帖最后由 pengw 于 2010-8-20 11:07 编辑 ]

ggglgq

　　
　　
  
    互为 循环公式（特殊的“相似变换”）的所有 状态，都具有相同的 环结构，
  
因此也都具有相同的 最小循环周期 。相关内容请参考： 循环公式的一种现象
  
        http://bbs.mf8-china.com/viewthread.php?tid=562

        http://www.randelshofer.ch/rubik/scriptfacility.html
  
当然它在最少步数上也有不可替代的作用，但这需要根据“环结构”综合测定，
  
不是一两句话能说清楚的。即 有时可运用“循环公式”（特殊的“相似变换”）
  
知识 构造出 不同的 最少步状态 及 最远状态 。 这是循环理论的另一用法。
  
　　
　　
　　

[ 本帖最后由 ggglgq 于 2010-8-18 18:56 编辑 ]

黑白子

原文说“……公式 P = R U D R2 B R' L B2 U2 F2 D R2 F' B' R U2 L B2 R
  
　= (R U D R2 B R' L B) (B U2 F2 D R2 F' B' R U2 L B2 R)  ，分割 B2
  
　　公式 Q = (B U2 F2 D R2 F' B' R U2 L B2 R) (R U D R2 B R' L B)  
   
　= B U2 F2 D R2 F' B' R U2 L B2 R2 U D R2 B R' L B ，归并 R R 为 R2
  
    此时 公式 Q 称为 公式 P 的 一个 循环公式 。”
可是执行公式P和它的循环公式Q，得到的结果不同。循环公式有什么用途呢？

ggglgq

　　
  
  
    这样统一规定也是可以的。
　　
　　

乌木

确实，用U U'……12种基本操作，不考虑U2等动作－－用U U或U' U'代替，这样较好。

用12基本操作和用18基本操作应是两种统计步数的方法，恐怕不宜在同一问题中，一会儿用12基本操作法，一会儿用18基本操作法，即，不宜在同一问题中一会儿把D2算一步，一会儿把D2看作D D算两步，甚至再把D和D分置于公式的两头，人为弄出不同的步数来。（当然，最后两种结果都没错，只不过统计法变了而已。）
不知我的看法对吗？

补充：我想，在18基本操作统计步数的方法中，U2这一步的变化是只考虑前一态“跃迁”为后一态的，不应该去考虑其中“经过”所谓“中间态”U或U'的，故，18基本操作法不能把U2看作UU或 U'U'的，U2就是一步。对吗？

此事或许得看什么场合，在计较步数时，认定一种统计方法（180°要么算一步，要么算两步）；在探讨公式的变换时，就要灵活处理，需要时，U2就得拆为UU或U'U'，等等。

[ 本帖最后由 乌木 于 2010-8-18 14:26 编辑 ]

ggglgq

原帖由 黑白子 于 2010-8-16 15:52 发表
  
已知一个公式，如何求它的循环公式呢？
例如，如何求下面这个公式的循环公式?
R U D R2 B R' L B2 U2 F2 D R2 F' B' R U2 L B2 R
  

　　
  
    这里我想用一个 最简明 的方式来定义“循环公式”：
  
    如果 公式 P 可以分成 操作 A 、操作 B 前后两个部分： 即 P = A B ，
  
那么 公式 Q = B A 称为 公式 P 的 一个 循环公式 。
  
    由“循环公式”的定义可以得出，如果 公式 Q 为 公式 P 的 循环公式，
  
那么 公式 P 也为 公式 Q 的 循环公式，即 它们彼此互为 循环公式 。
  
  
    当然 公式 P 的 循环公式 可以很多，大家可以根据定义构造出 公式 P
  
的 多个 循环公式 ，它们之间互称 循环公式 。  如果公式 P 无法分成两个
  
部分，此时 公式 P 的 循环公式 就是 公式 P 自身。
  
  
   
  
    同样很容易证明，互称 循环公式 的 两个公式 同时互称 “相似变换”。
  
证明从略。
  
  
  
    这里需要注意 三 点：
  
    1、 公式 P 分成的 操作 A 、操作 B 前后两个部分，必须是 原公式 P
  
的 前后两个部分，不能增加或减少或改变 原公式 P 。
  
  
    2、 分割、归并 公式中的非单位操作，由魔方的 基本操作 确定。
  
　　　如对于 正六面体 三 阶魔方，一般定义的操作为 U、U2、U' 等 18 种
  
基本操作（有的还定义 中层、整体旋转，对于其他魔方可能还有 U3 等操作）
  
分割、合并公式中的非单位操作，可由魔方的 基本操作 确定，比如 黑白子
  
提供的　　
  
　　公式 P = R U D R2 B R' L B2 U2 F2 D R2 F' B' R U2 L B2 R
  
　= (R U D R2 B R' L B) (B U2 F2 D R2 F' B' R U2 L B2 R)  ，分割 B2
  
　　公式 Q = (B U2 F2 D R2 F' B' R U2 L B2 R) (R U D R2 B R' L B)  
   
　= B U2 F2 D R2 F' B' R U2 L B2 R2 U D R2 B R' L B ，归并 R R 为 R2
  
    此时 公式 Q 称为 公式 P 的 一个 循环公式 。
  
  
    当然，如果 正六面体 三 阶魔方 只给提供基本操作为 U、U' 等 12 种
  
基本操作，那就简单多了。如果 正六面体 三 阶魔方 还容许 中层、整体旋转
  
基本操作，那就麻烦许多，等等  ......  。 这些情况 请大家自己排列组合
  
总结规律。
  
  
    3、 公式 P 为最少步公式，但 公式 P 的（某个）循环公式 Q 却 不一定
  
是 最少步公式。比如对于 正六面体 三 阶魔方 来说， D2 U2 是 最少步公式，
  
但是 它的 循环公式 D U2 D 明显不是 最少步公式。（这仅是个最简单的例子，
  
实际情况复杂得多。）