[原创]基于N阶定律的魔方复原算法分析:第一版(完成于西藏)

pengw

魔方复原算法分析

-------------------------------------------------
1 穷举复原法
1.1 初始设定
起始图案:特定的任意非复原图案,称为A
目标图案:复原图案,称为B
1.2 操作目标
找出A到B的最短复原步数
1.3 复原方法
* 假定A能在N步内复原
* 偿试N步在另一个B图案魔方六个面的不同分配方式
* 如果N步的一个分配方式再现了A,则此分配方式的逆序就是A图的复原步骤，再用N-1步递归调用第二步，直至找到最小分配方式
* 如果N步的所有分配方式不能再现B，则用N+1步递归调用第二步，直至找到再现B的分配方式
* 这也是当前唯一可行的最优算法
1.4 算法优点
算法结构简单，保证找出最短步数
1.5 算法缺点
耗时长，技术含量最低
对四阶以上高阶魔方来说，无疑是挑战宇宙年龄
2 顺序复原法
2.1 初始设定
起始图案:特定的任意非复原图案,称为A
目标图案:复原图案,称为B
2.2 操作目标
找出A到B的转换步骤
2.3 复原方法
将魔方每层块进行排序,逐层逐块对魔方块进行块归位,这种算法要求编排每个块可能状态对应的公式序列,依据块的当前状态选择合适的公式实施块复位,最后将所有块复位的公式按顺拼接在一起就是一个特定图案的复原步骤
2.4 算法优点
* 算法构造容易，组织结构非常清淅
* 特适合初学编程新手及教学之用,本人十六年前做的第一个成功三阶复算法就是这种方法
* 公式数据可手工采集组织,可随时更新
2.5 算法缺点
* 公式数据采集量大,校对工作量大,需要一定的检索公式的技巧
* 一个公式对应块的一个状态,对三阶而言,复位第一个边角块需要求23组对应工式,复位第二个边角块需要20组对应个公式,复位第七个边角块须要2组公式,中棱块情况大至相同.
* 对四阶以上高阶魔方最上层边棱块错误(有一个边的所有边棱块二二互换了位置)的处理,要对最上层以下的所有n-1个内层实施90度转动,然后再对这n-1个内层逐块重复实施非扰动归位(即归位方法不再适成新的边棱块二二互换),最后才对最上层实施逐块归位
* 显然,这种方法到最上层才会发现边棱块错误,处理完边棱块错误后,又重复处理n-1个内层块的复位问题,且处理量不小.
* 对高阶魔方，手工编制公式数据不现实
* 极不适合步法优化.
2.6 附带特性
* 用块对应的公式组进行组合，可算出魔方的所有组合状态
* 在复原过程中即可判断出魔方的组装错误及错误类型
3 定律复原法
3.1 初始设定
起始图案:特定的任意非复原图案,称为A
目标图案:复原图案,称为B
3.2 操作目标
找出A到B的实现步骤
3.3 复原方法
* 从簇间关系的角度,找出A图案当前存在的非零态扰动关系并将其消解为零态扰动关系
* 仅用簇内变换规则对各块实施复位
3.4 算法优点
* 概念清淅
* 没有混沌的感觉,没有重复
* 构造算法容易
* 特别适合电脑处理
* 公式极少
* 特别适合高阶魔方还原
3.5 算法缺点
1. 对N阶定律要有非常透彻的理解
2. 特别不适合手工玩家复原，玩家应有鹰一样的视觉,内存条记忆的准确性
3. 可优化性差
4 经验复原法
4.1 初始设定
起始图案:特定的任意非复原图案,称为A
目标图案:复原图案,称为B
4.2 操作目标
找出A到B的复原步数
4.3 复原方法
通过对魔方当前状态的判断，应用已熟记的大量经验公式，对魔方实施复原
4.4 算法优点
速度快，平均优化效果相对较好
是一种折中性能最好的方法
4.5 算法缺点
* 算法设计不易，结构复杂，组织性差
* 手工操作，玩家需要记住大量经验公式，对玩家的记性与反应有极高的要求
* 严重依赖个人经验
* 不适合四阶以上高阶魔方求解处理
-------------------------------------------------------

