三、置换与等价

置换 -- 魔方的空间摆放方式有24种。每种方式对应唯一一种面之间的置换。由于(u,v,w)总是(x,y,z)的反方向，所以只要确定(x,y,z)的置换即可。以某一面着地时第一象限的三个轴标记为：

(yzx, zvx, vwx, wyx, // u面着地

zxy, xwy, wuy, uzy, // v面着地

xyz, yuz, uvz, vxz, // w面着地

zyu, ywu, wvu, vzu, // x面着地

xzv, zuv, uwv, wxv, // y面着地

yxw, xvw, vuw, uyw) // z面着地

所有置换构成置换群。其中L[xyz]为1元。

状态的等价关系 -- 对于魔方的两个状态S与T，如果存在一个置换L，使得 S*L = T 则称S与T等价。

动作的相似关系 -- 对于魔方的两个动作A与B，如果存在一个置换L，使得

S[0]*A = S[0]*L*B 则称A与B相似。

四、算法的优化

一个状态集S，为每个元素配一个深度指标。

1、 加入初始状态S[0]，深度为0。

2、 对S中每个新加入的元素，执行18个基本动作。

3、 对每个动作的结果，如果不与S中任何元素等价，则加入S之中，深度为被操作对象的深度加1。

4、 反复执行2到3，直到S不再增长为止。

对于魔方的一个状态S[i]，查找上述状态表中与之等价的状态，得到深度d执行18个基本动作，一定至少有一个动作的结果，其等价状态的深度为d-1，确认该动作为一步。反复尝试和确认，一定能够到达初始状态S[0]。

引入置换和等价关系，实际上是以时间换空间。因为这个算法的主要问题是空间开销太大，所以这种平衡是值得的。

五、算法的实现

我还没有真正动手做，仅仅提供一点建议吧。

1、 可以用0,1,2,3,4,5表示6种颜色。6个32位整数表示一个状态。每个整数表示一个面。整数中每三位表示一个色块。

2、 用32位整数表示深度应当足够了。

3、 调试时可以先选择三个基本动作，通过后再选择六个基本动作，这样一步步扩大。

六、其他

各种智能算法的评价函数可不可以用对状态表的统计分析的方法得到?

高中趣味数学就为大家介绍到这里，希望对你有所帮助。

相关推荐：

高中数学学习方法趣味诗精编

高中生趣味数学：猫捉老鼠