魔方吧·中文魔方俱乐部

标题: 科学家证明魔方最小还原步数为20步 [打印本页]

作者: joey0513 时间: 2010-8-13 12:47: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年所发明，曾经是世界上最畅销的智力玩具。
http://scitech.people.com.cn/GB/12428897.html

作者: ksac2015756 时间: 2010-8-13 12:48:35

呃，最近说这个的怎么这么多啊

作者: kattokid 时间: 2010-8-13 12:57:37

如果我没记错的话这是第五帖介绍最小步为20 的帖子了

作者: robester 时间: 2010-8-13 13:00:10

第四贴吧，
字数补丁。

作者: 五叶草 时间: 2010-8-13 13:13:09

原帖由 robester 于 2010-8-13 13:00 发表
第四贴吧，
字数补丁。

不过这是我看到的第1帖,一定要顶上!

作者: Da_Silva 时间: 2010-8-13 14:45:23

好久以前就知道是20了

作者: 三硝基甲苯 时间: 2010-8-13 19:29:13

我只是羡慕那台电脑..这样玩游戏就不卡了...

开玩笑。

终于看到像过程了..

作者: 761316975 时间: 2010-8-14 15:43:18

早在新闻上看到了

作者: 42752277 时间: 2010-8-14 15:44:54

我没记错的话好像发过了……

作者: 香蕉 时间: 2010-8-14 15:46:31

这个昨天才看过看过了

作者: E.T. 时间: 2010-8-16 13:59:20

第一次看到这个帖时，不是怎么相信。看到网上的媒体报道后，现在信了。

作者: yy1993628 时间: 2010-9-4 21:05:59

真的吗那好刷皮哦~！

作者: lanyong 时间: 2010-9-13 16:18:49 标题: 证明最少还原步数一思路

9月8日
关于魔方
前两天玩了下。
复原了一层。
后来研究了下。

有材料表明任意组合的3阶魔方可以在20步内复原。

我想到了一个采用逆向思维的方法的证明思路。

任意组合的3阶魔方可以在20步内复原的等价命题应该是：
3阶魔方可以在20步内形成所有的组合。

3阶魔方的组合总数已经被很多人用不同的方法进行了确认.我这里把它表示为Max.

那么我们要证明的是我们用20步，可以把这Max种可能组合方式完全表示出来。

f(0)=1;
f(1)=?

f(20)=?

Max=f(0)+f(1)+...+f(20);（p.s:在每步都不会重复（,即不产生相同的组合）的条件下）

括号中的0，1，2表示步数。

p.s:问题的关键这20步是否会产生相同的组合？如果有是否有办法可以计算出是多少。

这样上面的公式应该修正为:

Max=f(0)+f(1)+...+f(20)-n;
n为存在的相同组合。

p.s2:一定会有相同的组合，关键怎么样能判断出着20步，每步都能产生不重复的组合。

作者: liugexxxxx 时间: 2010-10-8 13:36:52

谁能试试到底要几步？？

作者: 不停的转 时间: 2010-10-16 21:39:34

27 25 20 20 还会再变吗？？

作者: tywzholmes 时间: 2010-10-18 12:28:38

留给计算机吧超出人脑极限了

作者: xiaoshudian 时间: 2010-10-18 12:41:26

不过这是我看到的第1帖,一定要顶上!

作者: 黑白子 时间: 2016-1-26 15:32:11

这个最少步是把旋转180度也算作一步。

作者: pizza49 时间: 2016-3-19 10:29:15

请问有没有纯数学的方法证明20是下确界？

作者: 清欢 时间: 2016-7-23 21:46:02

这帖子算是普及知识的吧

作者: 1644 时间: 2018-5-2 20:27:48

发个万能公式呗！各位哥哥姐姐们

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