<<返回上一页

Rubik的任何尺寸的立方体现在都可以解决

发布时间:2019-02-06 02:07:00来源:未知点击:

雅各布·阿隆(图片来源:斯图尔特·克拉克)只有最硬核的拼图解决方案才能超越标准的3x3x3魔方,尝试更大的拼图,如右图所示现在已经开发出一种算法,可以解决任何大小的魔方它可能为人类试图处理这些棘手的野兽提供线索去年加利福尼亚州帕洛阿尔托的程序员托马斯·罗基奇(Tomas Rokicki)领导的团队表明,即使是最混乱的标准魔方魔方也可以在20次或更少的时间内解决,因此Rubik的立方体科学得到了提升这个壮举是一个大问题:这个数字被称为“上帝的数字”,假设全能者无法更快地解决它但是这个结果并没有揭示怪物立方体因此,麻省理工学院的计算机科学家Erik Demaine开始寻找一种通用算法,用于求解任意边长的立方体 - n个正方形新方法与Rokicki不同后者使用了一种“蛮力”方法,依靠从谷歌借来的计算机来检查所有43种可能的解决方案,但是Demaine说对大型立方体做同样的事情是不可能的 “你无法通过计算搜索来解决n的所有值,”他解释道相反,Demaine的团队开始研究Rubik的魔方爱好者通常用来快速解决难题的方法基本上,您尝试将单个方块或“cubie”移动到所需位置,同时尽可能保持立方体的其余部分不变因为在不打扰其他人的情况下移动单个立方体是不可能的,所以这种方法非常耗时,需要一些与n2成比例的移动德梅因和他的同事发现了一个捷径每个立方体都有一条特定的路径,可以将它放置在正确的位置他的算法寻找所有需要朝同一方向行进的立方体,然后同时移动它们 “我们发现,不是一次解决一个立方体,而是可以将该过程并行化并解决几个问题,”Demaine说对具有类似路径的立方体进行分组可以减少因子约为log n所需的移动次数这意味着边n的立方体所需的最大移动次数与n2 / log n成正比(arxiv.org/abs/1106.5736)在没有计算机的情况下找出单个立方体的路径并非易事,更不用说为整个立方体做这件事了,因此人类不太可能直接应用这个公式但Demaine认为它可以为立方体解算器提供一些技巧 “它给了我一些如何更快地解决这个问题的想法,”斯图尔特克拉克表示赞同,他是英国达勒姆大学的魔方爱好者和物理学家,拥有一个11x11x11的立方体克拉克表示,该算法背后的一些技术可能可用于加速其他问题,这些问题涉及搜索或排序具有与立方体类似的数学结构的数据集 “这需要进行一些调整,但有些地方你可以在正确的方向上进行调整”那么Rubik的立方体是否放弃了它的所有秘密不,Demaine说现在,他的算法只给出了求解任何给定大小的立方体所需的移动次数的近似值:它表明该值与n2 / log n成比例他的第一个任务是找出如何将其转换为给定尺寸的立方体的确切数字然而,即便如此,仍有一个难题 Demaine的当前算法只找到解决多维数据集的最有效方法,如果它处于该多维数据集的最扰乱状态但是他还想探索一种算法是否存在,以便找到较少扰乱的立方体所需的移动次数 “假设有人拿出一个解码的20x20x20魔方并进行五次移动 - 你能从这个混乱的状态中找出这五个动作是什么吗”他问道换句话说,你能用五步解决它吗他怀疑你不能,但尚未证明这一点 “我们不知道”对于Rokicki来说,下一个任务是找到一种算法,可以在尽可能少的动作中解决任何4x4x4立方体 “解决单个随机4x4x4位置可能需要更多的CPU时间,而不是我们用来证明3x3x3上帝的数字”更多关于这些主题: