数学家破解上帝之术_还原魔方只用20步_副本.pdf

20 20 数学家破解上帝之术，还原魔方只用2200步 尽管拥有43,252,003,274,489,856,000种不同的可能组合状态，但魔 方都可以在20步内还原。 北京时间2010年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年时 间。 注1：上文中魔方特指不带图案的3x3x3魔方，其中1步指转动某个面 一下（90度，180度，270度都算1步） 注2：以上转自网络，以下原创，转载请注明出处。 ==================== 答 疑 部 分 ==================== 1. 什么是上帝之数？ 说到上帝之数，得从最少步还原说起。对于一个打乱的魔方，有人可 能需要100步才能将它还原，有人可能需要60步，这取决于还原的步 骤或算法。我们假设上帝还原魔方的时候总是用最少的步骤还原，那 这时候我们就想到一个问题，上帝算法在最坏情况下需要几步才能将 魔方还原（要知道魔方状态好多好多，打得不够乱的可能上帝只需要 5步就还原了，那打得稍微乱一些的，恶心一些的呢）？那么这个数字 就被叫做上帝之数。 2. 既然所有魔方都可以在20步内还原，为什么上帝之数不可能是19 或者更少呢？ 其实很简单，因为1995年的时候某大神就找到了一个坑爹状态（就 和那堆精心构造的反例似的），通过计算机暴力有哪些信誉好的足球投注网站的办法发现，无 论如何也不可能在19步内把它还原，或者说上帝还原这个坑爹状态也 得20步，所以很显然上帝之数没法小于20了。 3. 那个什么谷歌计算机到底算了多少个状态？ 其实精确值是 55,882,296*19,508,428,800 个状态，大约占三阶总 状态数的1/40，所以其实算法上和暴力破解差得不太多，只不过，按 照35CPU年算来，差不多每秒十亿个状态确实很高端霸气上档次（膜 拜）。剩下39/40的状态果断用数学方法证明掉了，思路差不多是说， 如果解决A类状态的步骤简单变形就能解决B类状态，那A和B类 只要暴力求一个。 4. 每秒十亿个状态，平均求解一个状态只要1纳秒，如何做到的？ 额那主要是因为现在只关心上帝之数是否是20的问题，而不关心具体 某个状态的最少步数是多少。一个不是很恰当的比喻是说，比如我找 到个状态，它