魔方吧·中文魔方俱乐部

标题: 最远态小于26步之论文《Twenty-Six Moves Suffice for Rubik's Cube》摘录 [打印本页]

作者: noski 时间: 2008-3-12 00:43:53 标题: 最远态小于26步之论文《Twenty-Six Moves Suffice for Rubik's Cube》摘录

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 编辑 ]

附件: 26-1.jpg (2008-3-12 00:43:53, 34.57 KB) / 下载次数 102
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTM1MzJ8YTBkMTljNDV8MTc0OTUyODExNXwwfDA%3D

附件: 26-2.jpg (2008-3-12 00:43:53, 35.29 KB) / 下载次数 106
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTM1MzN8NzNjZDEyNzd8MTc0OTUyODExNXwwfDA%3D

作者: ggglgq 时间: 2008-3-12 09:28:06

原帖由 noski 于 2008-3-12 00:43 发表
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大师的似同非同。

inversion 的意思是“倒置”，即 “上下镜像”，如同看江河中的“倒影”！

其作用效果与本人的“48 同态”中的“左右镜像”完全一样！

这里的“自同构”一词用的比“同态”好。 “自同构”一词很好、很到位！

作者: ggglgq 时间: 2008-3-12 09:39:19

inversion 一词的意思请大家参考： 魔方词典

http://bbs.mf8-china.com/viewthread.php?tid=615&extra=page%3D1&page=2

I
i（inverse）原义反转。义同“'”。
Ibaneze Guitar Polish GP-800 吉他琴身抛光剂。含有硅酮成分。可以作为魔方的润滑剂。
Ideal Toy Corporation 上世纪八十年代创立的魔方工厂。
Identity 通过一系列魔方转动，最终回到最初转动前的原点。魔方的守恒特性。
Impossiball（图片：

）由Uwe Meffert发明，1982年面世。也被称作Incrediball。貌似三角形积聚而成的球体以五个活动块一组转动。
Inspection Time 魔方比赛用语。转动魔方前允许预先了解状态以准备解法的时间。例如世界比赛的十五秒规则。
Inverse 请参考“mirror”。

虽然 94Walter 翻译的不准确，但意思大家都明白。

作者: duoasis 时间: 2008-3-12 10:01:40

原文有么？能发上来不？

作者: ggglgq 时间: 2008-3-12 10:08:05

关于三阶最远状态步数不超过26步的文章.pdf

http://bbs.mf8-china.com/attachment.php?aid=12270

作者: noski 时间: 2008-3-12 10:12:59 标题: 回复 4# 的帖子

论文原文在这个贴子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."

作者: ggglgq 时间: 2008-3-13 08:55:59

科普一下：“48 同态”

先送大家一个《正六面体二阶魔方-48“同态”图解》软件（点击下载）。

下面简单介绍一下本人的 48 “同态”优化技巧：

1.对于每一操作，都存在一个“左右镜像（对称）操作”（只考虑一个，不要考虑太复杂）

2.对于正六面体二阶魔方的每一操作 T ，都存在 4 * 6 个相对位置的操作态。相当于：
把 n 号位置移到“后左上 0 位置”后再进行操作 T ，共有 4 * 6 个相对位置的操作态。

由 1、2 即可得到正六面体二阶魔方每一操作的 48“同态”操作。详见
《正六面体二阶魔方-48“同态”图解》

由正六面体二阶魔方 48 “同态”优化技巧可知，知道正六面体魔方的一个操作 T ，
就可以知道它的 48 个“同态”操作 T48 ，效率提高了近 48 倍！ 48 “同态”优化技巧
可以大大缩短程序的运行时间，提高程序的运行效率。

“48 同态”对于“正六面体 N 阶魔方”都成立。

作者: ggglgq 时间: 2008-3-14 14:53:53

非常欢迎大家探讨魔方的最少步算法及其深刻的循环变换理论。

首先，对比正六面体二阶魔方的总状态数为 3674160 。
从复原态出发，其分布如下（旋转 180° 按一步计算）：
复原态 1
第01步 9
第02步 54
第03步 321
第04步 1847
第05步 9992
第06步 50136
第07步 227536
第08步 870072
第09步 1887748
第10步 623800
第11步 2644
第12步 0
-----------------------------
总数 3674160

其次，正六面体二阶魔方“考虑角块绝对位置”的总状态数为 88179840 。
从复原态出发，其分布如下（旋转 180° 按一步计算）：
复原态 1
第01步 18
第02步 243
第03步 2874
第04步 28000
第05步 205416
第06步 1168516
第07步 5402254
第08步 20775972
第09步 45391890
第10步 15139920
第11步 64736
第12步 0
-----------------------------
总数 88179840

作者: ggglgq 时间: 2008-3-14 14:55:14

本人开发正六面体二阶魔方最远状态软件时采用了 48 “同态”优化技巧。
在此“技巧”下，本人开发的程序只需计算总状态数的约 1 / 48 个状态，就可以
完成正六面体二阶魔方最远状态的计算。下面是 48 “同态”优化技巧下的结果。

正六面体二阶魔方经过 48 “同态”后的“不同状态”的总状态数仅为 77802 。
从复原态出发，其分布如下（旋转 180° 按一步计算）：
复原态 1
第01步 2
第02步 5
第03步 19
第04步 68
第05步 271
第06步 1148
第07步 4915
第08步 18364
第09步 39707
第10步 13225
第11步 77
第12步 0
------------------------------
总数 77802 ≈ 3674160 / 48

正六面体二阶魔方“考虑角块绝对位置”的“不同状态”的总状态数仅为 1841970 。
从复原态出发，其分布如下（旋转 180° 按一步计算）：
复原态 1
第01步 2
第02步 9
第03步 71
第04步 637
第05步 4449
第06步 24653
第07步 113073
第08步 433709
第09步 947300
第10步 316616
第11步 1450
第12步 0
---------------------------------
总数 1841970 ≈ 88179840 / 48

作者: 黑白子 时间: 2013-8-9 11:12:29

ggglgq 发表于 2008-3-14 14:53
非常欢迎大家探讨魔方的最少步算法及其深刻的循环变换理论。

首先，对比正六面体二阶魔方的总状态数为 ...

正六面体二阶魔方经过 48 “同态”后的“不同状态”的总状态数仅为 77802 ，为什么不是76545，相差的1257个状态是怎么回事？

作者: 黑白子 时间: 2013-8-9 11:14:12

ggglgq 发表于 2008-3-14 14:55
本人开发正六面体二阶魔方最远状态软件时采用了 48 “同态”优化技巧。
在此“技巧”下，本人开发的程序 ...

正六面体二阶魔方“考虑角块绝对位置”的“不同状态”的总状态数仅为 1841970 ，为什么不是1837080，相差的4890哪去了？

作者: ggglgq 时间: 2013-8-9 17:08:44

　　
　　

回黑白子的两楼，因为有很多状态没有 48 同构，它们只有如 16 同构、 12 同构、8 同构等等。
　　
　　
　　
　　

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