荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: fengzhiying (风之影), 信区: CMCS
标 题: 魔方解法的一点想法(转载)
发信站: 荔园晨风BBS站 (Fri Dec 8 15:47:08 2006), 站内
一、概念
面(face) -- 魔方有6个面，分别标为(u,v,w,x,y,z)，其中(u,v,w)分别是
(x,y,z)的反方向。
状态(status) -- 魔方的所有可能的不同色块排列。一般的表示为S[i]。
初始状态(S[0]) -- 魔方6面各自同色的状态。
动作(action) -- 迎着每一个面有左转90度(left)，转180度(opsite)，右转
90度(right)等3种操作，共18种基本动作。分别标为：
(ul, uo, ur,
vl, vo, vr,
wl, wo, wr,
xl, xo, xr,
yl, yo, yr,
zl, zo, zr)
先执行动作A，再执行动作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]。
状态集S中元素个数的估计：六个面的中心点不因动作而变化，8个顶点与12
个棱，应当有 8!*12! 约50M个状态。虽然顶点和棱在位置上还有自由度，但是顶
点和棱之间也有相互的约束关系。我不能定量地计算各自的程度，但是我觉得PC
机的计算能力应当可以对付，至少值得一试。
三、置换与等价
置换 -- 魔方的空间摆放方式有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、调试时可以先选择三个基本动作，通过后再选择六个基本动作，这样一步
步扩大。
六、其他
各种智能算法的评价函数可不可以用对状态表的统计分析的方法得到？
--
假如给多奶奶一秒钟，我想再对奶奶说：“我爱你”。
假如给多奶奶一分钟，我想再拉拉奶奶的手。
假如给多奶奶一小时，我想再听奶奶给我讲故事。
假如给多奶奶一天 ，我想再陪奶奶去逛逛街；到市场去买菜，再吃奶奶煮的饭菜。
假如给多奶奶一个月，我很想陪奶奶去游览祖国秀美山河。
假如给多奶奶一年 ，我一定好好听奶奶的话认认真真的读书。
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 218.17.74.57]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店