魔方吧·中文魔方俱乐部

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

作者: 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

　　

　　举例：

１、正六面体三阶魔方的一个循环变换：

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)) 都是最少步变换最重要。

　　
　　
２、二阶平面魔方的一个循环变换：
  　
为了使大家更好地理解魔方的最远状态（或任意状态）与循环变换的关系，
我在这里用二阶平面魔方的最远状态（二阶平面魔方只有一个最远状态）做说明：
注：因为二阶平面魔方只有一个最远状态，大家好理解，其它魔方同理。
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/)