魔方吧·中文魔方俱乐部

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

【翻译】20步可还原任意状态魔方 [复制链接]

银魔

哈尔滨的~

Rank: 7Rank: 7Rank: 7

积分
3803
帖子
3045
精华
12
UID
24088
性别
保密

魔方理论探索者 六年元老

发表于 2010-8-10 22:50:36 |显示全部楼层
原文:www.cube20.org
__________________________________________________

上帝之数是20


3×3×3魔方的每一个状态都可以在20步以内还原。
通过由Google贡献的大约时长35年的CPU空闲时间,一个研究团队已经根本地(essentially)解决3×3×3魔方的每一个状态,并进一步提出没有状态需要超过20步还原。 每一个状态都用一个有着一连串步骤的算法解决。这用的算法可能用一连串的步骤解决顶层,然后用另一串步骤解决中间的边块,然后是类似的步骤。我们知道很多不同的算法,它们在复杂度和所需步数上有所不同,但是那些可以被人类记忆的方法通常要超过40步。
Superflip,第一个被证明最少需要20步还原的状态。
有人可能猜测上帝用的算法更高效,总是用最少的步骤解决;这被称作"上帝算法"(God's Algorithm)。这个算法在解决最复杂的魔方状态时所用的步数称作"上帝之数"。终于,上帝之数被证明是20了。 从有魔方以来,人们花了15年时间才找到第一个被证明至少需要20步才能还原的状态;在那之后,我们又花了将近15年证明了20步可以解决所有的状态。


上帝之数的历史
到1980年,通过分析小于等于17步的有效不同转动得到的状态数,发现这个数字小于3×3×3魔方的状态数,所以上帝之数的下界被确定为18。由早期的魔方解决方法小册子的算法来看,第一个上帝之数的上界大概在80左右。这个表格统计了随后的成果。

日期下界上界范围摘要和链接
1981年7月185234Morwen Thistlethwaite 证明 52 步足够了。
1992年4月184224Hans Kloosterman把它改善到 42步
1992年5月183921Michael Reid 证明 39 步总是足够的。
1992年5月183719Dik Winter 一天之后就把它降低到 37 步
1995年1月182911Michael Reid在分析完Kociemba's two-phase algorithm后把上界减少到29 步
1995年1月20299Michael Reid 证明 ''superflip'' 状态(角块全正确, 棱块全部原地翻转) 需要 20 步
2005年12月20288Silviu Radu 证明 28 步 总是足够的。
2006年4月20277Silviu Radu 改善他得到的上界到 27 步
2007年5月20266Dan Kunkle 和 Gene Cooperman 证明 26 步是足够的。
2008年3月20255Tomas Rokicki 把上界减少到 25 步
2008年4月20233Tomas Rokicki 和 John Welborn 把它减少到只有 23 步
2008年8月20222Tomas Rokicki 和 John Welborn 把它继续减少到 22 步
2010年7月20200Morley Davidson, John Dethridge, Herbert Kociemba, 和 Tomas Rokicki 四人证明了上帝之数确切的是20步。
  我们是如何做的我们如何解决全部43,252,003,274,489,856,000种状态的?
  • 我们把状态分成2,217,093,120个集合,每个集合有19,508,428,800种状态。
  • 我们通过对称性和集合覆盖把要解决的集合数减少到55,882,296个。
  • 我们并没有找到每个状态的最小步,但是我们找到了小于等于20步的解法。
  • 我们写个一个可以在大约20秒解决一个集合的程序。
  • 我们用了大约35个CPU年解决了这55,882,296个集合里的所有状态。
分区法
我们将这个大问题化为2,217,093,120个小问题,每个问题由19,508,428,800个不同的状态组成。每个子问题都足够小到可以用一台流行配置的电脑解决,我们分解问题的方法(数学上,运用{U,F2,R2,D,B2,L2}生成的群的陪集(coset),简单的说就是H的陪集)使得我们可以非常快速的解决每一个集合。
对称性
如果你拿一个混乱的魔方,把它上下颠倒一下,这样你不会把它变得更难还原;它还是需要同样的步数还原。还原这两个状态,你可以只还原其中一个状态,然后把解决方法也上下颠倒一下就可以还原另一个状态了。一个魔方在空间中有24种不同的摆放方法,通过镜像可以得到2种对称状态,所以总共可以减少48倍需要还原的状态。运用类似对称论证和找到一个解决到一个大的"集合覆盖(set cover)"问题的方法,我们能把要解决的集合数从2,217,093,120减少到55,882,296。
好方法和最优方法
随机状态H的陪集
最优化0.362,000,000
20步或更少3,9001,000,000,000
一个最优方法不需要比还原必要的步数多的步数还原。自从发现了一个还原必要步数是20步的状态,我们就不需要用最优方法解决每一个状态了;我们只需要找到一个小于等于20步的方法还原每一个状态。这要简单相当多;左边的表格显示了一个配置较好的台式电脑解决随机状态时的速度。
解决速度,状态数/秒
快速陪集求解程序运用数学技巧和精心编程的结合,我们能在一台台式机上以左边表格里写的速度解决完整的H的陪集,得到最优方法或者小于等于20步的方法。
   大量的电脑最终,我们能将这55,882,296个H的陪集分派到Google的大量的电脑上,并在几个星期内完成计算。Google没有公布它的电脑系统信息,但是这将会花费一台配置较好的台式机(Intel Nehalem, 四核, 2.8GHz) 11亿秒,即35个CPU年,去完成这个计算。
最难的状态是什么?
我们知道有些状态最少需要20步还原已经15年了;我们刚刚证明了没有状态需要更多的步数。 最少步需要20步的状态既罕见又丰富;它们罕见是因为它们只有全部状态的十亿分之一,然而很可能有超过一亿个这样的状态。我们还不能确切的知道它们到底有多少。这张右边的表格给出了每个最小步数所包含的状态数。对于大于等于16步的情况,只能给出一个估值。我们的研究已经确认前面的结果,从0到14,15步的结果是一个新成果。我们希望月内能有另外的研究者独立确认这个结果。
到目前为止我们已经发现了大约2000万个最小步20步的状态。下面的状态曾是我们的程序遇到的最难解决的状态:

最小步数状态数量
01
118
2243
33,240
443,239
5574,908
67,618,438
7100,803,036
81,332,343,288
917,596,479,795
10232,248,063,316
113,063,288,809,012
1240,374,425,656,248
13531,653,418,284,628
146,989,320,578,825,358
1591,365,146,187,124,313
16大约 1,100,000,000,000,000,000
17大约 12,000,000,000,000,000,000
18大约 29,000,000,000,000,000,000
19大约 1,500,000,000,000,000,000
20大约 300,000,000
联系我们
我们的团队由这些人组成:
Morley Davidson,肯特州立大学的数学家
John Dethridge,Google总部加利福尼亚州山景城的工程师
Herbert Kociemba,德国达姆施塔特的数学老师
Tomas Rokicki,美国加利福尼亚州帕罗奥图市的程序员
我们的Email是:
rokicki@gmail.com
davidson@math.kent.edu


Rubik's Cube是Seven Towns, Ltd的注册商标。
感谢Werner Randelshofer为此页面提供的魔方展示插件。



------------------------------------------------------------------------------------

[ 本帖最后由 shifujun 于 2010-8-11 20:39 编辑 ]
桥式是一种思想而不是一套公式!

银魔

哈尔滨的~

Rank: 7Rank: 7Rank: 7

积分
3803
帖子
3045
精华
12
UID
24088
性别
保密

魔方理论探索者 六年元老

发表于 2010-8-10 22:54:10 |显示全部楼层
其实俺昨天晚上就翻译完了,就是没搞定排版的问题。
桥式是一种思想而不是一套公式!

使用道具 举报

铜魔

冷血王

Rank: 8Rank: 8

积分
12477
帖子
8833
精华
4
UID
74604
性别

四年元老

发表于 2010-8-10 22:57:30 |显示全部楼层
好像是不是有人先你一步了?用的是穷举法?

[ 本帖最后由 kattokid 于 2010-8-10 22:58 编辑 ]
魔方—无处不在
    魔方—无可取代


使用道具 举报

银魔

哈尔滨的~

Rank: 7Rank: 7Rank: 7

积分
3803
帖子
3045
精华
12
UID
24088
性别
保密

魔方理论探索者 六年元老

发表于 2010-8-10 23:03:38 |显示全部楼层
确实是穷举了,48同态算1个,还有我听不懂的集合覆盖,通过这两个手段减少了一部分状态。其余状态都穷举了。
桥式是一种思想而不是一套公式!

使用道具 举报

Rank: 4

积分
2382
帖子
2101
精华
1
UID
4575
兴趣爱好
其它

十年元老

发表于 2010-8-10 23:10:26 |显示全部楼层
妙!两幅图案都是24步。

使用道具 举报

Rank: 3Rank: 3

积分
889
帖子
578
精华
0
UID
68034
性别
保密

四年元老

发表于 2010-8-10 23:13:37 |显示全部楼层
翻译得很好,我算明白一点上帝之数的算法了

使用道具 举报

银魔

哈尔滨的~

Rank: 7Rank: 7Rank: 7

积分
3803
帖子
3045
精华
12
UID
24088
性别
保密

魔方理论探索者 六年元老

发表于 2010-8-10 23:13:46 |显示全部楼层
原帖由 黑白子 于 2010-8-10 23:10 发表
妙!两幅图案都是24步。

那个原网页实际只是想展示一下打乱是什么样子的,没想贴出来20步的还原步骤。
桥式是一种思想而不是一套公式!

使用道具 举报

红魔

小熊

Rank: 4

积分
2426
帖子
2034
精华
1
UID
80942
性别
居住地
苏州市
兴趣爱好
理论

四年元老

发表于 2010-8-10 23:43:03 |显示全部楼层
无奈飘过。。。。。。。。。。。
挣扎吧。。在血和暗的深渊里。。

使用道具 举报

Rank: 2

积分
236
帖子
133
精华
1
UID
1267641
性别
保密
发表于 2010-8-11 11:07:27 |显示全部楼层
这……很尴尬一不小心抢了你的风头……
讨论两个翻译问题吧:
A History of God's Number,那段第一句:
By 1980, a lower bound of 18 had been established for God's Number by analyzing the number of effectively distinct move sequences of 17 or fewer moves, and finding that there were fewer such sequences than Cube positions.
这句话,18被确定为上帝之数的下限然后by后面的内容我其实没看懂,“the number of effectively distinct move sequences of 17 or fewer moves”,还有 “there were fewer such sequences than Cube positions”是什么意思。
还有,
Symmetry,那一段中间一句:
There are 24 different ways you can orient the Cube in space, and another factor of two using a mirror, for a total reduction of a factor of about 48 in the number of positions that need solving
这句话意思我大概看懂了,但是and后面的语法结构我没搞明白。
这两处你是怎么理解的,望指教。

使用道具 举报

透魔

阿V

Rank: 6Rank: 6

积分
7728
帖子
6455
精华
2
UID
1253084
WCA ID
2010ZHAN17
兴趣爱好
速度

论坛建设奖 爱心大使 六年元老 八年元老

发表于 2010-8-11 11:08:35 |显示全部楼层
怎么又变成20了,不是17吗、???
静坐常思己过,闲谈莫论人非

使用道具 举报

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

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

GMT+8, 2019-6-17 13:43

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部