四、对称
魔方是一个高度对称的物体，我们可以利用对称性来减少时间空间上的开销。
对称的形式有 4 种基本情况，原本状态，只颜色变化，只位置变化，镜像。
它们都是等价的，如果我们能解决其中一个，就能解决其他的，只要在解法上加上相应的对称变化即可。
来看一个同位置不同颜色的例子，看看原状态经过怎样的变化后得到的一种等价状态：
假如对还原状态的魔方进行 A(一个转动序列) 操作得到如下状态：
我们要得到它的一个等价状态，进行如下操作，还原状态先绕 UD 轴逆时针转动 90°，再做 A 操作，最后绕 UD 轴顺时针转动 90°。
看到这大家有没有联想到什么，是不是很像矩阵的相似变换，有一些还原算法就是把魔方存成矩阵的形式，魔方变换就是相应的矩阵变换，道理都是相通的。
Ⅰ 对称变换
① 基本变换
上述的一些等价形式都是通过对称变换得来的，对于每个状态加上自己有 48 种变换形式，一般来说每个状态也就有 48 种等价形式，它们都是由 4 种“基本对称”组合而成：
1. S_U4：围绕 UD 这个轴转动 90°，4 种
2. S_F2：围绕 FD 这个轴转动 180°，2 种
3. S_URF3：围绕 URF 这个角块转动120°，3 种
4. S_LR2：关于 LR 层的镜像，2 种
合起来 4*2*3*2=48 种
具体怎么转动的我就不具体画图表示了(唉主要是变换的 3D 制图太难了，尝试了一下，效果不好，见谅)，既然是变换操作，所以对称变换还是可以用状态的块层次来表示，具体来看 4 种基本对称变换的定义，从块的替代关系中应该就能理解具体是怎么变换的了。
48 种对称变换操作初始化也很容易，4 个 for 循环，调用 multiply 函数进行复合操作，得到的结果填到 symCube[48] 数组里面去，这里就不赘述重复操作了。
注意上面的镜像变换，定义角块方向变化全部加 3 ，也就是说镜像的角块方向取值为 [3,5]。
② 逆变换
上述为了得到等价状态做了两次对称变换，两种变换互为逆过程，群论里面叫做互为逆元，我们这需要为每一个对称变换找到它们对应的逆变换。
那怎么得到相应的逆变换？在群论里面互逆的两个元素复合操作等于幺元，也就是相当于乘法里面的互为倒数的两个数相乘为 1，而在魔方里面还原状态就是幺元就是那个 1 。所以我们只要对 48 个变换进行两两复合操作，看结果是否达到还原状态即可。
Ⅱ 等价
因此对于每种状态我们只需要记录属于哪一个集合(行号)，所使用的对称变换(列号) ，这么一个集合我们称为等价类。如此一来就可以省下很多空间和时间，因为存的信息少了，搜索的状态空间也少了。在科先巴的二阶段算法里，保持了 UD 轴不动，所以只用到了 16 种对称变换。
加入一个状态属于等价类 y ，使用的对称变换为 i，那么我们就可以用新坐标 y*16+i 来描述原状态。但是并不是每个等价类里面都有不同的 16 种状态，也就是说不是每个状态都有 16 种不同对称状态。比如说有等价类 y y 和对称变换 i，j，y*16+i 与 y*16+j 是有可能描述的同一个状态的。这个在后面剪枝部分还会再说明
关键问题在于我们如何得知一个坐标它属于哪一个等价类，使用的是哪一个对称变换？直接来看伪码分析：
Ⅲ 对称变换表
上述的代码里面已经使用过了，类似前面的转动表，对称变换，转动都是变换操作，转动有转动表，对称变换也得有相应的变换表。比如定义以下的表：
具体的初始化操作同转动表，都是建立在状态的复合操作之上，以角块方向的对称变换表举例说明：
源程序里面命名用的是 conjugate 这个词，共轭，我这儿直接用的 Sym 来说明，私以为可能更直观一些。
这部分讲述对称性，根据篇一种计算的状态数我们知道，一个三阶魔方的状态数多到爆炸，但还好魔方是个高度对称的物体，我们可以使用对称性来减少计算量。下一部分算法核心：剪枝
魔方是一个高度对称的物体，我们可以利用对称性来减少时间空间上的开销。
对称的形式有 4 种基本情况，原本状态，只颜色变化，只位置变化，镜像。
它们都是等价的，如果我们能解决其中一个，就能解决其他的，只要在解法上加上相应的对称变化即可。
来看一个同位置不同颜色的例子，看看原状态经过怎样的变化后得到的一种等价状态：
假如对还原状态的魔方进行 A(一个转动序列) 操作得到如下状态：
我们要得到它的一个等价状态，进行如下操作，还原状态先绕 UD 轴逆时针转动 90°，再做 A 操作，最后绕 UD 轴顺时针转动 90°。
看到这大家有没有联想到什么，是不是很像矩阵的相似变换，有一些还原算法就是把魔方存成矩阵的形式，魔方变换就是相应的矩阵变换，道理都是相通的。
Ⅰ 对称变换
① 基本变换
上述的一些等价形式都是通过对称变换得来的，对于每个状态加上自己有 48 种变换形式，一般来说每个状态也就有 48 种等价形式，它们都是由 4 种“基本对称”组合而成：
1. S_U4：围绕 UD 这个轴转动 90°，4 种
2. S_F2：围绕 FD 这个轴转动 180°，2 种
3. S_URF3：围绕 URF 这个角块转动120°，3 种
4. S_LR2：关于 LR 层的镜像，2 种
合起来 4*2*3*2=48 种
具体怎么转动的我就不具体画图表示了(唉主要是变换的 3D 制图太难了，尝试了一下，效果不好，见谅)，既然是变换操作，所以对称变换还是可以用状态的块层次来表示，具体来看 4 种基本对称变换的定义，从块的替代关系中应该就能理解具体是怎么变换的了。
48 种对称变换操作初始化也很容易，4 个 for 循环，调用 multiply 函数进行复合操作，得到的结果填到 symCube[48] 数组里面去，这里就不赘述重复操作了。
注意上面的镜像变换，定义角块方向变化全部加 3 ，也就是说镜像的角块方向取值为 [3,5]。
② 逆变换
上述为了得到等价状态做了两次对称变换，两种变换互为逆过程，群论里面叫做互为逆元，我们这需要为每一个对称变换找到它们对应的逆变换。
那怎么得到相应的逆变换？在群论里面互逆的两个元素复合操作等于幺元，也就是相当于乘法里面的互为倒数的两个数相乘为 1，而在魔方里面还原状态就是幺元就是那个 1 。所以我们只要对 48 个变换进行两两复合操作，看结果是否达到还原状态即可。
Ⅱ 等价
因此对于每种状态我们只需要记录属于哪一个集合(行号)，所使用的对称变换(列号) ，这么一个集合我们称为等价类。如此一来就可以省下很多空间和时间，因为存的信息少了，搜索的状态空间也少了。在科先巴的二阶段算法里，保持了 UD 轴不动，所以只用到了 16 种对称变换。
加入一个状态属于等价类 y ，使用的对称变换为 i，那么我们就可以用新坐标 y*16+i 来描述原状态。但是并不是每个等价类里面都有不同的 16 种状态，也就是说不是每个状态都有 16 种不同对称状态。比如说有等价类 y y 和对称变换 i，j，y*16+i 与 y*16+j 是有可能描述的同一个状态的。这个在后面剪枝部分还会再说明
关键问题在于我们如何得知一个坐标它属于哪一个等价类，使用的是哪一个对称变换？直接来看伪码分析：
Ⅲ 对称变换表
上述的代码里面已经使用过了，类似前面的转动表，对称变换，转动都是变换操作，转动有转动表，对称变换也得有相应的变换表。比如定义以下的表：
具体的初始化操作同转动表，都是建立在状态的复合操作之上，以角块方向的对称变换表举例说明：
源程序里面命名用的是 conjugate 这个词，共轭，我这儿直接用的 Sym 来说明，私以为可能更直观一些。
这部分讲述对称性，根据篇一种计算的状态数我们知道，一个三阶魔方的状态数多到爆炸，但还好魔方是个高度对称的物体，我们可以使用对称性来减少计算量。下一部分算法核心：剪枝
