能改善你生活的魔方解法

对于东北大学的计算机科学家吉恩·库珀曼（Gene Cooperman）和丹尼尔·坎克尔（Daniel Kunkle）来说，魔方不是一个游戏——它是终极的组合难题，他们的解决方案有望改善我们所有人的生活。当一个魔方速解冠军解决魔方时，他只是解决了魔方众多可能的打乱状态中的一个版本。但是，解决任何可能的魔方最快的方法是什么？

坎克尔指出，答案并不容易：魔方有43万亿种可能的状态，评估所有这些状态是一项巨大的任务。其中一项计算耗费了8000个中央处理器小时（相当于运行家用电脑整整一年），并产生了120太字节的数据。

“基本的攻击思路是将它分解成子问题，然后证明这些子问题的最优解，”坎克尔说。他和库珀曼使用超级计算机和数学群论解决了魔方所有可能的状态，只需26步。诚然，这并不比之前的27步记录有显著的改进。但库珀曼和坎克尔表示，他们搜索和枚举魔方状态的特定方法可以应用于更大的问题。他们用来探索通往魔方解决方案的无数路径的方法，也可以用来识别最佳航班时刻表或最快的电话路由方式。