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

ggglgq 发表于 2005-4-16 09:29:59

魔方状态变换序列
先给一个“终极状态”的特例：（请参考“<a href="http://bbs.mf8-china.com/dispbbs.asp?boardID=15&ID=514&star=2&page=1" target="_blank" >终极状态</A>”）
<APPLET code=RubikPlayer.class codeBase=3 height=400 width=300><PARAM NAME="scrpt" VALUE="R F2 U R2 U2 B L R B2 L' D' F2 U' L B L' F' U2 R' U'"><PARAM NAME="initscrpt" VALUE="U R U2 F L B' L' U F2 D L B2 R' L' B' U2 R2 U' F2 R'"><PARAM NAME="scrptlanguage" VALUE="HarrisENG"></APPLET>


本文所涉及的内容默认为“正六面体三阶魔方”，可以很容易扩展到其它各类
魔方中去。为使结论尽量不产生偶然的冲突，特规定旋转 180 度为 2 步！
 为了阐述方便，下面先引入几个描述性的概念：
描述性理解的概念有：状态、终极状态、路过、偶尔路过、出路。
 1.状态：本文所提的所有的“状态”均为从“初始状态”出发，由某一最少步
变换序列而产生的“状态”。通常我们用这个最少步变换序列表示这个“状态”。
一个“状态”往往可以有很多“最少步变换序列”！
比如：从初始状态出发，由最少步变换序列 r1 r1 产生的状态，记作：
状态 r1 r1 。当然状态 r1 r1 有两个最少步变换序列： r1 r1 和 r3 r3 。
 2.路过：如果状态 A 的步长大于 1 ，并且最少步变换序列 A 是唯一最少步，
变换序列 B 为去掉变换序列 A 最后一个步长为 1 的变换的任一子变换序列，
此时我们称状态 A “路过” 状态 B 。
比如：状态 r1 u1 f1 是唯一最少步变换序列，则状态 r1 u1 f1 分别路过
状态 r1 、状态 u1 、状态 r1 u1 。 
 3.偶尔路过：如果状态 A 的步长大于 1 ，并且变换序列 A 不是唯一最少步，
变换序列 B 为去掉变换序列 A 最后一个步长为 1 的变换的任一子变换序列，
此时我们称状态 A “偶尔路过” 状态 B 。
比如：状态 r1 r1 不是唯一最少步变换序列，则状态 r1 r1 分别偶尔路过
状态 r1 、状态 r3 。 这是因为状态 r1 r1 和状态 r3 r3 为同一状态的
两个最少步变换序列。 
 4.终极状态：设 c 为任意一个步长为 1 的变换，对于状态 A 存在一个由 c
结束的最少步变换序列 B ，使得 A = B ，则称状态 A 为“终极状态”。
由 [宇宙飞碟] 的离初始状态最远的图案的定理可知：
任一离初始状态最远的状态都为终极状态，但反过来说却是错误的！
 5.出路：如果状态 A 不是终极状态，我们称状态 A 有 “出路” 。
只有状态 A 有出路时，我们才有可能沿着状态 A 的出路构造比状态 A
更远的状态！而寻找这种出路，照目前看来，在没有更先进的理论面世之前，
也只能用“循环变换”理论更容易些了！定理：任一状态不偶尔路过某一终极状态 。


 证明非常简单，因为若一个状态 P 偶尔路过某一终极状态，设状态 P 变换序列为
a1 a2 ... b1 b2 ... bm -c ... an ，其中 b1 b2 ... bm 为终极状态，那么对于这个
终极状态 b1 b2 ... bm ，存在一个由 c 结束的最少步变换序列 c1 c2 ... c(m-1) c ，
使得 b1 b2 ... bm = c1 c2 ... c(m-1) c ，这时我们发现，变换序列 P 已经变为
a1 a2 ... b1 b2 ... bm -c ... an = a1 a2 ... c1 c2 ... c(m-1) c -c ... an ，
a1 a2 ... b1 b2 ... bm -c ... an = a1 a2 ... c1 c2 ... c(m-1) ... an ，即说明
P = a1 a2 ... b1 b2 ... bm -c ... an 不是最少步变换序列，这与状态的概念矛盾，
故定理得证。
 由上面的定理直接得到： 离初始状态最远的状态不偶尔路过某一终极状态 。
 这个定理告诉我们，如果一个状态是终极状态，那么它有可能是一个离初始状态
