[原创]魔方循环变换理论概述（待完善） - 第3页 - ★ 计算机最少步理论版 (Software Solver Theory) - 魔方吧·中文魔方俱乐部

ggglgq 发表于 2004-6-12 16:36:00

盲拧 54 秒包括记忆

实际上昨天讲的“六、循环变换 [集合] 的构造”问题，往往不是
一个人乃至不是一台计算机在有限的时间内能完成的，即便有再精深的
理论做指导，具体到某个特定的魔方（比如：正十二面体的五魔方）它
需要成千上万的程序员以及成千上万台计算机按照统一规定的方案进行，
它的复杂度远不是求解一个特定图案的最少步所能相提并论的！它是集
所有可能的最少步于一体的“精华”！
 下面简单谈谈这种“循环变换 [集合]”的作用：
 七、构造循环变换 [集合] 的意义：
 如： abcdefgh
 abcdfijk
 abcdglmn
 abcdhopq
 abcdirst
均为某个特定的魔方的循环变换，那么在搜索最少步时，例如此时
已搜索完成：
 abcdd..........
轮到搜索
 abcde..........
但是由 abcdefgh 是该魔方的循环变换，得到：
 abcde 可以被步长更小的 (-h)(-g)(-f) 所替代
那么此时就没必要搜索所有以 abcde 打头的变换了，即不必搜索
 abcde..........
同理，因
 abcdfijk
 abcdglmn
 abcdhopq
 abcdirst
均为该魔方的循环变换，因此也不必搜索
 abcdf..........
 abcdg..........
 abcdh..........
 abcdi..........
同理也不必搜索诸如：
 bcdef..........
 cdfij..........
 dglmn..........
 opqab..........
 bcdir..........

 gfggs abcde..........
 fmfg abcdf..........
 fldsk abcdg..........
 kfk abcdh..........
 romfg abcdi..........
 等等......
 从而大大缩短了计算机的搜索时间，提高了运算效率。
 这就是我创建《魔方循环变换理论》的初衷，就是我前面提到的
《魔方循环变换理论》的用途：
1.帮我们找到魔方任意一个变换的最少步变换；
2.帮我们找到魔方最少步最长的变换；
3.魔方中心粒最少步变换的解决；
4.利用计算机找出某种魔方所有循环变换的[集合]；
5.利用 4. 的[集合]解决该魔方的上述 1. 2. 3. 的最少步变换问题。
 魔方的循环变换在步数较少时是可以手工加理论进行解决的：
比如：我让宇宙飞碟发表的“有关《正六面体三阶魔方的循环变换》
理论的一些命题[定理]”就详细阐述了 “正六面体三阶魔方” 任意五个
[其中任意三个相连的旋转不全相同] 的旋转都是唯一的最少步。并在此
基础上手工找出以下几种循环变换：
 长度最少的循环变换 [长度为 4 ] ：

 value="r1r1r1r1"

长度为八的循环变换：

 value="r1l1r1l1r1l1r1l1"

长度为十二的循环变换：

 value="b1u1b3r3u1r3f1r1f3u3r1u3"
 
 长度为十四的循环变换：

 value="r1f1d1f3d3r3u1r1d1f1d3f3r3u3"

 长度为十六的循环变换：

 value="f3l3f1r1f3l1f1l1u1l3u3r3u1l1u3l3"

又如，如果要构造出正十二面体的五魔方所有循环变换的[集合]，
就必须运用计算机解决！（它的搜索量太大） 但如果我们构造出这个
正十二面体的五魔方所有循环变换的[集合]，那么求解最少步还原魔方
的问题几乎就像 “查表 [集合] 求解” 一样轻松愉快！


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

ggglgq 发表于 2004-6-14 08:17:27

[分享]魔方屏保！

