魔方20步完成——群论.doc

《魔方20步完成——群论.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数学家破解"上帝之数"还原任意魔方仅需要20步来源：陈霜的日志尽管拥有43,252,003,274,489,856,000种不同的可能组合状态，但魔方都可以在20步内还原。北京时间2010年8月13日消息，据国外媒体报道，相信许多人都玩过魔方，但是此前没有人知道任意组合的魔方的最小还原步数究竟是多少。这一问题困扰了数学家长达三十多年，这个最小还原步数也被称为“上帝之数”。美国加利福尼亚州科学家近日利用计算机破解了这一谜团，研究人员证明任意组合的魔方均可以在20步之内还原，“上帝之数”正式定为20。这支研究团队位于美国加利福尼亚州帕洛阿尔托市。科学家们通过计算机计

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

3、维德森表示，他们准备将研究成果提交给杂志正式发表。程序员托马斯-罗基花了15年的时间，致力于寻找这个谜团的答案。据罗基介绍，研究团队所采用的算法可以在1秒钟内尝试10亿种可能，此前的计算机算法1秒钟内只能处理4000种可能。为了让问题简单化，研究团队采用了一种所谓“群论”的数学技术。他们首先将魔方所有可能的起始状态集分成22亿个集合，每个集合包含了195亿个可能的状态。集合的分配原则是这些可能的状态是如何应对一组10个可能的还原步骤。再通过魔方不同的对称性，这种分组技术使得研究团队将集合数减少到5600万个。研究人员所采用的算法可以快速将这些还原步骤与恰当的起始

4、点匹配起来，从而实现在20秒内处理一个集合中的195亿种可能。对于普通的家用电脑来说，以这样的速度完成整个处理任务需要大约35年时间。注1：上文中魔方特指不带图案的3x3x3魔方，其中1步指转动某个面一下（90度，180度，270度都算1步）注2：以上转自网络，以下原创，转载请注明出处。====================答疑部分====================1.什么是上帝之数？说到上帝之数，得从最少步还原说起。对于一个打乱的魔方，有人可能需要100步才能将它还原，有人可能需要60步，这取决于还原的步骤或算法。我们假设上帝还原魔方的时候总是用最少的

5、步骤还原，那这时候我们就想到一个问题，上帝算法在最坏情况下需要几步才能将魔方还原（要知道魔方状态好多好多，打得不够乱的可能上帝只需要5步就还原了，那打得稍微乱一些的，恶心一些的呢）？那么这个数字就被叫做上帝之数。2.既然所有魔方都可以在20步内还原，为什么上帝之数不可能是19或者更少呢？其实很简单，因为1995年的时候某大神就找到了一个坑爹状态（就和那堆精心构造的反例似的），通过计算机暴力搜索的办法发现，无论如何也不可能在19步内把它还原，或者说上帝还原这个坑爹状态也得20步，所以很显然上帝之数没法小于20了。3.那个什么谷歌计算机到底算了多少个状态？其实精确值

6、是55,882,296*19,508,428,800个状态，大约占三阶总状态数的1/40，所以其实算法上和暴力破解差得不太多，只不过，按照35CPU年算来，差不多每秒十亿个状态确实很高端霸气上档次（膜拜）。剩下39/40的状态果断用数学方法证明掉了，思路差不多是说，如果解决A类状态的步骤简单变形就能解决B类状态，那A和B类只要暴力求一个。4.每秒十亿个状态，平均求解一个状态只要1纳秒，如何做到的？额那主要是因为现在只关心上帝之数是否是20的问题，而不关心具体某个状态的最少步数是多少。一个不是很恰当的比喻是说，比如我找到个状态，它的最少步数是17步，那么很显然这个

7、状态边上3步以内的状态就可以直接pass掉了，反正这些个状态撑死也能在20步内搞定的，至于它们是不是能够在19步内搞定我们根本就不关心，反正它们就算能在18步内搞定，上帝之数也不会小于20（前面说过了），我就不用费那心思去算他们了。答疑部分待续。。。====================干货部分（随手写的，过两天试着详细化一下）====================1.首先将魔方状态群根据H()子群分解成2,217,093,120个右陪集，其中每个陪集中的元素个数为19,508,428,800。2.利用魔方的对称性（即对于状

8、态A及整体转动S，S^-