魔方吧·中文魔方俱乐部

标题: 中科大物理系陈希解决任意超高阶魔方的计算机求解问题 [打印本页]

作者: xh176233756 时间: 2012-5-3 00:12:48 标题: 中科大物理系陈希解决任意超高阶魔方的计算机求解问题

传送门：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秒还原，在中国科技大学超算中心的高性能并行机上也获得类似的运算结果。

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

作者: lietice 时间: 2012-5-3 05:50:18

“所以即便使用高性能计算机，上百阶魔方的还原也是不易的，其难度好比于从构成整个宇宙的所有基本粒子中找到一个指定的粒子。因此计算机求解必须设计好的算法。”

我觉得变化状态再多，只要有时间，解决100阶魔方不是问题。降价法能用吧？？难道他的算法是最少步？那样的话确实很牛。

作者: 咖啡味的茶 时间: 2012-5-3 07:01:02

我两年前写了一个复原程序...但是因为本人不会编程所以没有写出来。20阶手动复原过。哈哈哈哈哈
用的就是降阶法。
本人七阶魔方手动复原5分钟，假设一秒转动5步，一共复原大概1500步。两年前握用家里的计算机计算100万位Pi，用时20秒，每一位数字运用了0.00002。假设计算每一位数字的速度和转动一下魔方的计算一样，那么1500*0.00002=0.03秒输出答案。

作者: schuma 时间: 2012-5-3 07:27:58

降阶法等等的方法都是假设你会解三阶魔方的，或者有一些先验知识，比如会用交换子构造公式之类的。那篇论文用的是模拟退火算法。

单纯的使用模拟退火算法不需要对魔方的解法有任何了解，不需要知道怎么构造公式。在这种假设条件下，降阶法是不能用的。于是这个问题就变得非常难。

不过原文说"....因此直接使用原始的模拟退火法并不能求解该问题。陈希同学使用了几种技巧（分阶段还原、分簇还原、设计特殊的试探方法）并且动态改变能量函数的形式，从而能够跳出局部极小顺利达到能量最低态。" 所以论文的作者到头来还是借用了一些魔方里的先验知识来解决问题。从某种角度讲，这有点耍赖。不过对于一个本科毕业设计来说还是不错的。

作者: 祭司zhangcy 时间: 2012-5-3 08:17:51

倒不是最小步，但是是一种比较节省步骤的方法，最近我正在努力联系陈希，希望能和他交流一下。

作者: sokoban 时间: 2012-5-3 11:17:49

文章还是很有问题，解高阶早就有很好的算法，他的算法可以说有趣，但并不比原来的好。

文章透露出来的他是首次解决高阶魔方的计算机求解的观点是错误的，求解从来都不是问题，早就解决了。

[ 本帖最后由 sokoban 于 2012-5-3 11:20 编辑 ]

作者: sokoban 时间: 2012-5-3 11:33:47

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

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

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

作者: sokoban 时间: 2012-5-3 12:06:58

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

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.

作者: schuma 时间: 2012-5-3 12:31:53 标题: 回复 8# 的帖子

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

作者: 小明的马甲 时间: 2012-5-3 13:15:24 标题: 回复 9# 的帖子

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

作者: sokoban 时间: 2012-5-3 13:25:43 标题: 回复 9# 的帖子

这篇？

http://arxiv.org/abs/1106.5736

作者: 小明的马甲 时间: 2012-5-3 13:31:31 标题: 回复 11# 的帖子

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

作者: versionxp 时间: 2012-5-6 12:04:42

能还原不是亮点，计算最少步才是王道！

他的测试怎么都是7,101,5001,的奇数阶魔方？

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

作者: 邦邦 时间: 2012-9-20 20:45:52

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

作者: 武杰610206738 时间: 2012-9-30 15:32:57

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

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)