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

数学家破解上帝之术 还原魔方只用数学家破解上帝之术 还原魔方只用 20202020 步步 尽管拥有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的问题 而不关心具体 某个状态的最少步数是多少 一个不是很恰当的比喻是说 比如我找 到个状态 它的最少步数是17步 那么很显然这个状态边上3步以内 的状态就可以直接 pass 掉了 反正这些个状态撑死也能在20步内搞 定的 至于它们是不是能够在19步内搞定我们根本就不关心 反正它 们就算能在18步内搞定 上帝之数也不会小于20 前面说过了 我 就不用费那心思去算他们了 答疑部分待续 干货部分 随手写的 过两天试着 详细化一下 1 首先将魔方状态群根据 H 子群分解成 2 217 093 120 个 右 陪 集 其 中 每 个 陪 集 中 的 元 素 个 数 为 19 508 428 800 2 利用魔方的对称性 即对于状态 A 及整体转动 S S 1 A S 和 A 同解 将陪集的个数降为 55 882 296 即约为总量的1 40 3 暴力求解每个陪集 其中第三条的算法用到一些 trick 对于给定陪集 R H r 使用 IDA 算法搜索 R 到 H 的解 则对 于每个解 m 有 r m h 其中h属于 H 于是有 h r m 1 其中 h h 1 注意到 h 属于 H 子群 所以 h 也属于 H 于是 h r 属于 H r R 因此 映射 H H r f h h r 是双射 即选取 R 中的任何一个状态t 如果 t 可以在 N 步内访问 H 中的所有 状态 则说明 R 中的所有状态可以在 N 步内还原 实际暴力求解每个陪集的算法为 a 首先取 N 15及 R 中的某一个元素进行进行 IDA 即标记出可以 在15步内访问到的 H 中的所有状态 结果保存为 bitvector 的形式 以节省内存 b 直接对这些状态在下转动1步 使得转动 后的状态依然属于 H 将新访问到的状态与15步状态合并 记为16 步内可以访问到的状态 事实上16步内可以访问的状态会比标记出来 的多 但 IDA 的性能远低于直接转动特定状态的性能 为了证明上 帝之数为20步不需要那么做 c 重复上述步骤 b 四次 即得到20步内可以访问到的 H 中的状态的 一部分 受限于 IDA 但也足够了 d 此时 H 基本已经遍历完毕 平均还会剩下几百个状态没有遍历到 将这些状态所对应的 R 中的状态用二阶段算法搞定之 即证明了整个 陪集中的那么多状态都可以在20步内完成 对于大部分陪集 上述算法性能很高 但对于某些恶心的陪集 很有 可能 c 完成后留下了海量没有遍历到的状态 这时候需要改进上述算 法 即增加一部分16步的 IDA 过程 计算时间上 计算完 a 平均需要3 1秒 计算完 c 平均需要17 4秒 计算完 d 平均20秒不到 即20秒搞定一个陪集 总共55 882 296个 陪集共需要35CPU 年 注意到各陪集之间相互独立 上述过程可对不 同陪集进行分布式并行计算 最后汇总结果 据说利用魔方对称性将2 217 093 120个陪集降到55 882 296个并不 那么容易 因为 H 群只是 D4h 对称群 直接可利用的对称性只有16 种 所以采用了一种 set cover 的技巧 即在 H 群里找个对称性更强 的子群 即 Q Oh 的对称性 然后将 Q r 的个数利用对称性降为原来的1 48左右 最后从 H r 中精心寻找 一些陪集 完全覆盖所有的 Q r 这么一来 只要搞定所有这些能够 覆盖 Q 们的 H 就能证明所有的 Q 都能在20步内搞定 即证明了所 有的状态 但是由于 H 比 Q 大太多 这个覆盖