[原创]基于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编辑过]