中科大物理系陈希解决任意超高阶魔方的计算机求解问题

xh176233756

传送门：http://www.sciencedirect.com/science/article/pii/S0010465512001087

求鉴定。

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

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

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

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

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

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

武杰610206738

超高阶魔方目前应该没有什么实际意义吧？？
估计就能测试一下超级计算机的效能

邦邦

用计算机解魔方具有什么意义呢

versionxp

能还原不是亮点，计算最少步才是王道！
他的测试怎么都是7,101,5001,的奇数阶魔方？

[ 本帖最后由 versionxp 于 2012-5-6 12:07 编辑 ]

小明的马甲

1楼那篇。。一眼就看到了中心三循环和棱块对换公式。。

sokoban

这篇？

http://arxiv.org/abs/1106.5736

小明的马甲

据说论文用了各种公式，当时我被雷到了。。。

schuma

去年就有个论文(Erik Demaine et al)，是研究 n*n*n 魔方当n趋于无穷时，上帝之数（最小步数）的渐进性质。

sokoban

这就是引自原文的一个荒谬的说法：

However, up to this date, all the studies are limited to low-order cubes, mostly from 3 to 11. The solutions for high-order cubes and even extra-high-order cubes have little been attempted, neither its theory nor a feasible computer solution.

sokoban

原帖由 schuma 于 2012-5-3 07:27 发表
不过对于一个本科毕业设计来说还是不错的。

对于本科生是很不错了。但是还挂了他导师的名字，他导师就要为这文章负责。

文章的简介中充满错误的观点，对高阶魔方的求解显得很无知。这样的水平较低的文章还高调宣传就贻笑大方了。