八、步长为奇数的循环变换 [集合] 的构造 前面的“六、循环变换 [集合] 的构造”只是针对于大多数步长为偶数的
循环变换制订的一种最简易的“循环变换 [集合] 构造”的方法，下面再介绍
一下最简易的“步长为奇数的循环变换 [集合] 的构造”的方法： 1.构造步长为 1 的变换 a ，设 A 为 a ，执行 5 。
2.撤消上一步的构造，如果所有步长为 1 的变换都已遍历，则结束
构造循环变换；否则设撤消后的变换为 A ，执行 3 。
3.在 A 的基础上构造下一个步长加一的有效变换 A ，执行 4；若
构造不存在，则执行 2 。
 “ 例如：此时 A 为 a b c ... d ”
4.如果 A 不是最少步,则执行 2 。
 5.如果存在另一个变换 B ，并且 length(B) = length(A) + 1 ，使得
A = B [ B 可能不只一个，有几个就要执行几次 ] ，执行 6 ；否则执行 3 。
6.设 C 为 A (-B) [ 其中：-B 表示 B 的逐元逆变换，
 如 B = a b c ，则 -B = (-c) (-b) (-a) ] ，
 如果 any(circle0(C),half(C)) 都是最少步变换，则 C 为一个循环
变换，执行 7 ；否则执行 3 。
7.让循环变换 C 与前面（构造好的）那些循环变换比较是否相同，若
不相同则添加循环变换 C 并保存这些（新构造的）循环变换；否则不保存
这个循环变换 C 。
8.执行 3 。 对比“六、循环变换 [集合] 的构造”发现，区别仅在于第 5 步骤，
对于“步长为偶数的循环变换”强调 [ A 不是唯一最少步 ]，对于“步长为
奇数的循环变换”则强调 [ length(B) = length(A) + 1 ]。 请大家注意
这两种“强调”的含义。我这样安排只是为了方便大家对照理解，当然我们
可以把它们合并，但那样只适合于程序运行，并不适合读者理解。

ggglgq 发表于 2004-6-16 07:34:37

九、“魔方最少步库”的构造 我们由前面的“八、步长为奇数的循环变换 [集合] 的构造”及“六、循环
变换 [集合] 的构造” 得到： 唯一最少步变换-
 或 }->（与非最少步变换构成）步长为奇数的-
 最少步变换 -- }-> 循环变换
 且 }->（两个最少步变换构成）步长为偶数的-
另一最少步变换- 问题：唯一最少步变换或最少步变换全部都在循环变换 [集合] 中吗？ 这一问题始终困扰着我，至今我还不能给出严格的证明，不过我已经证明了： 定理：对于只有 [偶] 循环变换的魔方来说，唯一最少步变换将随着步长的
增加，最终 [全部都] 变成 [不] 唯一的最少步变换。 这一定理的证明我将会在“广义循环变换”定义给出的同时给出。
不过，我们在没有证明 “ 唯一最少步变换或最少步变换全部都在循环
变换 [集合] 中” 之前，可以在构造循环变换 [集合] 的同时，再追加构造一个
最少步变换 [集合] ，并且随着循环变换 [集合] 的不断增加，不断地检验最少步
变换 [集合] ，如果发现某个最少步变换存在于循环变换 [集合] 中，则删除
该最少步变换。最终的最少步变换 [集合] 可能是个空集。即便不是空集，则因为
我们在构造循环变换 [集合] 的同时，也同步构造了最少步变换 [集合] ，所以
我们就得到了一个由（魔方循环变换 [集合] ＋魔方最少步变换 [集合] ）所
构成的完整的（魔方最少步库）！
如果最少步变换[集合] 是个空集，那么魔方最少步库＝魔方循环变换[集合] 
命题： 魔方的最少步变换全部都在魔方的循环变换 [集合] 中。 欢迎大家跟贴给出这一命题真假性的证明或讨论。

宇宙飞碟 发表于 2004-6-17 18:21:17

如果魔方循环变换[集合] 能够包括所有最少步变换，而每一个循环变换 A 都可以代替它所包含的 length(A) 个 any(circle0(A),half(A)) 的最少步变换，那么就相当于说 “这个魔方循环变换[集合] 中的 [每一步] 都代表一个 [最少步变换]”，效率真是太高了！ [魔方循环变换理论] 构思太精妙了！ [魔方循环变换理论] 真乃 [精妙机] 也！