最远的状态 ，如果它不是最远的状态，那么我们不可能再通过这个终极状态来构造
其它任何状态，当然更不可能通过这个终极状态来构造离初始状态最远的状态了！
呵呵，希望魔友们在寻找 离初始状态最远的状态 时一定要避开 终极状态 的暗礁呀！

乌木发表于 2005-5-6 19:45:10

对循环变换我不懂，这里仅对老猫那16步提个问题。为何要写成“UULLRRU'DDU'LLRRDD”而不写成“UULLRRDDUULLRRDD”呢？

ggglgq 发表于 2005-5-7 12:14:41

乌木先生的问题很好！UULLRRU'DDU'LLRRDD 与 UULLRRDDUULLRRDD 都是循环变换，
但略有不同，比如“UULLRRU'D”与“UULLRRDD”两个子最少步就不一样。 总之，“魔方的循环变换”有很多，在用计算机编程解决具体某一魔方最少步问题时，
要对生成的循环变换库进行最大限度的优化，删减相近的循环变换，并要包含所有最少步，
使得循环变换库最小。

乌木发表于 2005-5-23 15:10:11

楼上回答我：“UULLRRU'DDU'LLRRDD 与 UULLRRDDUULLRRDD 都是循环变换，但略有不同，比如‘UULLRRU'D’与‘UULLRRDD’两个子最少步就不一样。”

我当然还是不懂，未入门嘛。我现只能理解为：把...DDUU...或...UUDD...写成...U'DDU'...是 “别有用心” 的，大概门外人入门后自会懂其奥妙的。

[ 本帖最后由乌木于 2009-3-12 11:56 编辑 ]

ggglgq 发表于 2005-5-29 09:55:23

循环变换球面网
 看到大家这两天都在研究“魔方网”，我也来这儿补补“循环变换球面网”！
 要我说，“魔方态关系网”可以看成均匀分布在一个大球面上。这个球面的大圆就是长度最大的 “循环变换”，每一个“循环变换”都是这个球面上的大圆或小圆。呵呵，这只是一个形象的比喻。 所谓大圆就是球体表面最大的圆，它的特点是圆心就是球体的球心，其它的圆心不过球心的圆叫小圆。
 大家可以研究一下“循环变换关系网”、“广义循环变换关系网”、“算子循环变换关系网”等等， 以及它们的异同并绘制它们的图形样本，这对大家的“各种网”都有帮助！我初步考虑可以这样绘制：
 1.循环变换：圆（正三角、正方形等等都是“圆”）
 2.广义循环变换：封闭的不规则图形
 3. N 阶（即周期为 N ）算子循环变换： N 个全等花瓣连成的封闭图形

ggglgq 发表于 2005-5-30 08:03:23

我构造的 2×2 平面魔方“循环变换球面网” 
<img src="http://bbs.mf8-china.com/data/attachment/forum/dvbbs/2005-5/2005530753795616.jpg">
 2×2 平面魔方有 4 种操作 U 、 D 、 L 、 R 。 2×2 平面魔方的“循环变换球面网” 为“正八面体的循环变换球面网”（如图）。
 请各位魔友注意，图中 A --> B 箭头表示：从 A 到 B 但还需要整体旋转后才能得到 B 。 图中不带箭头的可以互相转换；但带箭头的是不能互相转换的，转换后还需整体旋转。
 我们不妨分别用 U 、 U+ 、 U2 、 U- 表示（D 、 L 、 R 操作同理）： U 表示操作 U 后不需要再做整体旋转； U+ 表示操作 U 后再做顺时针整体旋转； U2 表示操作 U 后再做整体旋转 180 度； U- 表示操作 U 后再做逆时针整体旋转。
 由 2×2 平面魔方“正八面体的循环变换球面网”可以得出， 2×2 平面魔方“循环变换” 只有三种：
 1. 步长为 2 的循环变换：如 U U （两点式圆）
 2. 步长为 3 的循环变换：如 D R U- （正三角圆）
 3. 步长为 4 的循环变换：如 D U D U （正方形圆）
 其他的封闭多边形均是“广义循环变换”，当然可以构造出 N 阶（即周期为 N ）算子循环 变换。请感兴趣的魔友自己试试！
 由 2×2 平面魔方“正八面体的循环变换球面网”可以得出，2×2 平面魔方总状态数只有 6 个 （经过整体旋转后相同的为同一状态）。最小循环变换为 2 个步长，最大循环变换为 4 个步长。
 由最大循环变换为 4 个步长立即得到： 2×2 平面魔方 最远状态的最少步只有 2 个步长。 （即得 2×2 平面魔方任意两个状态之间最多需要 2 步）， 比如： D U 就是 2×2 平面魔方的一个最远状态！ 
