[注意] 两阶段搜索算法

ggglgq

以下是引用cube_master在2005-3-20 14:01:14的发言：

(2005-03-20 13:48:02) roundy(811416) 我的一个心愿:能集合魔方吧大集体的力量做一个工具:她有强劲高效的算法引擎,然后有漂亮的渲染3d引擎.可换壳.功能多样,可以帮助大家找最优解.找某个算法的多种解法供自己挑选最适合自己手感的方法.可以做为一个教练训练大家玩魔方.....

支持，roundy 的心愿也是所有魔友的心愿！

ggglgq

roundy 先生您好：

很长时间未光顾“魔方吧”了，今欣喜地看到 roundy 先生依据 Two-Phase-Algorithm 算法开发出国产的“正六面体三阶魔方”最少步软件，真是可喜可贺呀！我谨在此向 roundy 先生表示衷心地祝贺！

没有太多的时间仔细看和测试，感觉您对 Two-Phase-Algorithm 算法已经融会贯通了， 并且试着用它开发出很棒的三阶魔方最少步软件。下面谈谈我的一些个人看法 （信口胡说， 若有说的不对的地方还望 roundy 先生补充更正）：

1、您的“正六面体三阶魔方”最少步程序很干练，很精巧；

2、程序初始化的库很小，因此在处理步数较少的状态时速度很快；

在国外研究 Two-Phase-Algorithm 算法的人很多，其中研究高效快速的“估价函数” 是重中之重！因为面对“三阶魔方天文数字的状态”蛮算是不行的！尤其对于步数较多的 状态！比如要找“三阶魔方的最远状态”无论任何算法都要先进行“评估优化”！

能够胜任 Two-Phase-Algorithm 算法的人，必然能够掌握和胜任“循环变换算法”。 因为我很忙没太多时间研究算法和编程，因此我把我的“循环变换算法”在论坛上发表以 期待能有像您这样的程序员一起去研究完善，并运用其编程！ “循环变换算法”在“正六面体三阶魔方”运用时如果只考虑旋转 90 度为单步长，而 旋转 180 度为两步长，在此基础上得到正六面体三阶魔方“循环变换”的步数和 [或长度] 为偶数！这一点非常重要：我们就没必要考虑长度为奇数的循环变换，从而简化了编程。 当然，对于旋转 180 度为单步长，“循环变换算法”应该没有太大的问题。不知您对 此持怎样的看法 ？

ggglgq

补充 roundy 先生的原创最少步软件：

roundy 先生的原创最少步软件: http://bbs.rbook.net/UploadFile/2006-2/20062288395489694.rar

ggglgq

以下是引用大烟头在2005-3-20 14:24:21的发言：

最后举个例子让大家体会上面所说的内容.用步法D2 F2 L2 B2 U B2 U L' F R2 D2 U2 L D2 B' U F' R2 U2打乱一个已复原六面的魔方,然后使用cube explorer求出解法U2 R2 F U' B D2 L' U2 D2 R2 F' L U' B2 U' B2 L2 F2 D2 .我们可以看到,整个解法可以分为两步 (U2 R2 F U' B D2 L' U2 D2 R2 F' L)*(U' B2 U' B2 L2 F2 D2),你可以尝试在'*'号的位置停下来看一看整个魔方的状态,加深一下对这个算法的感性认识.

建议大家可以把 D2 F2 L2 B2 U B2 U L' F R2 D2 U2 L D2 B' U F' R2 U2 换成
D2 F2 L2 B2 U B2 U L' F L2 U2 D2 R2 L' D2 B' U F' R2 U2 再试试，程序运行要
等一段时间的。

或者 在 D2 F2 L2 B2 U B2 U L' F R2 D2 U2 L D2 B' U F' R2 U2 中随意插一些
循环变换，广义循环变换 等等，没什么大问题的。

ggglgq

 

    当前的两阶段搜索算法并不能在所有的情况下都找到最优解，在这种情况下我们必须
倒回头，继续再做一次 2 阶段搜索，这会增加很多的时间。如果确实需要优化一些情况，对于
Cube Explorer 您可以使用“优化”(Optimal) 选项。