魔方吧·中文魔方俱乐部

标题: 神的数字是26,四分之一旋转标准 [打印本页]
作者: 黑白子    时间: 2015-4-25 14:36:20     标题: 神的数字是26,四分之一旋转标准

本帖最后由 黑白子 于 2015-4-25 14:55 编辑

原文：http://cube20.org/qtm/
神的数字是26,四分之一旋转标准
鲁比克魔方的各个状态可以移动26步或者更少的步数解决。
俄亥俄州超级计算中心两名研究人员用了大约29 CPU年的计算机空闲时间，已经基本上解决了鲁比克魔方四分之一旋转标准的每个状态，并表明没有状态要求超过26步的移动。
UUFUUR'LFFUF'B'RLUURUD'RL'DR'L'DD 是第一个被证明需要移动26步的状态。
QQ截图20150425143201.png
四分之一度量标准是什么？
在立方体数学初期，如何衡量一个状态，两大阵营出现了的困难。（美国）西部海岸和斯坦福大学的数学家、自由思想家，倾向于半圈的度量，在任何扭转的面，无论旋转90度、180度或270度，算作一个单位。东海岸的人群，包括麻省理工学院，往往喜欢严谨的四分之一旋转度量，其中一个半圈算作两个动作，因为它当然可以通过连续两个四分之一旋转来实现。
事实上，四分之一旋转度量的数学是非常有趣的度量。立方体的状态可以用一个概念称为置换来描述，置换被分成偶状态和奇状态。每一个四分之一旋转度量可以从一个奇状态可以产生偶状态，反之亦然，所以四分之一旋转连接偶状态和奇状态。这不是真正的半圈度量。简单地通过检查的状态上，而不用任何搜索，可以确定任意状态的最优序列长度是偶数还是奇数。
进一步的兴趣来自于两个度量的对称性质。一个对称是一个距离，该距离是从解决最大限度为止，一个需要解决的最大数量。在半圈标准，神的数字是20，我们知道有数以亿计的这种状态。令人惊奇的是，在四分之一旋转度量，只有一个单一的状态（和它的两个旋转）是已知的，需要移动26步的最大值。尽管经过显著的努力，没有发现额外的26步状态。
即使在25步状态，只有两个状态（以及它们的旋转）已知存在。在距离24，大约有150000状态存在。

附件: QQ截图20150425143201.png (2015-4-25 14:35:42, 20.28 KB) / 下载次数 168
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjUwMzEzfDg1N2YwMjhlfDE3NjEzODI1OTh8MHww
作者: 黑白子    时间: 2015-4-25 14:39:19

本帖最后由 黑白子 于 2015-4-25 16:01 编辑

四分之一旋转神的数字历史
到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。

  
作者: 黑白子    时间: 2015-4-25 14:40:43

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

  

最少步数

  		  

状态数量

  		  

最少步数

  		  

状态数量

  
  

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

  
作者: 黑白子    时间: 2015-4-25 14:43:10

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

最远状态26步
[java3=300,300]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]UUFUUR'LFFUF'B'RLUURUD'RL'DR'L'DD[/param]
  [param=initScrpt]UUFUUR'LFFUF'B'RLUURUD'RL'DR'L'DD[/param]
[/java3]
作者: 公冶暖荷    时间: 2015-4-25 17:00:07

太深奥了，不懂。
作者: 黑白子    时间: 2015-4-26 21:16:24

本帖最后由 黑白子 于 2015-5-2 08:25 编辑
公冶暖荷 发表于 2015-4-25 17:00
太深奥了，不懂。


就是三阶魔方最远状态的最少步数是26步。这里，每步是90度，旋转180度算2步。
作者: Fenz    时间: 2020-10-18 12:35:22

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



欢迎光临 魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/) Powered by Discuz! X2