神的数字是26,四分之一旋转标准

黑白子

原文：http://cube20.org/qtm/
神的数字是26,四分之一旋转标准
鲁比克魔方的各个状态可以移动26步或者更少的步数解决。
俄亥俄州超级计算中心两名研究人员用了大约29 CPU年的计算机空闲时间，已经基本上解决了鲁比克魔方四分之一旋转标准的每个状态，并表明没有状态要求超过26步的移动。
UUFUUR'LFFUF'B'RLUURUD'RL'DR'L'DD 是第一个被证明需要移动26步的状态。

四分之一度量标准是什么？
在立方体数学初期，如何衡量一个状态，两大阵营出现了的困难。（美国）西部海岸和斯坦福大学的数学家、自由思想家，倾向于半圈的度量，在任何扭转的面，无论旋转90度、180度或270度，算作一个单位。东海岸的人群，包括麻省理工学院，往往喜欢严谨的四分之一旋转度量，其中一个半圈算作两个动作，因为它当然可以通过连续两个四分之一旋转来实现。
事实上，四分之一旋转度量的数学是非常有趣的度量。立方体的状态可以用一个概念称为置换来描述，置换被分成偶状态和奇状态。每一个四分之一旋转度量可以从一个奇状态可以产生偶状态，反之亦然，所以四分之一旋转连接偶状态和奇状态。这不是真正的半圈度量。简单地通过检查的状态上，而不用任何搜索，可以确定任意状态的最优序列长度是偶数还是奇数。
进一步的兴趣来自于两个度量的对称性质。一个对称是一个距离，该距离是从解决最大限度为止，一个需要解决的最大数量。在半圈标准，神的数字是20，我们知道有数以亿计的这种状态。令人惊奇的是，在四分之一旋转度量，只有一个单一的状态（和它的两个旋转）是已知的，需要移动26步的最大值。尽管经过显著的努力，没有发现额外的26步状态。
即使在25步状态，只有两个状态（以及它们的旋转）已知存在。在距离24，大约有150000状态存在。

黑白子

四分之一旋转神的数字历史
到1980年，上帝的数字下限19被确定，通过分析17或更少的有效的不同移动序列步数，并且发现这样的序列，比奇状态的魔方状态少。第一个上限，通过分析早期解决方案的小册子最坏情况下的移动步数，大概在140左右。这个表格总结了后续的结果。

日期	下界	上限	差距	注释和链接
1981年1月	21	140	119	丹霍伊首先表明，有的状态需要21步。
1981年7月	21	104	83	西斯尔思韦伟证明52步够了;两倍的给出了下限104在四分之一旋转标准。
1992年5月	21	56	35	迈克尔·里德证明56步就足够了。
1995年1月	21	42	21	迈克尔·里德证明42步就足够了。
1995年1月	22	42	20	迈克尔·里德发现，一些状态至少需要22步。
1998年8月	26	42	16	迈克尔·里德证明superflip加fourspot需要26步。
2005年11月	26	40	14	西尔维乌普拉杜降低上限为40步。
2006年1月	26	38	12	布鲁斯诺思克降低上限为38步。
2006年1月	26	36	10	西尔维乌普拉杜降低上限为36步。
2006年3月	26	35	9	西尔维乌普拉杜降低上限为35步。
2007年7月	26	34	8	西尔维乌普拉杜降低上限为34步。
2009年1月	26	32	6	托马斯罗基奇降低上限为32步。
2009年1月	26	31	五	托马斯罗基奇降低上限为31步。
2009年2月	26	三十	4	托马斯罗基奇降低上限至30步。
2009年6月	26	29	3	托马斯罗基奇降低上限为29步。
2014年8月	26	26	0	托马斯罗基奇和莫雷戴维森终于证明了神的数字在四分之一旋转标准是26。

黑白子

我们是如何做到的
我们怎么解决这个魔方的所有43,252,003,274,489,856,000状态？
•        我们将这些状态分成2217093120组，每组19508428800状态。
•        我们通过用对称和覆盖，将求解的组数降低到55882296。
•        我们没有发现每一状态的最佳解决方案，但寻找长度26或更少的而不是唯一的解决方案。
•        我们写了一个程序，解决一组在17秒左右。
•        我们使用了大约29CPU年，以找到解决所有在每个55882296组的状态的解。

黑白子

最少步数	状态数量	最少步数	状态数量
0	1	14	50,729,620,202,5​​82
1	12	15	472,495,678,811,004
2	114	16	4,393,570,406,220,123
3	1068	17	40,648,181,519,827,392
4	10011	18	368,071,526,203,620,348
5	93840	19	约3,000,000,000,000,000,000
6	878880	20	约14,000,000,000,000,000,000
7	8221632	21	约19,000,000,000,000,000,000
8	76843595	22	约7,000,000,000,000,000,000
9	717789576	23	约24,000,000,000,000,000
10	6701836858	24	约150.000
11	62549615248	25	36？
12	583570100997	26	3？
13	5,442,351,625,028	> 26	0

黑白子

联系
这项工作是由托马斯罗基奇、来自加利福尼亚州帕洛阿尔托程序员和来自肯特州立大学数学家莫利•戴维森进行。电子邮件可发送到rokicki@gmail.com或davidson@math.kent.edu。
鲁比克魔方是Seven Towns公司的注册商标。
感谢卢卡斯嘉禹为此页面上写的魔方动画。
这项工作是由来自美国俄亥俄州超级计算机中心的计算机支持。

黑白子

最远状态26步

  
  
  

公冶暖荷

太深奥了，不懂。

黑白子

公冶暖荷 发表于 2015-4-25 17:00
太深奥了，不懂。

就是三阶魔方最远状态的最少步数是26步。这里，每步是90度，旋转180度算2步。

Fenz

数学分析的话，R2、M都算作两步比较合理。26 比 20 更有意义