魔方吧·中文魔方俱乐部

标题: 对循环变换理论的思考备忘录 [打印本页]

作者: aubell    时间: 2010-3-29 19:33:01     标题: 对循环变换理论的思考备忘录

1. 需要多少个公式可以覆盖三阶魔方的所有状态?
2. 通过这些公式所得的路径是否最短?
3.  是否阶数越高的公式覆盖的状态越多?
4. 已有证明,最高的阶是1260,如U F2 B' L B' ,
需要重复1260次可回到起点。这样高阶的公式有何意义?
作者: Cielo    时间: 2010-3-29 21:18:46

前两个问题是什么意思?

反正存在两个公式 A 和 B,交替操作它们若干次,可以转出任何一个状态(这里考虑的是普通三阶魔方)。
作者: aubell    时间: 2010-3-29 21:27:33     标题: 回复 2# 的帖子

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

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

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

[ 本帖最后由 aubell 于 2010-3-29 21:31 编辑 ]
作者: aubell    时间: 2010-3-29 21:40:24

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

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

[ 本帖最后由 aubell 于 2010-3-29 21:46 编辑 ]
作者: ggglgq    时间: 2010-3-29 23:31:13

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

  
  
  好像有人误把 循环公式 当成 循环变换 了。先普及一下魔方 循环变换
  
的定义吧:
  
    一、先给出几个记号:
  
    在本理论中,统一规定:
   
    小写字母表示步长为 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    时间: 2010-3-29 23:35:54

  
  
  举例:
  
    1、正六面体三阶魔方 的一个 循环变换 :
  
    A = F' L' F R F' L F L U L' U' R' U L U' L'
  
[java3=300,300]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]F' L' F R F' L F L U L' U' R' U L U' L'[/param]
[/java3]
  
它的所有 半子变换 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)) 都是最少步变换 最重要。
  
  
  
    2、二阶平面魔方 的一个 循环变换 :
   
为了使大家更好地理解 魔方的最远状态(或 任意状态) 与 循环变换 的 关系,
我在这里用 二阶平面魔方的最远状态(二阶平面魔方 只有一个最远状态) 做说明:
注:因为 二阶平面魔方 只有一个最远状态 ,大家好理解,其它魔方同理。
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    时间: 2010-3-30 10:23:42

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


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

可以这么看,设 AB 的周期是 n,则 BA 的周期也是 n,所以所有周期不是 n 的状态都无法被覆盖。
作者: aubell    时间: 2010-3-30 10:34:43

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

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

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

谢谢G的点拨。
作者: aubell    时间: 2010-3-30 10:36:56     标题: 回复 8# 的帖子

我才刚明白这个是“共轭”,呵呵
谢谢!

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

[ 本帖最后由 aubell 于 2010-3-30 12:17 编辑 ]
作者: aubell    时间: 2010-3-30 10:48:17

也许应该从化简“共轭公式”和“交换子”的组合入手。
循环公式的不同次数也要化简。

呵呵,“循环变换”真的不太好理解,继续学习中...

[ 本帖最后由 aubell 于 2010-3-30 11:00 编辑 ]
作者: aubell    时间: 2010-3-30 12:27:25

从状态的“形态”对公式分类:
1.盲拧中需要奇偶校验的(含独立Parity)
2.不需要奇偶校验的(不含独立Parity)
转换方式:任意一个90度旋转

二分法
如何把这两类各自继续“二分”下去呢?
作者: dangerxxxx    时间: 2010-3-30 13:47:45

很复杂貌似看不懂
作者: superflip    时间: 2010-3-30 15:27:22     标题: 回复 6# 的帖子

循环变换这定义也太强悍了吧~

版主能否提供一下利用此变化在2阶魔方的最小步搜索程序时的应用,我也比较好奇此算法的时间和空间复杂度~
作者: ggglgq    时间: 2010-3-31 09:17:04

 
  
  
    非常高兴地看到有这么多魔友参与 循环变换、循环公式 等 循环理论 的
  
