“上帝不能做得更快”:魔方魔方解开了

2017-11-14 04:03:03

雅各布·阿隆(Jacob Aron)花了15年的时间才达到这一点,但现在很清楚,魔方的每一个可能的混乱安排都可以在最多20次移动中解决 - 而你甚至不需要取下贴纸根据一个团队的说法,他将谷歌的计算能力与一些聪明的数学见解相结合,以检查多维数据集可能占据的所有43个可能混乱的位置他们的壮举解决了魔方所呈现的最大难题来自加利福尼亚州帕洛阿尔托的程序员Tomas Rokicki说:“主要的突破是找到一种方法,以如此快的速度同时解决如此多的职位,”他花了15年的时间寻找最少的动作保证解决Rubik立方体的任何配置这个数字被称为“上帝的数字”,假设即使全能者也无法更快地解决这个难题新科学家在2008年报道说,Rokicki将God's Number的数值减少到了22,但很明显,进一步降低它需要一些聪明的捷径为了进一步简化问题,Rokicki和他的团队现在使用了数学分支中称为群论的技术首先,根据这些配置如何响应一组10个可能的移动,他们将所有可能的起始配置的集合划分为22亿集,每个集包含195亿个配置通过利用多维数据集的各种对称性,这种分组允许团队将集合数量减少到5600万例如,将翻动的立方体颠倒过来并不会使其难以解决,因此可以忽略这些等效位置但是,仍然需要检查大量的启动配置,因此团队还开发了一种加速此过程的算法先前的方法通过尝试一组起始移动每秒解决大约4000个立方体,然后确定结果位置是否更接近解决方案如果没有,算法会抛弃这些移动并重新开始 Rokicki的关键洞察力是要意识到这些死胡同的行动实际上是不同起始位置的解决方案,这导致他的算法可以尝试每秒10亿个立方体你可以这样想他的解决方案想象一下,在一个陌生的城市拜访一位朋友他们给你指示何时向左或向右转,但忽略了包括一个起点如果您按照随机点的方向进行操作,则您不太可能到达目的地,但将它们与正确的起点匹配肯定会让您到达目的地同样,团队的算法可以快速匹配移动到正确的起点,使他们能够在20秒内解决每组195亿即使在这样的速度下,在普通计算机上完成整个任务大约需要35年因此,该团队的解决方案依赖于另一条捷径:加州山景城Google工程师John Dethridge能够利用其雇主庞大的计算帝国在几周内解决问题我们已经知道15年来,立方体的一些配置只需要20个动作来解决 - 许多数学家怀疑没有更多需要该团队的详尽搜索证明了他们的正确性“像这样的研究表明,纯粹的数学经常可以用来使计算难题变得更加可行,”曼彻斯特大学的数学家Mark Kambites说,他没有参与团队的工作 “魔方是计算群理论方法的一个有趣的测试案例”这项工作尚未经过同行评审,但Rokicki指出它是早期作品的延伸,发表于数学智能,减少了神的数量 22.关于这些主题的更多信息: