魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 513302|回复: 65
打印 上一主题 下一主题

【翻译】“上帝之数"是20(初稿) [复制链接]

Rank: 2

积分
236
帖子
133
精华
1
UID
1267641
性别
保密
跳转到指定楼层
1#
发表于 2010-8-10 15:55:57 |只看该作者 |倒序浏览

原文: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.comdavidson@math.kent.edu.


    Rubik's Cube是Seven Towns公司的注册商标。
    感谢Werner Randelshofer上使用在本页魔法Java程序。




(水平有限,错误之处欢迎指正,如有更好的翻译建议欢迎提出)

superflip.jpg (19.23 KB, 下载次数: 106)

superflip

superflip

history.jpg (139.97 KB, 下载次数: 71)

history

history

solution_rate.jpg (15.38 KB, 下载次数: 87)

rate

rate

hardest.jpg (18.61 KB, 下载次数: 88)

hardest

hardest

distance_count.jpg (60.93 KB, 下载次数: 67)

dis_count

dis_count

已有 3 人评分经验 收起 理由
今夜微凉 + 10 辛苦!
夜雨听风 + 10 辛苦了
strawberry + 10 辛苦了!

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

Rank: 2

积分
236
帖子
133
精华
1
UID
1267641
性别
保密
2#
发表于 2010-8-10 16:15:32 |只看该作者
上午看到有人发网址,就试着翻译了一下。翻得不好大家多多指教哈。另外请教排版问题,图片如何插入文中。
另一位朋友的翻译参见:http://bbs.mf8-china.com/viewthread.php?tid=58793&extra=page%3D1

【几个注释】
1,魔方是1974年由Rubik教授发明的,约1980年才开始由Ideal Toys公司带到全世界范围。到1995年1月,Michael Reid证明了“超级翻转”(即角块正确,棱块位置正确但颜色翻转)需要20步才能还原。这是第一个被找到的需要20步才能还原的魔方状态。(后文指出需要20步才能还原的状态出现概率小于十亿分之一,难怪找了15年才找到第一个……)

2,1980年,人们分析了17步或更少的步数组成的有效序列(其实就是不超过17有效步的算法)的数量,并发现这个数量小于魔方的状态总数,显然一个这样的“有效序列”(算法)会对应地生成或还原一种魔方状态,这样17步或17步以内就不能还原全部的魔方状态,因此,18被确定为上帝之数的一个下限。(感谢shifujun指教)

3,“对称性”一段我自己也没有理解清楚,那个折减系数“约48”原文给了一个连接,The real size of cube space(魔方空间的实际大小),貌似很高深,我瞄了两眼也觉得看不懂,但有一点,显然2,217,093,120/55,882,296=39.67……<48,我猜会不会是比如某个“朝向”会跟相应的“镜像”重合,从而这个系数减小之类的……望大虾指点。

4,“合适解”还是“最优解”那段,比较好理解。因为既然需要20步才能还原的状态已经被找到了,上帝之数就不会小于20了。因此他们的做法是对任意状态“找出一个不超过20步的解”而不必“找出最小步解再看它有没有超过20”,这样做的好处就是大大加快了求解速度,表格中的数据显示对任意状态“找出不超过20步的解”的速度要比“找到最优解”的速度快约10000倍。

5,H陪集(cosets of H)基本不懂,请高手指教。

其他问题欢迎提出讨论。

[ 本帖最后由 firstjasmines 于 2010-8-20 22:17 编辑 ]

使用道具 举报

Rank: 1

积分
137
帖子
134
精华
0
UID
1250385
3#
发表于 2010-8-10 16:17:51 |只看该作者
感谢你的翻译,谢谢了!顶一下


选择附件上传以后,前面有一个 插入 的链接
你按一下就把图片插入到文中了

[ 本帖最后由 reta 于 2010-8-10 16:18 编辑 ]

使用道具 举报

Rank: 2

积分
470
帖子
408
精华
0
UID
1245253
性别

两年元老

4#
发表于 2010-8-10 16:18:01 |只看该作者
有人发过了把........................

使用道具 举报

铜魔

♂鉦版宅娚ミ

Rank: 8Rank: 8

积分
10831
帖子
9358
精华
1
UID
90305
性别

爱心大使 六年元老

5#
发表于 2010-8-10 16:20:37 |只看该作者
LZ辛苦了   
之前发的是英文版  没看到中文
哥拧的不是魔方,是寂寞
“人生就好比魔方,要想好下一步该怎么走”
魔方吧-福建超级群:63887957
玩魔方就是玩个低调

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
1528
帖子
1438
精华
0
UID
4455
性别
居住地
广州市
兴趣爱好
收藏

收藏爱好者 国家(地区)纪录(NR) 十年元老

6#
发表于 2010-8-10 16:20:56 |只看该作者
但人脑!=计算机,比赛中最小步数要突破20不容易阿!

使用道具 举报

Rank: 1

积分
126
帖子
123
精华
0
UID
1268006
性别
保密
7#
发表于 2010-8-10 16:32:13 |只看该作者
感谢翻译
这个的确是魔方求解划时代的突破

使用道具 举报

Rank: 1

积分
25
帖子
22
精华
0
UID
1266499
性别
8#
发表于 2010-8-10 16:48:42 |只看该作者
楼主为魔友做贡献好样的
噢噢噢噢噢噢噢噢噢噢噢

使用道具 举报

铜魔

冷血王

Rank: 8Rank: 8

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

四年元老

9#
发表于 2010-8-10 17:06:13 |只看该作者
终于有翻译的了,顶了再看
魔方—无处不在
    魔方—无可取代


使用道具 举报

Rank: 8Rank: 8

积分
18050
帖子
16478
精华
9
UID
449
性别

魔方理论探索者 论坛建设奖 爱心大使 十年元老

10#
发表于 2010-8-10 18:18:23 |只看该作者
原帖由 reta 于 2010-8-10 16:17 发表

选择附件上传以后,前面有一个 插入 的链接
你按一下就把图片插入到文中了

上传成功后,先要在文中需要插图之处点击一下,留个光标,再点击“插入”,图片就插入光标处了。

使用道具 举报

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

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

GMT+8, 2024-11-1 07:18

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部