[原创]魔方循环变换理论概述 （待完善）

ggglgq

魔方循环变换理论概述（待完善）

一、魔方循环变换的定义：

1.先给出几个记号：

在本理论中，统一规定：
小写字母表示步长为 1 的变换；
大写字母表示由步长为 1 的变换构成的变换。

对于变换 A ，若它的积为单位元，则记为： A = 1 ；

对于变换 A ，
length(A) 表示变换 A 的长度;
half(A) 表示 length(A) 的一半并取整;
例如: A = a1 a2 a3 a4 a5 a6 ；
length(A) = 6 ， half(A) = 3 。
又如: A = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11；
length(A) = 11 ， half(A) = 5 。

对于变换 A ，
circle0(A) 表示变换 A 的首尾相连的旋转变换，旋转方向
继承变换 A 的方向；
注意：变换 circle0(A) 是没有首尾的，但却是有方向的。
如：circle0(a1 a2 a3) 与 circle0(a3 a2 a1) 是反方向。
any(A,n) 表示变换 A 的任意一个相连的长度为 n 的子变换；

2.魔方循环变换的定义：
对于有效变换 A ，如果 A = 1 ，并且 any(circle0(A),half(A))
都是最少步变换，则称变换 A 为循环变换。记作：
循环变换 A 或 circle(A)

二、魔方循环变换的例子：
这里以正六面体三阶魔方为例说明：
由魔方循环变换定义得：宇宙飞碟所举的 [长度为 四 的循环变换] 、
[长度为 八 的循环变换] 、[长度为 十二 的循环变换] 、[长度为 十四
的循环变换] 、 [长度为 十六 的循环变换] 均为正确循环变换的例子。
但宇宙飞碟昨天举的 [长度为 210 的循环变换] 、 [长度为 126
的循环变换] 是错的，是他和大家开玩笑呢。

对于一般的魔方，设它的 [最少步最长的变换] 的长度为 x ，那么
它的循环变换长度最长不过为 2*x+1 。对于正六面体三阶魔方，虽然我还
不清楚它的 [最少步最长的变换] 的长度为多少，但肯定不会超过 30 ，
它的循环变换长度必然小于 61 。因此对于正六面体三阶魔方，宇宙飞碟
昨天的 [长度为 210 的循环变换] 、[长度为 126 的循环变换] 是错的。
不过如果作为不严谨的理解，可以另外再定义一个广义循环变换，
不妨称上面的“魔方循环变换的定义”为狭义循环变换。这样宇宙飞碟
昨天举的 [长度为 210 的循环变换] 、 [长度为 126 的循环变换] 是
两个广义循环变换。

明天再为大家证明 [循环变换] 的首尾无关性！例如：若变换 a1 a2 a3 为
循环变换，则变换 a1 a2 a3 与 a2 a3 a1 和 a3 a1 a2 为同一个循环变换。

[此贴子已经被作者于2006-4-1 14:35:26编辑过]

宇宙飞碟

下面我给出我所知道的真正意义上的几个循环变换： 长度最少的循环变换 [长度为 4 ] ： value="R1R1R1R1" 长度为 八 的循环变换 ： value="R1L1R1L1R1L1R1L1" 长度为 十二 的循环变换 ： value="B1U1B3R3U1R3F1R1F3U3R1U3" 长度为 十四 的循环变换 ： value="R1F1D1F3D3R3U1R1D1F1D3F3R3U3" 长度为 十六 的循环变换 ： value="F3L3F1R1F3L1F1L1U1L3U3R3U1L1U3L3"

宇宙飞碟

两个广义循环变换：

即：105 个 "U1R1"

即：63 个 "U1R3"

cube_master

以下是引用宇宙飞碟在6/3/2004 2:49:44 PM的发言： 呵呵，定理：如果恩师在 www.supersoko.com/bbs 上是 [哥白尼]，那么在本论坛上是“发现了魔方广义循环变换、狭义循环变换”的 [爱因斯坦] 。[em17] 不知大家是否支持该定理呢？请大家跟贴发表意见！[em02][em07][em17]

我正在努力的理解。

ggglgq

　　
　　
三、同一变换的定义：
      同一变换的定义：若两个变换 A 、B 满足: AB=BA，则称 A 与 B 可交换，并且规定 AB 与 BA 是同一变换。
      由同一变换的定义得：若变换 A = a1 a2 a3 ... ax 为循环变换，那么
           a1 a2 a3 ... ax = 1
      所以
           a1 (a2 a3 ... ax) = (a2 a3 ... ax) a1 = 1
      因此 a1 (a2 a3 ... ax) 与 (a2 a3 ... ax) a1 是同一变换。
      故
          a1 a2 a3 ... ax  与 a2 a3 ... ax a1 是同一变换。
      又由变换 A = a1 a2 a3 ... ax 为循环变换，所以
        any(circle0(A),half(A)) 都是最少步变换，故
        a1 a2 a3 ... ax 与 a2 a3 ... ax a1 是同一循环变换。

        同理可得： a2 a3 ... ax a1 与 a3 ... ax a1 a2 是同一循环变换。
          .......................................
          .......................................
          .......................................
       这样我们就证明了 [循环变换] 的首尾无关性！即：
           A = a1 a2 a3 ... a(x-1) ax 为循环变换，那么所有
                 a1 a2 a3 ... a(x-1) ax
                 a2 a3 ... a(x-1) ax a1
                 a3 ... a(x-1) ax a1 a2
                   ................
                 ax a1 a2 a3 ... a(x-1)
          都为同一循环变换。因此在前面的循环变换定义中，把它们统一记作：
                    循环变换 A 或 circle(A)

