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

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

轻描淡写3333333

收藏了慢慢看吧。。。。。

铯_猪哥恐鸣

ggglgq 发表于 2015-5-18 16:18
　　
  
    嗯，Two-Phase Algorithm 并非是 双向广搜算法，不然它就是严谨的最少步算法了。

好吧，这样啊。

因为已经有文章指出求解某个状态的最少步解是NP难问题了，不知道这一块的研究可能的价值是什么。

ggglgq

　　
  
    嗯，Two-Phase Algorithm 并非是 双向广搜算法，不然它就是严谨的最少步算法了。
  
记得 铯 的《论二阶魔方的计算机求解及优化》是 双向广搜算法，但 不知何故 被阁下
  
删除了？！   上面的引用说的就是 双向广搜算法。
  
  
    想当初我对 循环变换 的浓缩法还是信心满怀的。但就一个 正六面体三阶魔方 的
  
最少步就已让我费尽心机，撞得头破血流了，到现在才知道 正六面体三阶魔方 最远态
  
要 26 步（我以前一直想象的是 22 步），就别说高阶魔方了（双向广搜算法 不现实）。
  
    因此，后来我把 循环变换 引向 循环变换球面网 —— 希望用图论（结合群论）和
  
度量（高维度量空间）等方法，来拓展研究 魔方 的最少步。  比如：
  
      http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=34872
  
      http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=7532
  
等都是我后来加的。
  
  
    能指出《循环变换概论》这些不严谨的地方，说明 铯 是个有心人啊。希望我们能
  
从不同角度出发，不断挖掘深藏在魔方内部的宝藏，为我们的魔方最少步理论添砖加瓦。
  
　　
　　
　　
　　
　　
　　

铯_猪哥恐鸣

首先纠正个错误：

正六面体的三阶魔方共有 4.325200 E+19 种不同状态的图案， 它大约是 1.0 E+10 的平方，因此设正六面体的三阶魔方的前 N 步的节点 个数为 1.0 E+10 ，那么正六面体的三阶魔方的前 2N 步的节点便可超过 正六面体的三阶魔方 4.325200 E+19 种不同状态的图案。（分两个 N 步） 这就是开发正六面体三阶魔方最少步软件 Cube 的作者 H.Kociemba 采用 The Two-Phase Algorithm 算法的理论基础，他制作了一个大小 1G 左右的“表”，便于求解时查表计算。

Two-Phase Algorithm并不是这个原理。

从上下文来看可能你想表达的是双向广搜算法。那么问题来了：
对于给定状态，如何用你生成的表（循环变换集合）来求解该状态？
请给出一个精确可操作的算法，我会在你基础之上分析它的时间复杂度、空间复杂度等。

注：如果是传统的双向广搜，复杂度依然大的不可接受。比如以18f的状态为例，你需要遍历所有9f及以内的状态，并且把这些节点都保存在内存中。从现有的知识来看，这总共约有20G个节点，而且在这一步，对称性优化是用不上的，尽管生成的表可以除以48，搜索空间是无法除的。于是如果采用双向广搜，即便抛开时间复杂度不谈，内存里如何存储这20G个节点就是问题。而相比而言，现在IDA*算法搜索的节点只需要500M以内，且不需要保存搜索过的节点，即搜索过程的额外空间占用可以忽略。

黑白子

ggglgq 发表于 2005-10-9 16:15
循环变换的迷雾——“无效变换”
    1.有效变换、无效变换的定义：
以下是引用ggglgq在2004-6-24  ...

这个发言的原帖在哪里？


______________________________________________________________________________
  
   
    为了看帖方便，就在这里回帖吧。
   
    关于 有效变换 的定义，经过缜密思考，感觉挺复杂的。因此取消了 有效变换 的定义。
  
当初只是为了强调 循环变换 与一般循环的不同，所以加上了 有效变换 的概念。 后来感觉
  
不必再过多解释 有效变换 可能更好些，所以就删去了有关 有效变换 的定义……
  
    唉，越说越复杂……不说了。
  
                       ggglgq   回复
   
  
  
               

黑白子

ggglgq 发表于 2005-1-5 08:31
以下是引用ggglgq在2005-1-3 11:05:04的发言：
  
  在三阶魔方中是“循环变换”的，在五阶魔方中间用却 ...

这个是否对纯色魔方而言是循环变换，对全色魔方则不是循环变换？
　　
______________________________________________________________________________________
  
       是的。                         ggglgq   回复
  
  
　　
　　

黑白子

宇宙飞碟 发表于 2004-6-3 14:59
下面我给出我所知道的真正意义上的几个循环变换：

长度最少的循环变换 [长度为 4 ] ：

已经找出三阶魔方的这些循环变换，理论上又怎样根据这些循环变换找出三阶魔方的最少步呢？
　　
______________________________________________________________________________________
  
    需要利用计算机建立“魔方循环变换库”，详见《六、循环变换 [集合] 的构造》以后的内容，
  
比较复杂的。
  
    http://bbs.mf8-china.com/forum.p ... =153&page=2#pid1168  
  
                                             ggglgq   回复
  
  
　　
　　

黑白子

宇宙飞碟 发表于 2004-6-3 14:59
下面我给出我所知道的真正意义上的几个循环变换：

长度最少的循环变换 [长度为 4 ] ：

长度为4和8的比较明显，长度为12、14和16的公式为什么是循环变换？

　　  
______________________________________________________________________________________
  
        按循环变换定义判定。  
  
                                            ggglgq   回复
  
  
　　
　　

黑白子

什么是子变换和半子变换？请举例说明。
  
  
___________________________________________________________________________________
　
　　
　　
  
    唉，不用群定义“循环变换”，解释起来真麻烦。
  
    设 变换 A = a1 a2 ... an = 1  ， n 为 变换 A 的长度，为正整数。
  
  
    当长度 n = 1 时，A 为点循环变换 （单位点，点循环变换）。  这个情况比较特殊，
  
只有骰子类魔方才具备这个特征，此情况可以看成 无 半子变换（注：不得不解释的废话）。
  
   
    当长度 n > 1 时，半子变换 是指循环公式中的 相连的半子变换（不是离散的）：
  
  
         如果 n 为偶数，半子变换 是 相连的长度为 n 的一半的子变换；
  
  
         如果 n 为奇数，半子变换 是 相连的长度为 n-1 的一半的子变换；
  
  
  
        比如对于变换 A1 = a1 a2 a3 a4 a5 a6  ，此时 n = 6， n 的一半 为 3 ：
  
        其所有的 半子变换 为 a1 a2 a3 、a2 a3 a4 、a3 a4 a5 、a4 a5 a6 、a5 a6 a1 、a6 a1 a2
  
  
  
        比如对于变换 A1 = a1 a2 a3 a4 a5 a6 a7 ，此时 n = 7， n-1 的一半 为 3 ：
  
        其所有的 半子变换 为 a1 a2 a3 、a2 a3 a4 、a3 a4 a5 、a4 a5 a6 、a5 a6 a7 、a6 a7 a1 、a7 a1 a2
  
      
　　
　　                                 ggglgq  回复