忍冬:完成于西藏拉萨,布达拉宫脚下

2005年月4月14日

[此贴子已经被作者于2006-11-8 6:44:41编辑过]

黑白子

定律复原法好像是说分簇复原法，即消除簇间关系，用簇内变换还原。
感觉全文似乎在论述计算机复原法，不像是人工复原法。

大东东

让电脑用CFOP的解法还原没有任何的意义   追求20步内还原   步数真的是个问题  你就是让电脑穷举所有的步骤要很长时间的   就一般的电脑估计地球灭亡N+1次了   那验证是用超级计算机完成的   不过遇到一个数学天才  难说了   至少我尝试过   我的电脑在有限的时间内   利用穷举是没法解出来的

乌木

你说的“不采用任何参照”恐怕是指以魔方的周围环境为参照吧？这时候，哪怕通常说的复原态也应该因不同取向而呈现出24种状态。这说明前提、条件不同时，看起来结论大不同，实际还是有共同点的。这里决无什么“人一转身变成猴子”之类的事情，人转身只是显示其某侧面而已。不同前提、条件的处理方法适用的场合不同嘛，不必相互排斥、不共戴天的啊！

earthengine

原帖由 <i>乌木</i> 于 2005-12-12 17:39 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=16319&amp;ptid=790" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
看了17楼爱因斯坦兄的说法，启发我有个想法。任一乱态魔方的
任一块都可作为复原基准，好像晶体生长的晶种似的。这种玩法
颇有趣，也不难。现有的许多复原法不一定用同一种基准，多数
以六个中心块为基准，直观、 ...

<br>你这个想法很正确。由于立方体魔方的“整体翻转”有24种状态，因此不采用任何参照时，总状态数总是翻了24倍。当采用任意块作为参照时，总状态数就总是减少到24分之一。因此，这个块在允许整体翻转的情况下必然可以到达24种不同的位态（位置＋方向）。这就证明了公式 位置数*方向数＝24这个定理。<br>

清道夫2

欲哭无泪

ggglgq

呵呵， 有点“三战吕布”的味道。[em01]

乌木

看了17楼爱因斯坦兄的说法，启发我有个想法。任一乱态魔方的

任一块都可作为复原基准，好像晶体生长的晶种似的。这种玩法

颇有趣，也不难。现有的许多复原法不一定用同一种基准，多数

以六个中心块为基准，直观、方便。从道理上往开里想，任何合法

状态都是某一态（比如六面复原态）这一转那一转如此这般得来的；

设想我不在魔方外看它如此这般折腾，我缩小到躲在“任一舱”－－

任一魔方块－－内部，只见舱外群魔乱舞，完了，我让它们逆过来舞，

或者按别的优化的路线舞，不就可以复原的吗？在舱内看，完全可以

把本舱当作不动的“基准”的嘛。

[此贴子已经被作者于2005-12-12 17:40:25编辑过]

爱因斯坦

就这样比较,看到位置与色向与复原态一致的就是复原的,否则就不是.

比如图中明显有一个角块就是复原的,而中心块明显就没有复原.

这里的复原就是严格的位置与色向的复原,是真正严格的复原.

而一般的复原仅是相对的复原.不是太严格.

大家初步算出来的状态数都是严格的全状态数.

除以24就得到相对状态数,也就是大家常说的状态数.

大烟头

一个打乱的魔方以一个复原态的魔方做参照比较，要如何比较啊？

就拿忍大师来讲吧，奇阶魔方他会以两魔方中心块相对位置来作参照比较。偶阶的咋办啊？

N阶魔方还是以其中一个角块为参照点为好啊，不管奇阶魔方还是偶阶魔方它们都有角块的。

[em01]