ggglgq 发表于 2004-6-18 07:53:19

十、魔方最少步库的大小 我们知道魔方有多少种不同状态的图案，就应该有多少种不同的
最少步变换。
比如：正六面体的三阶魔方有 4.325200 E+19 种不同状态的图案；
又如：正十二面体的五魔方有 1.006696 E+68 种不同状态的图案。
 ( 其中 E+19 表示 10 的 19 次方 等等，以后不再说明 )
假设魔方的最少步变换全部都在魔方的循环变换 [集合] 中，
那么我们甚至对正六面体的三阶魔方的循环变换 [集合] 都没那么
大的存储空间去装，更别提正十二面体的五魔方了。 怎么办呢？ 我们分析魔方变换数据结构得到，设魔方的第 N 步的节点个数为 x ，
那么第 2N 步的节点个数为 x 的平方，第 3N 步的节点个数为 x 的立方，
第 4N 步的节点个数为 x 的四次方，第 5N 步的节点个数为 x 的五次方，
.................................
即得魔方的前 a*N 步的节点个数数量级是魔方的前 N 步的节点个数
数量级的 a 次方！
假设 1.0 E+10 是现今计算机解决问题的最大存储空间，只要看不同
状态的图案个数（魔方最少步库的大小）是 1.0 E+10 的多少次方就
可以大概估计出要如何 分 这个库。 比如：正六面体的三阶魔方共有 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
左右的“表”，便于求解时查表计算。

又如：正十二面体的五魔方共有 1.006696 E+68 种不同状态的图案，
它大约是 1.0 E+10 的七次方，同样设正十二面体的五魔方前 N 步的节点
个数为 1.0 E+10 ，那么正十二面体的五魔方的前 7N 步的节点便可超过
正十二面体的五魔方 1.006696 E+68 种不同状态的图案。（分七个 N 步） 这些问题应是程序员们大展自己聪明才智的问题，这里我就不多说了。
相信每个程序员都可以依据《魔方循环变换理论》创造出适合自己的算法，
及适合自己的“前 N 步的节点”的魔方最少步库。 对了，顺便说一下，对于正六面体的三阶魔方，这个“前 N 步的节点”
的魔方最少步库构造时，再考虑和它旋转、对称后都相同的最少步，就要
至少除以 48 （ 6 个面，每个面都有 4 个相邻面，确定了两个相邻面即
固定了该魔方，然后再考虑对称的 2 种情形，即可得 6 x 4 x 2 = 48 ）
即得按《魔方循环变换理论》制作的正六面体的三阶魔方最少步库的
大小为 4.325200 E+19 的算术平方根除以 48 得到：137 M 即 0.137 G 。
然后考虑每个字节所表示的数值最大为 256 ，六个面共有 12 种步长为 1
的变换，256 > 12 x 12 ，因此每个字节又可至少装下两个步长的变换，
从而由 137 M 除以 2 得到：68.5 M 。所以我们可以最多用 68.5 M 的
存储空间，即可进行 The Two-Phase Algorithm 算法。这确是一个喜人的
数字，也是一个理想中的数字，对于程序员们来说，要走的路还长 ......

宇宙飞碟 发表于 2004-6-18 14:44:17

<DIV class=quote>以下是引用ggglgq在6/18/2004 7:53:19 AM的发言：

 十、魔方最少步库的大小
 我们知道魔方有多少种不同状态的图案，就应该有多少种不同的
最少步变换。
比如：正六面体的三阶魔方有 4.325200 E+19 种不同状态的图案；
又如：正十二面体的五魔方有 1.006696 E+68 种不同状态的图案。
 ( 其中 E+19 表示 10 的 19 次方 等等，以后不再说明 )
假设魔方的最少步变换全部都在魔方的循环变换 [集合] 中，
那么我们甚至对正六面体的三阶魔方的循环变换 [集合] 都没那么
大的存储空间去装，更别提正十二面体的五魔方了。
 比如：正六面体的三阶魔方共有 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
