魔方问题新进展: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翻译,原文地址
做人要厚道,转贴请注明出处

18 条评论

  • swj

    Kunkle和Cooperman将数据巧妙地进行了处理,使得数据的排列正好与计算机读取的顺序相符

    这个很神奇地嘛

    整个思路看懂了 还不错 很有启发意义的

  • ulitmate

    跟老妈讲
    我也有如此志向
    然后说服她买一台PS3
    改造成 超级计算机
    可行吗?

    回复:想改造成超级计算机的话,光ps3是不够的,你还需要wii、xbox、gba和psp

  • victorking1

    这个貌似人来做的话就不大可能的,还是机器好
    对了,今天什么时候出来看《哈》,记到哈,现在过了12点
    记到打电话

  • Voldemort_Stupiddddddddd

    建议还是google提出的那个“全球计算机合作计算计划”(我自己编的)好,说什么安装客户端,然后你的电脑在空闲的时候google会发来一个大问题的极小的一个部分,让你用屏保时间来算一下,这要比超级计算机实惠多了

    回复:前几年我曾参加过seti@home,很有意思

  • yiyi

    超级计算机?
    看那chip的题目,当时还真有这种想法.
    不过,第2个想法是用并行运算;…[stun]

    回复:超级计算机本身就应该使用了并行运算

  • 纳米

    那26步是什么

    回复:步骤本身并无规律。不过youtube上曾有一个解魔方教程,自己去找吧

  • Ben.MQ

    impressive.

  • Eagle_Fantasy

    恩,果然牛

  • yiyi

    我的意思是:在没有超级计算机的情况下,
    用VC写个并行,在机房的N台PC上运算…

  • yiyi

    seti@home? 很久以前看IBM的资料介绍过的,也下了个. 那个屏保蛮PL的, 可惜是以CPU为代价di…
    IBM似乎还有个计算什么分子的…运行了1个月,最终以导致系统效率降低为由卸了~

    回复:给你颁发一个评论最积极奖

  • Andriy

      掌上电影宝.

      你去发明个这家伙造福人类把

  • dv/dt

    人来做的话也有公式的,靠着公式就可以解开任何魔方,当然没人去在意布数问题。

  • computer迷

    用量子计算机穷举吧。

  • IDK

    很想看看26步的公式(魔方轉動的那種)…好讓自己也”神”一下吧!!

  • L

    好像现在已经推进到21步了
    (有人推测是20步)

  • ximi

    推荐一个论坛
    bbs.mf8.com.cn

  • cervelo jersey

    ps3wii、xbox、gba和psp 这些一起就能改造超级计算机吗?

发表评论