本文主要是介绍一些笔记自己备忘，魔方最少步数的起点：Thistlethwaite‘s algorithm算法的引理。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前置：
1. w : 是一个映射，（但是不满足同态性质），类型是：H→ C2^(12)， w(g)第i个分量wi表示：
在第i位置的原坐标下，按逆时针计算的方向数为Fi，这个棱块x，经过某{F,B,L,R,U,D}某复合一个操作后，到达了第j位置
在新的第j位置的坐标下，按逆时针计算的方向数Fj,则这两个数之间的关系是：(Fi + wi) 再mod 3 ， 就等于 Fj。也就是Fi+wi=Fj (mod 2环境下)
换句话说wi是一个过程量，原位置下计数为Fi,新位置下计数为(Fi+wi) (mod2)。
换句话说，我在未变换前的方向数知道了Fi，然后查表找到这个变换前位置的分量wi，就知道了变换后原方块在新位置的方向数是多少了。
2. v : 是一个映射，（但是不满足同态性质），类型是：H→ C3^(8) ， v(g)第i个分量vi表示：
在第i位置的原坐标下，按逆时针计算的方向数为Fi，这个棱块x，经过某{F,B,L,R,U,D}某复合一个操作后，到达了第j位置
在新的第j位置的坐标下，按逆时针计算的方向数Fj,则这两个数之间的关系是：(Fi + vi) 再mod 3 ， 就等于 Fj。也就是Fi+vi=Fj (mod 3环境下)
换句话说vi是一个过程量，原位置下计数为Fi,新位置下计数为(Fi+vi) (mod3)。
换句话说，我在未变换前的方向数知道了Fi，然后查表找到这个变换前位置的分量vi，就知道了变换后原方块在新位置的方向数是多少了。
3.v : 不是同态,代表方向 H→ C3^(8)
4.ρ : 是一个同态映射,代表位置 类型是：H→ SV
5.w : 不是同态,代表方向 H→ C2^(12)
6.σ : 是一个同态映射,代表位置 类型是：H→ SE
7. H：是全体魔方状态的集合，不同于魔方群G，群H包括不可还原和可还原的状态。（换句话说，可以拆开魔方，但是不能撕贴纸！）
8.SE :是一个群，里面的元素是12排列代表的向量，代表棱块的位置变换的全体， 由于E代表棱块一共12个，所以SE等价于S12。
9.SV :是一个群，里面的元素是8排列代表的向量，代表角块的位置变换的全体， 由于V代表棱块一共8个，所以SV等价于S8。
命题：
w(gh) := w(g) + σ(g)^(-1)·w(h)
v(gh) := v(g) + ρ(g)^(-1)·v(h)
证明：（思路是一般化某个任意分量来做变化，是否成立。再推广到所有分量。）
已知g：{
方向过程量：w(g)= (p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12)
位置过程量：σ(g)
}
已知h：{
方向过程量：w(h)= (q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12)
位置过程量：σ(h)
}
1.先证明第一条公式：
对于某个状态Sta1：
方向绝对量：Sta1 = (j1,j2,j3,j4,j5,j6,j7,j8,j9,j10,j11,j12)
位置绝对量：(k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12)
1.经过g作用后：{
方向绝对量错误：(j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12)
方向过程量：Sta1 → (Sta1作用g以后) = w(g)
位置：σ(g)·(k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12)= ?
方向绝对量 : σ(g)·(j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12)
}
2.再经过h作用后：{
方向绝对量：σ(h)( σ(g)·(j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12) + (q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12) )
方向过程量：（Sta1作用g以后）→ (Sta1作用g以后,再作用h以后) = ？
位置：σ(h)·σ(g)·(k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12)= ？
}
小引理：绝对方向量A1 经过x→, 绝对方向量为A2， 和w(x)有什么关系，如何表达w(x):
σ(x)·(A1 + w(x)) = A2
所以,w(x) = (σ(x))^(-1)·A2 - A1
分析初始方向绝对量和最后2次作用后的方向绝对量,后者是按定义算出来的值。
(j1,j2,j3,j4,j5,j6,j7,j8,j9,j10,j11,j12) = "A1"
→
σ(h)( σ(g)·(j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12) + (q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12) )
= σ(h)·σ(g)·(j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12) + σ(h)·(q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12)
= "A2"
所以复合的方向过程量：
w(gh) := (σ(gh))^(-1)·A2 - A1 = (σ(g))^(-1)·σ(h)^(-1) · A2 - A1
= (j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12) +
(σ(g))^(-1)·(q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12) - (j1,j2,j3,j4,j5,j6,j7,j8,j9,j10,j11,j12)
= (p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12) + (σ(g))^(-1)·(q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12)
试着列举一下：
w(g) = (p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12)
σ(g)·w(h) = σ(g)·(q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12)
w(g) + σ(g)·w(h) = (p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12) + (σ(g))^(-1)·(q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12)
举例说明：
g=F,h=R,
经过gh后，
已知：
因为g换位效果是:
{1,2,3,4,5,6,7,8}
{8,2,1,4,3,6,7,5}
因为h换位效果是:
{1,2,3,4,5,6,7,8}
{2,4,1,3,5,6,7,8}
gh复合换位：
{1,2,3,4,5,6,7,8}
{2,4,8,1,3,6,7,5}
v(g) = {2,0,1,0,2,0,0,1}
v(h) = {1,2,2,1,0,0,0,0}
-- 首先根据等式左边算一下，也就是根据定义算一下：
gh变换后绝对位置 =(0先经过g操作：加v(g),然后被ρ(g)作用) = {2,0,1,0,2,0,0,1} = {1,0,2,0,1,0,0,2}
=(经过h操作：加v(h),然后被ρ(h)作用) = {2,2,1,1,1,0,0,2} = {2,1,2,1,1,0,0,2}
v(gh) = (σ(gh))^(-1)·A2 - A1 = ?
这里A1 = 0, A2 = {2,1,2,1,1,0,0,2} ,
σ(gh) = {2,4,8,1,3,6,7,5} ,
σ(gh)^(-1) = {4,1,5,2,8,6,7,3}
v(gh) = {4,1,5,2,8,6,7,3} · {2,1,2,1,1,0,0,2} - 0
= {1,2,1,1,2,0,0,2}！！！对啦！！
-- 下面通过等式右边算一下：
σ(g)(v)(h)= σ(g)·v(h) = 就是按照g的换位来更改这些v(h)中的分量，
= {0,2,1,1,2,0,0,0}
v(g) + σ(g)(v)(h)= σ(g)·v(h) = {2,0,1,0,2,0,0,1} +
{0,2,1,1,2,0,0,0}
= {2,2,2,1,1,0,0,1}
(σ(g))^(-1)·v(h) = {2,2,0,1,0,0,0,1}
v(g) + (σ(g))^(-1)·v(h) = {2,0,1,0,2,0,0,1} +
{2,2,0,1,0,0,0,1}
= {1,2,1,1,2,0,0,2}！！！对啦！！
这篇关于一些笔记自己备忘，魔方最少步数的起点：Thistlethwaite‘s algorithm算法的引理。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
