科学家证明还原任意魔方最多需20步..docVIP

科学家15年证明还原任意魔方最多需20步  魔方由匈牙利埃尔诺-鲁比克教授于1974年所发明，曾经是世界上最畅销的智力玩具。据国外媒体报道，相信许多人都玩过魔方，但是此前没有人知道任意组合的魔方的最小还原步数究竟是多少。这一问题困扰了数学家长达三十多年，这个最小还原步数也被称为“上帝之数”。美国加利福尼亚州科学家（Morley Davidson, John Dethridge, Herbert Kociemba, 和Tomas Rokicki），近日利用计算机破解了这一谜团，他们证明任意组合的魔方均可以在20步之内还原，“上帝之数”正式定为20(Gods 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步内还原。当然，还有其他的报道称已证明出更少的还原步骤。 2008 年七月， 来自世界各地的很多最优秀的魔方玩家聚集在捷克共和国 (Czech Republic) 中部的帕尔杜比采 (Pardubice)， 参加魔方界的重要赛事： 捷克公开赛。 在这次比赛上， 荷兰玩家阿克斯迪杰克 (E. Akkersdijk) 创下了一个惊人的纪录： 只用 7.08 秒就复原一个颜色被彻底打乱的魔方。 无独有偶， 在这一年的八月， 人们在研究魔方背后的数学问题上也取得了重要进展。 在本文中， 我们就来介绍一下魔方以及它背后的数学问题。 一. 风靡世界的玩具1974 年春天， 匈牙利布达佩斯应用艺术学院 (Budapest College of Applied Arts) 的建筑学教授鲁比克 (E. Rubik) 萌生了一个有趣的念头， 他想设计一个教学工具来帮助学生直观地理解空间几何的各种转动。 经过思考， 他决定制作一个由一些小方块组成的， 各个面能随意转动的 3×3×3 的立方体。 这样的立方体可以很方便地演示各种空间转动。 随后魔方风靡全球， 其原因最大的魔力就在于其数目惊人的颜色组合。 一个魔方出厂时每个面各有一种颜色， 总共有六种颜色，（一般为 ：黄、白、绿、蓝、红、橙） 但这些颜色被打乱后， 所能形成的组合数却多达 4325 亿亿。 如果我们将这些组合中的每一种都做成一个魔方， 这些魔方排在一起， 可以从地球一直排到 250 光年外的遥远星空。 也就是说， 如果我们在这样一排魔方的一端点上一盏灯， 那灯光要在 250 年后才能照到另一端。 如果哪位勤勉的玩家想要尝试所有的组合， 哪怕他不吃、 不喝、 不睡， 每秒钟转出十种不同的组合， 也要花 1500 亿年的时间才能如愿 (作为比较， 我们的宇宙目前还不到 140 亿岁)。 与这样的组合数相比， 广告商们常用的 “成千上万”、 “数以亿计”、 “数以十亿计” 等平日里虚张声势、 忽悠顾客的形容词反倒变成了难得的谦虚。 我们可以很有把握地说， 假如不掌握诀窍地随意乱转， 一个人哪怕从宇宙大爆炸之初就开始玩魔方， 也几乎没有任何希望将一个色彩被打乱的魔方复原。 二. 魔方与 “上帝之数”魔方的玩家多了， 相互间的比赛自然是少不了的。 自 1981 年起， 魔