魔方吧·中文魔方俱乐部

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

科学家证明魔方最小还原步数为20步 [复制链接]

Rank: 3Rank: 3

积分
992
帖子
676
精华
1
UID
74920
性别
保密
发表于 2010-8-13 12:47: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年所发明,曾经是世界上最畅销的智力玩具。
http://scitech.people.com.cn/GB/12428897.html

Rank: 2

积分
474
帖子
423
精华
0
UID
32106
性别
保密

爱心大使 四年元老

发表于 2010-8-13 12:48:35 |显示全部楼层
呃,最近说这个的怎么这么多啊
已有 1 人评分经验 收起 理由
谢老师 + 1 很不幸,现在才看到第四贴,那前三贴呢?

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

封魔了,只聊天

使用道具 举报

铜魔

冷血王

Rank: 8Rank: 8

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

四年元老

发表于 2010-8-13 12:57:37 |显示全部楼层
如果我没记错的话 这是第五帖介绍最小步为20 的帖子了
魔方—无处不在
    魔方—无可取代


使用道具 举报

红魔

电工九段

Rank: 4

积分
2899
帖子
2458
精华
1
UID
24502
性别
发表于 2010-8-13 13:00:10 |显示全部楼层
第四贴吧,
字数补丁。

使用道具 举报

红魔

Rui

Rank: 4

积分
1649
帖子
1623
精华
0
UID
110911
性别
发表于 2010-8-13 13:13:09 |显示全部楼层
原帖由 robester 于 2010-8-13 13:00 发表
第四贴吧,
字数补丁。
不过这是我看到的第1帖,一定要顶上!
当真理还在穿鞋,谣言已走遍了世界的每一个角落。

使用道具 举报

积分
2
帖子
2
精华
0
UID
1270224
性别
发表于 2010-8-13 14:45:23 |显示全部楼层
好久以前就知道是20了
又有一个白色的魔友诞生了!

使用道具 举报

Rank: 4

积分
1179
帖子
1061
精华
0
UID
1250802
性别
保密

两年元老

发表于 2010-8-13 19:29:13 |显示全部楼层
我只是羡慕那台电脑..这样玩游戏就不卡了...


开玩笑。

终于看到像过程了..

使用道具 举报

Rank: 1

积分
190
帖子
184
精华
0
UID
1258358
性别
保密
发表于 2010-8-14 15:43:18 |显示全部楼层
早在新闻上看到了

使用道具 举报

透魔

阿V

Rank: 6Rank: 6

积分
7732
帖子
6459
精华
2
UID
1253084
WCA ID
2010ZHAN17

论坛建设奖 爱心大使 十年元老 十二年元老

发表于 2010-8-14 15:44:54 |显示全部楼层
我没记错的话好像发过了……
静坐常思己过,闲谈莫论人非

使用道具 举报

Rank: 2

积分
358
帖子
307
精华
0
UID
1257620
性别
发表于 2010-8-14 15:46:31 |显示全部楼层
这个昨天才看过看过了

使用道具 举报

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

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

GMT+8, 2024-3-29 06:23

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部