最远态小于26步之论文《Twenty-Six Moves Suffice for Rubik's Cube》摘录

noski

Twenty-Six Moves Suffice for Rubik’s Cube
这是美国东北大学计算机科学学院的Daniel Kunkle和Gene Cooperman合写的一篇论文，用计算机验证了在26步之内可以还原三阶魔方的任何状态。
基本思路是用两阶段搜索，穷举出第一阶段小于13步，第二阶段小于16步，然后又对各阶段最远的状态分析了一下，得出13+16-3=26的结论。


Note that in all cases, we consider a move to be any quarter or half turn of a face of the cube, also known as the face-turn metric. We do not consider the alternative quarter-turn metric, which defines a half-turn to be two moves.
文中，作者把180步旋转看成了一步。

a new fast multiplication (requiring less than 100 nanoseconds) of either a symmetrized coset or a symmetrized group element by a generator (see Sections 3, 4.1 and 5 for definitions);
使用了单次运算时间在100ns内的快速乘法，这样每秒可以算10M次，每次乘法可以生成一个新状态。记得有人说过PIII计算机每秒可算多少多少次，和这个不一样的。

One approach to finding bounds on solutions to Rubik’s cube would be to produce the entire Cayley graph for the corresponding group. Cooperman, Finkelstein and Sarawagi used this method to show that 11 moves suffice for Rubik’s 2x2x2 cube [1].
一个方法是画出魔方所有状态的凯利图（纵坐标是代，横坐标是状态，大概像是子孙关系图），1990年那三个人用这个方法证明了二阶魔方的最远步数为11。（90年这篇论文我下到了，还没看，名字是Applications of Cayley graphs）

In 1992, this algorithm was improved by Kociemba [3] to use a subgroup chain of length two. In 1995, Reid [6] proved the worst case for the two steps was 12 and 18, for a total upper bound of 30. Further analysis showed that the worst case never occurs, and so a bound of 29 was shown. This bound was further refined by Radu [5] in 2006 to 27, which was the best upper bound before this work.
这里简要说了计算最小步数上限的进展，运用两阶段搜索法，1995年算出是12+18=30步，后来验证了某些状态不可能出现，就成了29步，2006年被减到27步，而07年这篇论文把上限减小到26步。

The group of Rubik’s cube is decomposed into a chain of length two, using the square subgroup (the subgroup generated by using only half-turns of the faces) as the intermediate subgroup. The square subgroup has only 663,552 elements, and there are approximately 6.5e13 cosets in Rubik’s group.
180度状态集（Square Subgroup），我就先这么叫吧，就是只允许每个面做180度转动得到的所有状态。这些状态正是二阶段搜索算法的中转站。180度状态集共有663,552个状态。这样就把魔方总状态分成了663552组，每组约6.5e13个状态。

Because of the small size of the square subgroup, only 15,752 after reduction by symmetries, these computations are negligible when compared to the corresponding computations for the cosets.
First, we constructed the Cayley graph of the square subgroup by breadth-first search, using the square generators. This computations took only seconds, even using a simple implementation on a single computer. Then, we found the optimal solution for all elements of the square subgroup, where we allowed any of the 18 generators to be used. This was done using a bidirectional search for each of the subgroup elements, using a day of CPU time.
We chose to use bidirectional search for this case, which proceeds in two phases. First, we performed a forward search to depth 7 using all of the generators. Then, we performed one backward search for each of the 15,752 elements of the square subgroup. These backwards searches required anywhere from milliseconds to a few hours in the worst case. Overall, this optimization took less than one day, requiring no parallelization.
180度状态集比较小，消同态之后只剩下15752个状态。限定只允许180度转动时，算出这个状态集的最远步数为15，用普通计算机花了几秒时间。允许所有转动时，算出其最远步数为13，用普通计算机算了一整天。

For Rubik’s cube, we desire a subgroup of 48 automorphisms that preserve the set of generators: the natural automorphisms of Rubik’s cube. Each automorphism can be identified with a symmetry of a geometric cube: either one of 24 rotations of the entire cube or a rotation followed by an inversion of the cube. An inversion of the cube maps each corner of the cube to the opposite corner.
这段可能很让人感兴趣，为了减少计算量，减少计算时间，引入了48 automorphisms，48自同构，48同态。。其中的24个是由于整体翻转得到的，再加上inversion的24个。至于是怎么倒转过来了还未弄清楚，不过感觉和g大师的似同非同。

The computation used the DataStar cluster at the San Diego Supercomputer Center (SDSC). We used 16 compute nodes in parallel, each with 8 CPUs and 16 GB of main memory. For outof- core storage, we used DataStar’s attached GPFS (IBM General Parallel File System). We used up to 7 terabytes of storage at any given time, as a buffer for newly generated states in the breadthfirst search. The final data structure, associating a 4-bit value with each symmetrized coset, used approximately 685 GB.
The computation required 63 hours, or over 8000 CPU hours. The fast multiplication algorithm allowed us to multiply a symmetrized coset by a generator at a rate between 5 and 10 million times per second, depending on the size of available CPU caches.
这里看看多大的计算量：16个计算机节点并行运算，每一个节点都有8个CPU、16G内存，动用了7TB的存储空间，算了63个小时，算完了。最后结果数据有685G。如果用单CPU的电脑，就要算上63x16x8=8064小时=336天，当然存储空间还得够用。

至于怎么就29-3了，没细研究。下面是两个阶段的结果图：



补充：该文章的参考文献7则给出了目前最远步数的下限，20步。
[7] Michael Reid. Superflip requires 20 face turns.
http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__Re__superflip_requires_20_face_turns.html
,1995.
所以，最远状态在20与26步之间，这样看来，以前传说的22~23步也许是事实。

[ 本帖最后由 noski 于 2008-11-25 00:43 编辑 ]

noski

论文原文在这个贴子2楼有下载：
http://bbs.mf8-china.com/viewthread.php?tid=5587&extra=page%3D1

看这里，在美国研究魔方还有国家科学基金会支持。。。
"This work was partially supported by the National Science Foundation under Grants ACIR-0342555 and CNS-06-19616."