科学家15年证明还原任意魔方最多需20步(图)

发表:2010-08-13 20:46
手机版 正体 打赏 0个留言 打印 特大

尽管有43,252,003,274,489,856,000(约合4.3×1019) 种不同的可能组合状态,但魔方都能在20步内还原。

据国外媒体报道,相信许多人都玩过魔方,但是此前没有人知道任意组合的魔方的最小还原步数究竟是多少。这一问题困扰了数学家长达三十多年,这个最小还原步数也被称为“上帝之数”。美国加利福尼亚州科学家近日利用计算机破解了这一谜团,研究人员证明任意组合的魔方均可以在20步之内还原,“上帝之数”正式定为20。

这支研究团队位于美国加利福尼亚州帕洛阿尔托市。科学家们通过计算机计算和证明,任意组合的魔方都可以在20步内还原。这一结果表明,大约有10万多种的起始状态恰好可以在20步内还原。

利用谷歌公司计算机强大的计算能力,研究人员检验了魔方任何可能的混乱状态(确切数字为43,252,003,274,489,856,000 约合4.3×1019)。美国俄亥俄州肯特州立大学数学家莫雷-戴维德森教授也是研究人员之一,他表示,“我们现在可以肯定,这个 ‘上帝之数’就是20。对于我来说,我也回到了原地。魔方伴随着我成长,这也是我为什么深入研究这个数学问题的原因。这个谜团引起了人们的广泛关注,它也许是人类历史上最受欢迎的谜语了。”科学家们的初步研究成果发表于在线网站上,但戴维德森表示,他们准备将研究成果提交给杂志正式发表。

程序员托马斯-罗基花了15年的时间,致力于寻找这个谜团的答案。据罗基介绍,研究团队所采用的算法可以在1秒钟内尝试10亿种可能,此前的计算机算法1秒钟内只能处理4000种可能。

为了让问题简单化,研究团队采用了一种所谓“群论”的数学技术。他们首先将魔方所有可能的起始状态集分成22亿个集合,每个集合包含了195亿个可能的状态。集合的分配原则是这些可能的状态是如何应对一组10个可能的还原步骤。再通过魔方不同的对称性,这种分组技术使得研究团队将集合数减少到 5600万个。

研究人员所采用的算法可以快速将这些还原步骤与恰当的起始点匹配起来,从而实现在20秒内处理一个集合中的195亿种可能。对于普通的家用电脑来说,以这样的速度完成整个处理任务需要大约35年时间。

2007年,《每日电讯报》曾经报道称,任意组合的魔方均可在26步内还原。当然,还有其他的报道称已证明出更少的还原步骤。魔方由匈牙利埃尔诺-鲁比克教授于1974年所发明,曾经是世界上最畅销的智力玩具。



来源:新浪科技

短网址: 版权所有,任何形式转载需本站授权许可。 严禁建立镜像网站.



【诚征荣誉会员】溪流能够汇成大海,小善可以成就大爱。我们向全球华人诚意征集万名荣誉会员:每位荣誉会员每年只需支付一份订阅费用,成为《betway必威体育官网 》网站的荣誉会员,就可以助力我们突破审查与封锁,向至少10000位betway必威体育官网 大陆同胞奉上独立真实的关键资讯,在危难时刻向他们发出预警,救他们于大瘟疫与其它社会危难之中。
荣誉会员

看完这篇文章您觉得

评论



加入betway必威体育官网
会员
donate

betway必威体育官网 版权所有 Copyright © 2001 - Kanzhongguo.com All Rights Reserved.

blank
x
我们和我们的合作伙伴在我们的网站上使用Cookie等技术来个性化内容和广告并分析我们的流量。点击下方同意在网络上使用此技术。您要使用我们网站服务就需要接受此条款。 详细隐私条款. 同意