科学家15年证明还原任意魔方最多需20步-世界中文数学第一网,数...

科学家15年证明还原任意魔方最多需20步
2010年8月17日 19:59  新闻来源:新浪科技  阅读次数: 688    默认字体 9pt 10pt 11pt 12pt 13pt 14pt 15pt 16pt 17pt 18pt 20pt 25pt
据国外媒体报道，相信许多人都玩过魔方，但是此前没有人知道任意组合的魔方的最小还原步数究竟是多少。这一问题困扰了数学家长达三十多年，这个最小还原步数也被称为“上帝之数”。美国加利福尼亚州科学家（Morley Davidson,John Dethridge, Herbert Kociemba, 和Tomas Rokicki），近日利用计算机破解了这一谜团，他们证明任意组合的魔方均可以在20步之内还原，“上帝之数”正式定为20(God's Number is 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年所发明，曾经是世界上最畅销的智力玩具。
相关内容：A History of God's Number
By 1980, a lower bound of 18 had been established for God's Number by analyzing the number of effectively distinct move sequences of 17 or fewer moves, and finding that there were fewer such sequences than Cube positions. The first upper bound was probably around 80 or so from the algorithm in one of the early solution booklets. This table summarizes the subsequent results.
Date
Lower bound
Upper bound
Gap
Notes and Links
July, 1981
18
52
34
Morwen Thistlethwaite proves52 moves suffice.
April, 1992
18
42
24
Hans Kloosterman improves this to42 moves.
May, 1992
18
39
21
Michael Reid shows39 moves is always sufficient.
May, 1992
18
37
19
Dik Winter lowers this to37 moves just one day later!
January, 1995
18
29
11
Michael Reid cuts the upper bound to29 moves by analyzingKociemba's two-phase algorithm.
January, 1995
20
29
9
Michael Reid proves that the ''superflip'' position (corners correct, edges placed but flipped) requires20 moves.
December, 2005
20
28
8
Silviu Radu shows that28 moves is always enough.
April, 2006
20
27
7
Silviu Radu improves his bound to27 moves.
May, 2007
20
26
6
Dan Kunkle and Gene Cooperman prove26 moves suffice.
March, 2008
20
25
5
Tomas Rokicki cuts the upper bound to25 moves.
April, 2008
20
23
3
Tomas Rokicki and John Welborn reduce it to only23 moves.
August, 2008
20
22
2
Tomas Rokicki and John Welborn continue down to22 moves.
July, 2010
20
20
0
Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki prove that God's Number for the Cube is exactly 20.