Solving extra-high-order Rubik始s Cube problem by a dynamic simulated annealing
- 作者：Xi Chen ; Z.J. Ding ; zjding@ustc.edu.cn
- 关键词：Rubik始s Cube ; Monte Carlo ; Parallel
- 刊名：Computer Physics Communications
- 出版年：2012
- 期刊代码：30_00104655
- 类别：cp
- 出版时间：August, 2012
- 卷：183
- 期：8
- 页码：1658-1663
- 文件大小：584 K
摘要
A Monte Carlo algorithm, dynamic simulated annealing, is developed to solve Rubik始s Cube problem at any extra-high order with considerable efficiency. By designing appropriate energy function, cooling schedule and neighborhood search algorithm, a sequence of moves can select a path to decrease quickly the degree of disorder of a cube and jump out local energy minima in a simple but effective way. Different from the static simulated annealing method that adjusting the temperature parameter in Boltzmann function, we use a dynamic procedure by altering energy function expression instead. In addition, a solution of low-order cube is devised to be used for high efficient parallel programming for high-order cubes. An extra-high-order cube can then be solved in a relatively short time, which is merely proportional to the square of order. Example calculations cost 996.6 s for a 101-order on a PC, and 1877 s for a 5001-order using parallel program on a supercomputer with 8 nodes. The principle behind this feasible solution of Rubik始s Cube at any high order, like the methods of partial stages, the way to design the proper energy function, the means to find a neighborhood search that matches the energy function, may be useful to other global optimization problems which avoiding tremendous local minima in energy landscape is chief task.