新闻来源:《Computer Physics Communications》（183 (2012) 1658）。
中国科技大学物理系大四学生陈希同学在解决“高阶魔方的计算机解”问题时设计出一种改进后的模拟退火算法，可以高效地将任意阶魔方还原。这项研究刊于近期出版的《Computer Physics Communications》（183 (2012) 1658）。

在此之前，关于还原魔方问题的研究集中在低阶上（3至11阶），高阶与超高阶魔方少有人问津。因为魔方的状态数随其阶数急剧增加，其中5阶魔方就有10^75以上的状态数，所以即便使用高性能计算机，上百阶魔方的还原也是不易的，其难度好比于从构成整个宇宙的所有基本粒子中找到一个指定的粒子。因此计算机求解必须设计好的算法。

“高阶魔方的计算机解”问题是物理系丁泽军教授在对大三本科同学讲授《计算物理》课程时布置的一道课题研究题目，其目的是应用该课程讲授的知识解决一个有挑战性的未解决问题。“模拟退火算法”是一种常用的基于马可夫链蒙特卡罗方法的算法，用于各种科学和工程问题中的优化解。其原理是在一个大的相空间内用概率指针反复搜寻命题的最优解方向，探索步都倾向于选择一个使得能量降低的状态，从而避免在庞大的高能量状态集合中做无用搜索。当设计出一个合适的魔方能量态函数，使得魔方的能量随着它的混乱程度增加，则模拟退火法寻找到的能量最低点就是魔方的被还原状态，连接初始状态和还原状态的所有试探步，就是还原魔方的步骤。

但是，魔方问题有别于其它各种优化问题之处是由于魔方的态函数中密布着各种局部极小值，且缺乏长程单调指向性，因此通常的试探法很容易循环陷入局部极小，也很难找到正确的方向，因此直接使用原始的模拟退火法并不能求解该问题。陈希同学使用了几种技巧（分阶段还原、分簇还原、设计特殊的试探方法）并且动态改变能量函数的形式，从而能够跳出局部极小顺利达到能量最低态。

采用这样改进的模拟退火算法，串行程序在笔记本电脑上运行结果为：7阶魔方可在3秒左右还原，101阶魔方可用997秒还原；并行程序在上海超算中心“魔方”高性能并行机（Magiccube）上的运行结果为：5001阶魔方可用1877秒还原，在中国科技大学超算中心的高性能并行机上也获得类似的运算结果。

该研究的意义不仅是提供了任意高阶魔方的高效还原方法，拓展了模拟退火法的应用范围，更为重要的是对模拟退火法做的改进思想或可对其它科学工程问题中的最优解法提供借鉴。