左右的“表”，便于求解时查表计算。


 对了，顺便说一下，对于正六面体的三阶魔方，这个“前 N 步的节点”
的魔方最少步库构造时，再考虑和它旋转、对称后都相同的最少步，就要
至少除以 48 （ 6 个面，每个面都有 4 个相邻面，确定了两个相邻面即
固定了该魔方，然后再考虑对称的 2 种情形，即可得 6 x 4 x 2 = 48 ）
即得按《魔方循环变换理论》制作的正六面体的三阶魔方最少步库的
大小为 4.325200 E+19 的算术平方根除以 48 得到：137 M 即 0.137 G 。
然后考虑每个字节所表示的数值最大为 256 ，六个面共有 12 种步长为 1
的变换，256 > 12 x 12 ，因此每个字节又可至少装下两个步长的变换，
从而由 137 M 除以 2 得到：68.5 M 。所以我们可以最多用 68.5 M 的
存储空间，即可进行 The Two-Phase Algorithm 算法。
</DIV>

 我们可以最多用 68.5 M 的存储空间，即可进行 The Two-Phase Algorithm 算法。不知将来有朝一日三阶魔方最少步软件 Cube 3.20 的开发者 H.Kociemba 会对此作何感想？恐怕只有佩服我们中华民族的 [爱因斯坦] 了！
[此贴子已经被作者于6/18/2004 3:45:56 AM编辑过]

ggglgq 发表于 2004-6-24 08:08:40

十一、“广义循环变换”的定义及应用

1.“广义循环变换”严格的定义：对于最少步变换 A ，如果存在一个与 A 不同的变换 B ，使得 A(-B) = 1 ，设 C 为 A (-B) ， [ 其中：-B 表示 B 的逐元逆变换，如 B = a b c ，则 -B = (-c) (-b) (-a) ] 且 any(circle0(C),half(C)) 中存在一个是最少步变换，则称变换 C 为广义循环变换。记作：广义循环变换 C 或 Gcircle(C)
显然，若 length(B) <= length(A) + 1，条件[ 且 any(circle0(C),half(C)) 中存在一个是最少步变换 ] 多余。

2.“广义循环变换”的一般理解性定义：除了 1.“广义循环变换”严格的定义外，在不严格的情况下，有时泛称：对于有效变换 A ，如果 A = 1 ，则称变换 A 为广义循环变换。记作：广义循环变换 A 或 Gcircle(A)

3.“广义循环变换”的几个应用：

定理：对于只有 [偶] 广义循环变换的魔方来说，唯一最少步变换将随着步长的增加，最终 [全部都] 变成 [不] 唯一的最少步变换。
要证明上面的定理，只要证明下面的定理即可！