[此贴子已经被作者于2005-5-30 11:53:22编辑过]

ggglgq 发表于 2005-5-30 08:48:54

从上面的例子，大家可能对“循环变换球面网”已有了更进一步的认识。实际上各类魔方的 “循环变换”都构成“循环变换球面网”！ 不过，请大家注意，这个“循环变换球面网”的球面可能不是“三维空间的球面网”，而是 “高维空间的球面网”！

ggglgq 发表于 2005-5-30 11:24:42

为了大家便于理解 2×2 平面魔方总状态数只有 6 个，我把这 6 个状态“解压缩”展开 给各位看（借用乌木先生的图）！
<IMG border=0 src="http://bbs.mf8-china.com/data/attachment/forum/dvbbs/2005-5/200552911495060159.gif">
 再附上“正八面体的循环变换球面网”图，让大家对照理解！
<IMG border=0 src="http://bbs.mf8-china.com/data/attachment/forum/dvbbs/2005-5/2005530753795616.jpg">
 2×2 平面魔方有 4 种操作 U 、 D 、 L 、 R 。 2×2 平面魔方的“循环变换球面网” 为“正八面体的循环变换球面网”（如图）。
 请各位魔友注意，图中 A --> B 箭头表示：从 A 到 B 但还需要整体旋转后才能得到 B 。 图中不带箭头的可以互相转换；但带箭头的是不能互相转换的，转换后还需整体旋转。
 我们不妨分别用 U 、 U+ 、 U2 、 U- 表示（D 、 L 、 R 操作同理）： U 表示操作 U 后不需要再做整体旋转； U+ 表示操作 U 后再做顺时针整体旋转； U2 表示操作 U 后再做整体旋转 180 度； U- 表示操作 U 后再做逆时针整体旋转。

乌木发表于 2005-5-30 13:56:33

上午好像此处跟过帖，怎么看不到？再跟： 上面那网线改为经纬线，让它们也上球面来可能更好。 高维的东西能否尽量投影到三维，人脑易接受。

ggglgq 发表于 2005-5-31 09:14:44

下面再给出两个 2×2 平面魔方 24 态的关系网（它们不是“循环变换球面网”，因为 2×2 平面魔方 24 态“循环变换球面网”在三维空间中根本不存在，也就无法用三维空间 表示了。2×2 平面魔方 24 态“循环变换球面网”至少是一个四维空间的“球面网”。）
 noski 先生的 24 态图： 
<IMG border=0 src="http://bbs.mf8-china.com/data/attachment/forum/dvbbs/2005-5/200553111143517537.jpg">
 乌木先生的24 态的关系网：
<IMG border=0 src="http://bbs.mf8-china.com/data/attachment/forum/dvbbs/2005-5/20055301803042359.gif"> 
 noski 先生的 24 态图是乌木先生的图的改进版，它们能够间接体现“循环变换球面网”。
 因此 noski 先生的 24 态图已经是最好的用“三维立体图”构造“高维空间网”的表示 法了。但它不是 2×2 平面魔方 24 态“循环变换球面网”，而这个 24 态“循环变换球面网” 的确是存在的，不过是我们无法用“三维立体图” 表示罢了！因为三维空间根本不存在 24 个 顶点的正多面体！ 
[此贴子已经被作者于2005-6-1 12:29:46编辑过]

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

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