魔方吧·中文魔方俱乐部

标题: 科学家们通过计算机计算和证明，任意组合的魔方都可以在20步内还原 [打印本页]

作者: 谢老师 时间: 2010-8-13 22:37:44 标题: 科学家们通过计算机计算和证明，任意组合的魔方都可以在20步内还原

科学家们通过计算机计算和证明，任意组合的魔方都可以在20步内还原。
　　尽管拥有43,252,003,274,489,856,000种不同的可能组合状态，但魔方都可以在20步内还原。
　　北京时间8月13日消息，据国外媒体报道，相信许多人都玩过魔方，但是此前没有人知道任意组合的魔方的最小还原步数究竟是多少。这一问题困扰了数学家长达三十多年，这个最小还原步数也被称为“上帝之数”。美国科学家近日利用计算机破解了这一谜团，研究人员证明任意组合的魔方均可以在20步之内还原，“上帝之数”正式定为20。
　　这支研究团队位于美国加利福尼亚州帕洛阿尔托市。科学家们通过计算机计算和证明，任意组合的魔方都可以在20步内还原。这一结果表明，大约有10万多种的起始状态恰好可以在20步内还原。
　　利用谷歌公司计算机强大的计算能力，研究人员检验了魔方任何可能的混乱状态(确切数字为43,252,003,274,489,856,000)。美国俄亥俄州肯特州立大学数学家莫雷·戴维德森教授也是研究人员之一，他表示，“我们现在可以肯定，这个‘上帝之数’就是20。对于我来说，我也回到了原地。魔方伴随着我成长，这也是我为什么深入研究这个数学问题的原因。这个谜团引起了人们的广泛关注，它也许是人类历史上最受欢迎的谜语了。”科学家们的初步研究成果发表于网站上，但戴维德森表示，他们准备将研究成果提交给杂志正式发表。
　　程序员托马斯·罗基花了15年的时间，致力于寻找这个谜团的答案。据罗基介绍，研究团队所采用的算法可以在1秒钟内尝试10亿种可能，此前的计算机算法1秒钟内只能处理4000种可能。
　　为了让问题简单化，研究团队采用了一种所谓“群论”的数学技术。他们首先将魔方所有可能的起始状态集分成22亿个集合，每个集合包含了195亿个可能的状态。集合的分配原则是这些可能的状态是如何应对一组10个可能的还原步骤。再通过魔方不同的对称性，这种分组技术使得研究团队将集合数减少到5600万个。
　　研究人员所采用的算法可以快速将这些还原步骤与恰当的起始点匹配起来，从而实现在20秒内处理一个集合中的195亿种可能。对于普通的家用电脑来说，以这样的速度完成整个处理任务需要大约35年时间。
　　2007年，《每日电讯报》曾经报道称，任意组合的魔方均可在26步内还原。当然，还有其他的报道称已证明出更少的还原步骤。魔方由匈牙利埃尔诺·鲁比克教授于1974年所发明，曾经是世界上最畅销的智力玩具。

作者: 谢老师 时间: 2010-8-13 22:37:52

新浪科技

http://tech.sina.com.cn/d/2010-08-13/07334540637.shtml

科学网首页>新闻中心>正文

http://news.sciencenet.cn/htmlnews/2010/8/236020.shtm

維基百科，自由的百科全書

http://zh.wikipedia.org/zh-hk/%E9%AD%94%E6%96%B9

上帝的數字所有的三階扭計骰都可以在有限步數內復原，1982年，佛雷與辛馬斯特合著的《扭計骰手冊》定義任意的三階扭計骰都可以保證最少n步復原，並稱呼n為上帝的數字。在此書中，證明上帝的數字介於17~52之間。
1995年，瑞德證明上帝的數字介於20~29之間。2006年，雷杜用群論證明上界可改進為27。
2007年，電腦科學家古柏曼與他的學生用20台超級電腦花了8000個小時證明上界可改進為26。[29]
Tomas Rokicki於2008年宣布證明了任何扭計骰可以在25步以內解開[30]。之後又改進為22步[31]。
2010年,包括Tomas Rokicki和Morley Davidson等人的研究團隊證明任意組合的扭計骰可以在20步內還原。[32]現在上帝之數正式定為20。

当然这个是指三阶魔方的任何打乱情况，呵呵！不包括高阶、异型！

[ 本帖最后由谢老师于 2010-8-13 23:16 编辑 ]

作者: robester 时间: 2010-8-13 22:40:55

第五个了

作者: Vicki 时间: 2010-8-13 22:43:08

谢老师又发一遍~

作者: kattokid 时间: 2010-8-13 22:52:40

谢老师也发了啊！看来最近很热闹啊！上帝之数被找出来了

作者: haohmaru 时间: 2010-8-13 22:54:35

根据摩尔定律，
3年后的家用电脑需9年可计算完成
6年后的家用电脑可用2年计算完成
如果那些超级计算机能用在计算这个上面
那很快就可以出结果了

作者: 夜雨听风 时间: 2010-8-13 23:03:17

又见译文算高阶算法的软件就OK

作者: Paracel_007 时间: 2010-8-13 23:15:53

这的确是大事件啊。。。这么多帖子。。。

作者: 谢老师 时间: 2010-8-13 23:18:30

糟糕！看来，发之前要先查一下，呵呵！最近少看帖子啊！罪过！

作者: 龙魔 时间: 2010-8-14 07:51:09

看来上帝之数有了定论，长达N年之谜有了答案，剩下的是魔方高手们在实践中如何去找这个上帝之数了

作者: oboe 时间: 2010-8-15 12:31:31

那么以后比赛多一项了：只用20步还原的最少时间。

作者: 乌木 时间: 2010-8-15 15:59:18

原帖由 oboe 于 2010-8-15 12:31 发表
那么以后比赛多一项了：只用20步还原的最少时间。

是否先要有一套至少20步才能复原的打乱步骤吧？至于选手是用20步还是多于20步还原，不必管也无法看清的吧？
比如那个superflip态，那文章中除了说要20步复原外，也给出了22步复原步骤。具体的20步，“黑王子”、“hubo5563”和“noski”给出了多种20步步骤，见http://bbs.mf8-china.com/viewthread.php?tid=58758&extra=&page=4 。

作者: 谢老师 时间: 2010-8-18 15:51:14

谢谢乌木老师指点！

我看可以征集最远状态的魔方打乱程序，以后按这个程序生成WCA比赛打乱公式，希望在不远的将来，有电脑高手做出来！

作者: TOSO 时间: 2010-8-18 16:15:29

人脑赶不上电脑。

作者: shibazi88617 时间: 2010-9-22 17:18:47

看来我是孤陋寡闻了~~~我足足比LZ晚了一个月才在杂志上知道这件事~~~~~~~

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