关于24同构

铯_猪哥恐鸣

不想浪费精力在翻译和翻译产生的歧义上，请看下面网页吧
http://kociemba.org/math/symmetries.htm

大致的解释就是，我们可以定义4种“基”对称变换（"basic" symmetries）：
S_URF3, a 120 degree         turn of the cube around an axis through the URF-corner and DBL-corner,
        S_F2, a 180 degree turn         of the cube around an axis through the F-center and B-center,
        S_U4, a 90 degree turn         of the cube around an axis through the U-center and the D-center
        S_LR2, a reflection at the RL-slice plane.
则所有的对称变换可以表示成
(S_URF3)x1 * (S_F2)x2 * (S_U4)x3 * (S_LR2)x4with x1 from 0..2, x2 from 0..1, x3 from 0..3 and x4 from 0..1.
这样就一共定义了48个变换，此处不妨记为S_0, S_1...S_47
那么某个变换A的对称变换们为
B_i = S_i^-1 A S_i
这样对于某个状态A，就定义了48个不同的状态B_i，它们就是我们说的A的48同构，或者同态（我不知道这两个名词是怎么来的，也不想争论到底用哪个名词，总之我们找到了48个变换）
最后，存在某些变换A，使得B_i = B_j。也就是说并不是每个变换都可以找到48个同构变换，但事实上确实只有少数状态存在少于48个变换，具体这些状态他那个网站里都有。

[ 本帖最后由 铯_猪哥恐鸣 于 2011-5-3 21:38 编辑 ]

铯_猪哥恐鸣

好的，很高兴您在线。
第一个问题：
96同构是怎么产生的：
不知道你有没有注意到，上面所说的四个基对称变换中没有逆变换，事实上，如果加上逆变换，那么就有96个所谓同构了，当然是否应该叫“同构”我自己也没有把握，暂且就这么叫了。
第二个问题：
如何证明相对于基态都有最短路径：
对于上述给出的S_0, S_1, ... S_47，容易证明，如果A为某一种转动（RUBLDF），则S_i ^-1 A S_i也是一种转动。这样就很容易证明同态对于基态都有同样的最短路径。

铯_猪哥恐鸣

手动写起来比较耗时间，久等了，包括UFL总共48个，请核对。
UFL
URF
UBR
ULB
RFU
RDF
RBD
RUB
BUL
BRU
BDR
BLD
DFR
DLF
DBL
DRB
FUR
FLU
FDL
FRD
LUF
LBU
LDB
LFD
U'F'R'
U'L'F'
U'B'L'
U'R'B'
L'F'U'
L'D'F'
L'B'D'
L'U'B'
B'U'R'
B'L'U'
B'D'L'
B'R'D'
D'F'L'
D'R'F'
D'B'R'
D'L'B'
F'U'L'
F'R'U'
F'D'R'
F'L'D'
R'U'F'
R'B'U'
R'D'B'
R'F'D'

[ 本帖最后由 铯_猪哥恐鸣 于 2011-5-3 22:20 编辑 ]

铯_猪哥恐鸣

17楼不就是48个等长公式吗？

铯_猪哥恐鸣

求逆的话，由于你给的公式的特殊性，所以确实找不到96个，这一点我前面应该提到了。比如如果你给的公式是UFLF，那么48个等长公式为：
UFLF
URFR
UBRB
ULBL
RFUF
RDFD
RBDB
RUBU
BULU
BRUR
BDRD
BLDL
DFRF
DLFL
DBLB
DRBR
FURU
FLUL
FDLD
FRDR
LUFU
LBUB
LDBD
LFDF
U'F'R'F‘
U'L'F'L’
U'B'L'B‘
U'R'B'R’
L'F'U'F‘
L'D'F'D’
L'B'D'B‘
L'U'B'U’
B'U'R'U‘
B'L'U'L’
B'D'L'D‘
B'R'D'R’
D'F'L'F‘
D'R'F'R’
D'B'R'B‘
D'L'B'L’
F'U'L'U‘
F'R'U'R’
F'D'R'D‘
F'L'D'L’
R'U'F'U‘
R'B'U'B’
R'D'B'D‘
R'F'D'F’

[ 本帖最后由 铯_猪哥恐鸣 于 2011-5-3 23:03 编辑 ]

铯_猪哥恐鸣

不是很理解你的意思，比如你给出UFLF，那么我根据你给定的公式给出了上面48个状态，再加上它们的逆状态，总共96个状态。

铯_猪哥恐鸣

是的，你说的没错，这就是我给出的那个网页中提到的sym-coordinate。它的做法是：For each equivalence class we store the smallest coordinate as the representant of this class in an integer array
另外通过那个网站我大致知道，事实上利用对称并不能直接减小搜索量，但可以直接减小剪枝表(pruning table)的大小，换句话说，用同样的内存可以做更大的剪枝表，提高搜索效率。

[ 本帖最后由 铯_猪哥恐鸣 于 2011-5-3 23:31 编辑 ]

铯_猪哥恐鸣

我已经写出了48个，另外48个是这48个的逆，并且这96个里面没有重复，很容易验证把。
公式F确实不可能构造出96个不同的状态，这个我完全同意，即便是公式RUF也只能构造出48个状态，这一点我前面就给出了解释，因为某些个构造重复了。

[ 本帖最后由 铯_猪哥恐鸣 于 2011-5-3 23:18 编辑 ]

铯_猪哥恐鸣

等长显然，都是4步，是否最短这个因为只有4步，所以很容易验证，事实上由于原公式可以通过某个S_i变换过去，那变换后的公式当然也能同样的变换回来，所以只要原公式是最短，则变换后的公式一定最短且和原公式一样长。
好的，对于给定的长度为n的公式A = A1A2A3...An，生成的第i个公式B_i = S_i^-1 A S_i = S_i^-1 A1 S_i    S_i^-1 A2 S_i   ...   S_i^-1 An S_i
由于A1, A2, ..., An都是基本旋转（RUFBLD等），所以S_i^-1 Ak S_i事先算好即可，不需要给出A再另外计算。
大师辛苦~

[ 本帖最后由 铯_猪哥恐鸣 于 2011-5-4 00:00 编辑 ]