对循环变换理论的思考备忘录

aubell

1. 需要多少个公式可以覆盖三阶魔方的所有状态？
2. 通过这些公式所得的路径是否最短？
3.  是否阶数越高的公式覆盖的状态越多？
4. 已有证明，最高的阶是1260，如U F2 B' L B' ，
需要重复1260次可回到起点。这样高阶的公式有何意义？

Cielo

前两个问题是什么意思？

反正存在两个公式 A 和 B，交替操作它们若干次，可以转出任何一个状态（这里考虑的是普通三阶魔方）。

aubell

这又是什么意思呢？
还不如说存在六个最短的公式，(R ;U; F;  B;L; D)交替若干次，就可以转成任意状态。
两个和六个没有本质的区别。

不过，您说的两个公式是怎样的呢，非常希望知道。

我所说的“一个公式所覆盖的状态”是指：
把一个公式“头”截下来接在“尾”上，就会产生新的公式；
由一个公式按照这种方式产生的所有公式集对应的状态集，就是这个公式覆盖的状态。

[ 本帖最后由 aubell 于 2010-3-29 21:31 编辑 ]

aubell

魔方对应着有限状态自动机；
魔方公式对应着正则表达式。
希望能从正则表达式入手，突破化简。
s/R R'//g;
s/P1/P2/g;
... ...

如果AB=I,
那么A可以用B'来替换。

[ 本帖最后由 aubell 于 2010-3-29 21:46 编辑 ]

ggglgq

　　
　　
  
    欢迎大家 探索研究、丰富完善《魔方循环变换理论》。
  
    下面就楼主的问题作一下简要说明：
  
    1、需要多少个公式可以覆盖三阶魔方的所有状态？
  
    有待探索，可以预计数量“巨大”。编程搜索所有 正六面体三阶魔方 的
  
循环变换 是 不现实 和 不必要 的。 如果要编程对 正六面体三阶魔方 开解，
  
也只需研究 最大长度一半以内 的所有 循环变换 即可。
  
    2、通过这些公式所得的路径是否最短？
  
    依据魔方 循环变换 的定义，答案是肯定的。
  
    3、是否阶数越高的公式覆盖的状态越多？
  
    答案是否定的。 应该可以构造出阶数为 1 的 遍历公式，它将覆盖所有
  
正六面体三阶魔方 状态。
  
    4、已有证明，最高的阶是1260，如U F2 B' L B' ，
需要重复1260次可回到起点。这样高阶的公式有何意义？
  
    这个与 最少步 没有关系吧？ 更何况 3 、4 两问题 并非是 循环变换
  
的问题。  循环变换 的阶都为 1。
  
　　
　　

ggglgq

　　
  
　　好像有人误把 循环公式 当成 循环变换 了。先普及一下魔方 循环变换
  
的定义吧：
  
    一、先给出几个记号：
  
    在本理论中，统一规定：
   
    小写字母表示步长为 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 的子变换；
   
  
  
    二、魔方循环变换的定义：
  
    对于有效变换 A ，如果 A = 1 ，并且 any(circle0(A),half(A))
  
都是最少步变换，则称变换 A 为循环变换。记作：循环变换 A 或 circle(A)
  
　　　　
　　　　

ggglgq

　　
  
　　举例：
  
    １、正六面体三阶魔方 的一个 循环变换 ：
  
    A = F' L' F R F' L F L U L' U' R' U L U' L'
  

  
  

  
它的所有 半子变换 any(circle0(A),half(A)) 全都是最少步变换。
  
    比如 F' L' F R F' L F L  、 L' F R F' L F L U 、F R F' L F L U L'
  
等等 全都是 最少步变换。
  
    这里所有 半子变换 any(circle0(A),half(A)) 都是最少步变换 最重要。
  
　　
　　
    ２、二阶平面魔方 的一个 循环变换 ：
  　
为了使大家更好地理解 魔方的最远状态（或 任意状态） 与 循环变换 的 关系，
我在这里用 二阶平面魔方的最远状态（二阶平面魔方 只有一个最远状态） 做说明：
注：因为 二阶平面魔方 只有一个最远状态 ，大家好理解，其它魔方同理。
1.找到一个 循环变换（很难找的，对于 二阶平面魔方 当然容易了）；


比如 二阶平面魔方 的一个 最长的 循环变换（由两个 最长变换 构成 ）：
L R U D R L D U
2.由于 一个 循环变换 的 “逆变换”也是 循环变换，故 得到 L R U D R L D U
“逆变换” U D L R D U R L 也是一个 循环变换。
（请大家注意，对于其他魔方来说 L R U D R L D U “逆”为 -U -D -L -R -D -U -R -L ，
对于 二阶平面魔方 才有 -U -D -L -R -D -U -R -L = U D L R D U R L ，因为它
有长度为 2 的循环变换：比如 U U 。 这一点对其他魔方 不适用的）


3.由 循环变换 L R U D R L D U 得到 以下八个 半子变换 都是 最远状态：
L R U D
R U D R
U D R L
D R L D
R L D U
L D U L
D U L R
U L R U
4.由 循环变换 U D L R D U R L 得到 以下八个 半子变换 都是 最远状态：
U D L R
D L R D
L R D U
R D U R
D U R L
U R L U
R L U D
L U D L

5.二阶平面魔方 只有一个最远状态 ，大家可以试试。其他魔方可就复杂多了！
以上 十六 个 半子变换（全是最少步变换） 都指向 同一个 最远状态。





　　
　　
　　
　　　　
　　
  　

Cielo

原帖由 aubell 于 2010-3-29 21:27 发表
... 把一个公式“头”截下来接在“尾”上，就会产生新的公式；
由一个公式按照这种方式产生的所有公式集对应的状态集，就是这个公式覆盖的状态。

这种方式产生的“新的公式”都是和原公式共轭的，
即公式 AB，把头 A 接在 尾 B 上，得到的 BA = A'（AB）A.
所以它覆盖的状态必然只是很少一部分。

可以这么看，设 AB 的周期是 n，则 BA 的周期也是 n，所以所有周期不是 n 的状态都无法被覆盖。

aubell

感觉关键的地方是：
公式生成的方式
截头接于尾。

不必拘泥于等于A=I 。
用“截头接于尾”的方式生产的状态集具有“相似性”。
等于 I 的公式通过这种方式生成的公式具有“相等性”。

相似性是否比相等性更有普遍意义呢？
“相似性”是指状态的相似性：
例如原先是一个“角块三循环”公式，通过这种方式产生的必然还是“角块三循环”；
原先是“两棱换合并两角换”公式，通过这种方式产生的必然还是“两棱换合并两角换”。

谢谢G的点拨。

aubell

我才刚明白这个是“共轭”，呵呵
谢谢！

共轭比“截头接于尾”的方式更具有普遍性。
那么，一个公式的覆盖应扩展为：
一个公式连同它所有的共轭所覆盖的状态。

[ 本帖最后由 aubell 于 2010-3-30 12:17 编辑 ]