魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 1665|回复: 7

神的数字是26,四分之一旋转标准 [复制链接]

Rank: 4

积分
2460
帖子
2162
精华
1
UID
4575
兴趣爱好
其它

十四年元老

发表于 2015-4-25 14:36:20 |显示全部楼层
本帖最后由 黑白子 于 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状态存在。
已有 1 人评分经验 收起 理由
cube_master + 12 感谢分享

总评分: 经验 + 12   查看全部评分

Rank: 4

积分
2460
帖子
2162
精华
1
UID
4575
兴趣爱好
其它

十四年元老

发表于 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。

  

使用道具 举报

Rank: 4

积分
2460
帖子
2162
精华
1
UID
4575
兴趣爱好
其它

十四年元老

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

使用道具 举报

Rank: 4

积分
2460
帖子
2162
精华
1
UID
4575
兴趣爱好
其它

十四年元老

发表于 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

  

使用道具 举报

Rank: 4

积分
2460
帖子
2162
精华
1
UID
4575
兴趣爱好
其它

十四年元老

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

使用道具 举报

Rank: 4

积分
2460
帖子
2162
精华
1
UID
4575
兴趣爱好
其它

十四年元老

发表于 2015-4-25 14:46:47 |显示全部楼层
最远状态26步

  
  
  

使用道具 举报

Rank: 2

积分
490
帖子
438
精华
0
UID
1335531
兴趣爱好
速度
发表于 2015-4-25 17:00:07 |显示全部楼层
太深奥了,不懂。

使用道具 举报

Rank: 4

积分
2460
帖子
2162
精华
1
UID
4575
兴趣爱好
其它

十四年元老

发表于 2015-4-26 21:16:24 |显示全部楼层
本帖最后由 黑白子 于 2015-5-2 08:25 编辑
公冶暖荷 发表于 2015-4-25 17:00
太深奥了,不懂。


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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2020-9-27 08:28

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部