定理一：设对于只有 [偶] 广义循环变换魔方的最长变换的长度为 x ，并设：a1 a2 a3 ...... a(x-1) ax 为其中任意一个长度为 x 的最少步变换，设这个变换为 A ，即：A = a1 a2 a3 ...... a(x-1) ax ，又设 d 为任一个步长为 1 的变换，那么：对于这个最长变换 A 存在一个由 d 开始的长度为 x 的最少步变换 B ，使得：A = B 。
证明：假设 (-d) 使 a1 a2 a3 ...... a(x-1) ax 左无效，则得到存在 i ，使得 a1 a2 a3 ...... a(x-1) ax = ai a1 a2 a3 ...a(i-1) a(i+1)... a(x-1) ax 并且 d = ai ，此时设 B = d a1 a2 a3 ...a(i-1) a(i+1)... a(x-1) ax 即得结论。假设 (-d) 使 a1 a2 a3 ...... a(x-1) ax 左有效，因魔方的最长变换的长度为 x，因此对于变换 (-d) a1 a2 a3 ...... a(x-1) ax 必不是最少步变换，假设它的一个最少步变换为 b1 b2 b3 ...... bn （n <= x），则 (-d) a1 a2 a3 ...... a(x-1) ax (-(b1 b2 b3 ...... bn)) = 1 ， a1 a2 a3 ...... a(x-1) ax (-(b1 b2 b3 ...... bn)) (-d) = 1 ，设 B = d b1 b2 b3 ...... bn ，则 A = B 。因 (-d) 使 a1 a2 a3 ...... a(x-1) ax 左有效，而变换 B 又由 d 开始，故 B 与 A 是不同的变换，且length(A)=x，length(B) <= x+1 = length(A) + 1 ，又因 a1 a2 a3 ...... a(x-1) ax 为一个长度为 x 的最少步变换，故 a1 a2 a3 ...... a(x-1) ax (-(b1 b2 b3 ...... bn)) (-d) 为广义循环变换，又因该魔方为只有 [偶] 广义循环变换魔方，因此 n <= x - 1 。（若 n = x ，则 a1 a2 a3 ...... a(x-1) ax (-(b1 b2 b3 ...... bn)) (-d) 构成 [奇] 广义循环变换，与只有 [偶] 广义循环变换的魔方矛盾。）因此 a1 a2 a3 ...... a(x-1) ax = d b1 b2 b3 ...... bn ，(n <= x - 1) 又因 a1 a2 a3 ...... a(x-1) ax 为其中一个长度为 x 的最少步变换，所以 n = x - 1 且 d b1 b2 b3 ...... bn 为最少步变换。（若 n < x - 1 ，则 length( d b1 b2 b3 ...... bn ) < 1 + ( x - 1 ) = x 即 length( d b1 b2 b3 ...... bn ) < x ，与 a1 a2 a3 ...... a(x-1) ax 为一个长度为 x 的最少步变换矛盾。同样若 d b1 b2 b3 ...... bn 非最少步变换，亦得矛盾。）即得 B = d b1 b2 b3 ...... bn （ n = x - 1 ），且 A = B 。因 n = x - 1 ，所以 d b1 b2 b3 ...... bn （ n = x - 1 ）为一个长度为 x 的最少步变换。又因变换 B 由 d 开始，故定理得证。
同理，再由“右有效”可证得：

定理二：设对于只有 [偶] 广义循环变换魔方的最长变换的长度为 x ，并设：a1 a2 a3 ...... a(x-1) ax 为其中任意一个长度为 x 的最少步变换，设这个变换为 A ，即：A = a1 a2 a3 ...... a(x-1) ax ，又设 d 为任一个步长为 1 的变换，那么：对于这个最长变换 A 存在一个由 d 结束的长度为 x 的最少步变换 B ，使得：A = B 。

[ 本帖最后由 ggglgq 于 2009-8-2 00:28 编辑 ]

ggglgq 发表于 2004-6-27 16:29:04

实践证明，“宇宙飞碟”昨天给出的征解对角还原方法是“最少步”，
我看大家的确对《魔方循环变换理论》知之甚少，我们再谈谈《循环公式》
或许大家感兴趣些。《循环公式》地址：<a href="http://bbs.mf8-china.com/dispbbs.asp?boardID=2&ID=181&page=1" target="_blank" >http://bbs.mf8-china.com/dispbbs.asp?boardID=2&ID=181&page=1</A>
 《魔方循环变换理论》就暂时先告一段落吧。

ggglgq 发表于 2004-6-28 18:02:26

《魔方循环变换理论》就暂时先告一段落，若有建议，可以直接回帖提出，
或给我发 Email 联系： <a href="mailtggglgq@sina.com" target="_blank" >ggglgq@sina.com</A> 作者：刘国勤 2004.06.28

cube_master 发表于 2004-6-28 20:20:34

非常感激刘老师给　魔方吧　带来的新话题，亦希望各位对《魔方循环变换理论》有兴趣的朋友提出自己的见解。

页: 1 2 [3] 4 5 6 7 8 9 10 11 12

魔方吧·中文魔方俱乐部's Archiver

盲拧 54 秒包括记忆

[分享]魔方屏保！