四、创建《魔方循环变换理论》的意义，即循环变换理论的用途：
       1.帮我们找到魔方任意一个变换的最少步变换；
       2.帮我们找到魔方最少步最长的变换；
       3.魔方中心粒最少步变换的解决；
       4.利用计算机找出某种魔方所有循环变换的[集合]；
       5.利用 4. 的[集合]解决该魔方的上述 1. 2. 3. 的最少步变换问题。

五、利用计算机找出某种魔方所有循环变换的[集合]：
        想要“利用计算机找出某种魔方所有循环变换的[集合]”应该是这一
理论的最精彩的部分，因为随着 [循环变换 A] 的长度的增大，一个这样
的变换就代表 any(circle(A),n) [ n<=half(A) ] 的所有最少步变换，
它的利用效率是相当高的。


        愿对计算机编程感兴趣的魔方爱好者，能注意如何“利用计算机找出
某种魔方所有循环变换的[集合]”来为我们编程服务。同时欢迎大家一起
研究探讨、补充完善魔方循环变换这一理论，使之有更广泛的应用。


        因最近很忙，今后不能天天泡网，只能零星来几次，愿大家能谅解。
若有建议，可以直接回帖提出，或给我发 Email 联系： ggglgq@sina.com　

cube_master

能得到魔方的所有组合的循环变换至少需要多少步？

cube_master

以下是引用ggglgq在6/3/2004 2:33:33 PM的发言：

对于变换 A ， length(A) 表示变换 A 的长度; half(A) 表示 length(A) 的一半并取整; 例如: A = a1 a2 a3 a4 a5 a6 ； length(A) = 6 ， half(A) = 3 。 又如: A = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11； length(A) = 9 ， half(A) = 5 。

请问 又如: A = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11； length(A) = 9 ， half(A) = 5 。

是否应该是：length(A) = 11 ， half(A) = 6

ggglgq

我想不能单纯用 “循环变换至少需要多少步？” 来回答，因为： 对于一般的魔方，设它的 [最少步最长的变换] 的长度为 x ，那么 它的每一个循环变换的长度都不会超过 2*x+1 。但我们不能由一个像这样的 长度为 2*x+1 的循环变换得到魔方的所有最少步变换。 例如：x = 3 是某一魔方的 [最少步最长的变换] 的长度。 a1 a2 a3 b1 b2 b3 为它的一个循环变换， 那么它只能代替 a1、a2、a3、b1、b2、b3 a1 a2、a2 a3、a3 b1、b1 b2、b2 b3、b3 a1 a1 a2 a3、a2 a3 b1、a3 b1 b2、b1 b2 b3、b2 b3 a1、b3 a1 a2 共十八个最少步变换。 [ 注意：长度为 4、5、6 的变换不是最少步变换。如 a1 a2 a3 b1 不是最少步变换，因为 a1 a2 a3 b1 = -b3 -b2 ， 其中 -b3、-b2 分别 表示 b3、b2 的逆变换] 但它却不能代替这种魔方的所有最少步变换。

比如开发正六面体三阶魔方最少步软件 Cube 的作者 H.Kociemba 采用 The Two-Phase Algorithm 算法求解时，特别制作了一个大小是 1G 左右的“表”，便于求解时计算和查表。 对于正六面体三阶魔方，虽然我还不清楚它的 [最少步最长的变换] 的长度为多少，但肯定不会超过 30 ，它的循环变换长度必然小于 61 。 利用《魔方循环变换理论》制作所有循环变换的 [集合]，这个 [集合] 的 大小估计小于 H.Kociemba 制作的大小是 1G 左右的“表”。 [ 注：现在我还没有着手研究这一问题，准备在制作 {所有循环变换的 [集合]} 时，还要尽可能采用旋转、对称等技巧，使任何一个循环变换能 代替 {各种和它旋转、对称后都相同的循环变换}，这样制作出来的 {所有 循环变换的 [集合]} 才能更小，利用效率更高。]

[此贴子已经被作者于2005-5-8 18:12:07编辑过]

ayi2000

以下是引用宇宙飞碟在6/3/2004 3:06:39 PM的发言：

105 个 "U1R1"

这个曾经琢磨过，不过转了七、八十下没看出效果，放弃了…… 不想这个需要210步，汗！

[此贴子已经被作者于6/5/2004 11:12:49 AM编辑过]

notabdc

顶了先，慢慢看。

[此贴子已经被作者于6/6/2004 9:07:11 AM编辑过]