探讨。循环变换理论 还处在起步阶段,很多 关键性的基础问题 还没有搞明白,
  
希望大家积极参与探索探究。 先从 最初级、最基本 的东西开始吧,比如:
  
  
    征集各类小巧魔方态态关系网
  
    http://bbs.mf8-china.com/viewthread.php?tid=30653
  
   
    正 N 点 M 连循环变换球面网探究
  
    http://bbs.mf8-china.com/viewthread.php?tid=34872
  
  
  
  
作者: ggglgq    时间: 2010-3-31 09:22:39

原帖由 Cielo 于 2010-3-30 10:23 发表
  
  这种方式产生的“新的公式”都是和原公式共轭的,
即公式 AB,把头 A 接在 尾 B 上,得到的 BA = A'(AB)A.
所以它覆盖的状态必然只是很少一部分。

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

  
  
  
  
原帖由 aubell 于 2010-3-30 10:34 发表
  
感觉关键的地方是:
公式生成的方式
截头接于尾。

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

  
  
    不错,两位都探讨了 循环公式 的内容,它们都是相似变换(共轭),除
  
有“相同的阶”外,很多都不是最少步,不太适合 计算机 搜索。
  
  
    循环变换 与之不同,它的 半子变换 的 阶 不同,且都是 最少步变换,
  
效率很高,非常适合 计算机 搜索。 这是 循环变换理论 的 核心价值 所在。
  
   
    当然,循环变换、循环公式 都是 循环理论 研究的问题,它们的侧重点
  
有所不同,各有所长,可以互补对方不足。 我在这里只是强调 循环变换 的

“核心地位”,希望大家不要忽视 这“核心地位”之关键 而已。
  
  
  
  
  
  
作者: aubell    时间: 2010-3-31 17:42:28

“利用计算机找出某种魔方所有循环变换的[集合]”,
这个集合估计有多大?
作者: ggglgq    时间: 2010-3-31 19:12:07

  
  
  
    能够“利用计算机找出所有循环变换”的魔方,也是极少数的“小魔方”。
  
绝大多数魔方的“循环变换”数量比较大,编程搜索 正六面体三阶魔方 所有
  
循环变换 是 不现实 和 不必要 的。 如果要编程对 正六面体三阶魔方 开解,
  
也只需研究 最大长度一半以内 的所有 循环变换 即可。
  
     
    欢迎大家积极参与探索研究《魔方循环变换理论》,使之为广大魔友服务。
  
先从 最初级、最基本的东西开始吧,比如 15 楼所说的。
  
  
  
  
  
作者: superflip    时间: 2010-3-31 20:19:12     标题: 回复 18# 的帖子

不知版主说的“小魔方”多小?2阶魔方算不算,如果太小显然整个状态转换图都画出来了,那不都清楚了。

我想版主以前做出循环变化的定义,也是想部分提高计算机求解2,3阶最小步时的数据库效率,不知您是否在2阶上试过,我和aubell 一样也比较好奇这个数据库多大时可大幅提高搜索2阶最小步时的效率。或者说您在2阶上做出的最大的循环变换的集合有多大?
作者: superflip    时间: 2010-4-5 15:53:41

ggglgq版主回下19# 的问题行吗? 非常好奇答案,因为这条路与现有的思路不同,想了解下难度和目前的进展~
作者: ggglgq    时间: 2010-4-8 13:57:54

原帖由 superflip 于 2010-4-5 15:53 发表
  
ggglgq版主回下19# 的问题行吗? 非常好奇答案,因为这条路与现有的思路不同,想了解下难度和目前的进展~

  
  
  
    由于单位和家中配置了新电脑,以前 VB6 的魔方求解程序难以在新系统中
  
调试运行,因此本人暂缓此次 循环变换 在正六面体二阶魔方的探究,希望各位
  
魔友理解并见谅。    请各位魔友继续研究 循环变换 的其他问题吧。
  
  
  
  
  




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