魔方问题新进展:26步足以破解任何魔方

    最近,波士顿Northeastern大学的计算机科学家Daniel Kunkle证明了任何一个魔方可以在26步以内解开。这个结果打破了以往所有的记录。在解魔方的处理过程中,他构造了一些非常具有启发性的算法,这篇文章将简单地介绍一下这些算法。
    一个魔方大约有4.3 x 10^19种可能的初始状态,再牛的机器也不可能搜索完所有的可能。因此Kunkle和他的指导员Gene Cooperman想出了一些对魔方状态进行分类筛选的策略。
    Kunkle和Cooperman首先运用了一个小技巧将问题进行简化。如果魔方的每个面全是一种颜色,我们就认为魔方被解开,不管哪一面是哪一种颜色。换句话说,相互之间可以通过颜色置换得到的初始状态都是等价的。这样,“本质不同”的初始状态就减少到10^18种。
    接下来,他们开始观察一类更简单的问题:如果只允许180度转动(half-turn),有多少状态可以被解决。在10^18种状态中,只有大约15000种状态可以仅用180度旋转来破解。对于普通计算机来说,这个数目也不大,只需要不到一天的时间就可以搜索出解开所有15000多个魔方各自需要的最少步数。他们发现,这类初始状态中任何一个都可以在13步以内解决。
    然后他们需要做的就是找出,需要多少步才能把任意一种状态转化为这15000种特殊状态中的一个。为了完成这一工作,首先他们把所有的初始状态划分为若干个等价类,每个等价类里的状态都可以仅用180度转动互相得到。这样,同一个等价类中如果任一状态可以变换为其中一种特殊状态,同样的转动步骤也可以使该等价类的其它所有状态都变成特殊状态。最后他们找到了1.4 x 10^12个不同的等价类,需要解决的状态数由最初的4.3×10^19减少到1.4×10^12。但无论如何,10^12仍然是一个恐怖的数字。
    现在他们用了一台超级计算机来完成这个工作,并且使用了一些很有技巧性的决策来加速搜索过程。计算机需要耗费大量的时间读取硬盘上的数据,为了加快速度,Kunkle和Cooperman将数据巧妙地进行了处理,使得数据的排列正好与计算机读取的顺序相符,这样就节省了搜索硬盘的时间。
    “这种方法可以应用在任何一个组合问题上”,Kunkle说。他提到了西洋跳棋、国际象棋、航班安排和蛋白质摺叠等一系列问题。一种类似的组合学方法最近被用于寻找西洋跳棋的最优策略中。
    63小时的计算后,超级计算机得到的答案是,任何一种状态都能在16步以内转化为15000种特殊状态。而这些特殊状态又只需要13步达到最终状态,因此这种方法最终得到的结论是:29步以内可以解决任何一个魔方问题。
    但这个数字还不足以创造出新的记录,去年瑞典就曾经得到过27步内解决魔方问题的结论。Kunkle和Cooperman意识到,要想打破这个记录,他们还需要削减3步才行。
    应用他们现有的算法,只有8×10^7个状态集合还不能做到26步以内出解。再次对这些相对较少的状态进行搜索,最终他们找到了26步以内解决所有魔方的方法。
    7月29日他们在ISSAC(International Symposium on Symbolic and Algebraic Computation,国际符号和代数计算会议)上公布了这一结果。
    现在Kunkle和Cooperman希望把最大步骤数减少到25。他们认为他们可以对所有需要26步的状态进行暴力搜索来寻找更优的方案。
    虽然他们已经获得了很大的成功,但这一结果很可能还有改进的空间。许多学者认为20步以内足以解决任何魔方,但现在没有人能够证明。

Matrix67翻译,原文地址
做人要厚道,转贴请注明出处