魔方吧·中文魔方俱乐部

标题: 回到最初，从52步的 Thistlethwaite 开始(2) [打印本页]

作者: aubell 时间: 2011-2-9 12:13:23 标题: 回到最初，从52步的 Thistlethwaite 开始(2)

要用c代码实现一个Thistlethwaite算法。
代码要尽量写的美观、工整，易读。
效率先不要求。

(1)表存储什么？
存储深度，状态转移，

(2)是否要把每个阶段的算法“统一”起来？
诸多简短的实现都使用了“统一”的搜索形式。四个阶段用一个search函数。
让函数根据参数判断是那个阶段的搜索。
因为，即使分开来写，也会发现，四个搜索函数的格式基本一样。
所以，大都倾向于“统一”形式。
可先分开写，然后法统一。

[ 本帖最后由 aubell 于 2011-2-12 17:06 编辑 ]

作者: aubell 时间: 2011-2-9 12:14:50

占楼备用。这一层写基础代码。总体分析等。

代码已经完工。待继续美化、优化以后陆续贴出。
其实很有些凌乱，要慢慢整理好看一点。

实现上，生成的表很大。每个int用了四个字节存储，总共用了大约 20M。
改进以后，每个int其实可以改成BYTE，由于存储深度值，不会太大。
这样可以把表缩小到 5M。

由于每一步深度值不会太大，肯定不会超过32，那么用5个bit就够了；
不过，这个增加运算复杂度，实在没必要这样压缩空间。

现在机器的内存那么大，诶，真觉得用所谓“对称”减小存储量没有必要了。
但如果能利用“对称”搜索更短的公式，倒是很有趣的。

发现当前的实现在G3进入G4的时候，不是简单的进入了G4，而是不小心进入
了G4的一个子集，角都处于还原状态了！这样增加了phase3的使用的步数，而phase4
的步数也没有降低。大约长了3步。

现在存在的问题是，初始运行，生成“深度表”的时间太长了，大约用了3-5分钟。
真不知道高人TomasSirgedas是如何用150行完成的Thistlethwaite的，而且没有什么
等待时间，没有外部的表。有空把他的代码解剖一下。

（那些高效的代码基本都是不“转”魔方的，而是直接“看”魔方的状态。
存储好像都不太用线性表，而用hash表。
）

功能模块：
1. 排列、组合同数字之间的转化
2. 可以转动的魔方
3. 魔方状态的设定和获取
4. 状态深度表
5. 状态查找函数

“设定”到特定状态导致魔方状态的“不完整”，
这种方法感觉稍别扭；
争取改“转动到”某些状态。
使得只有获取状态的函数，没有设定状态的函数。

对称好像真的很麻烦。
用“整体翻转”和“镜像”？

要解析jaap,pochman,TomasSirgedas三个人的代码，
自己的准备重写了。

5分钟的初始化时间，那三个程序都能解数以万计的
魔方了。

奇怪的是Parity好像没有单独处理也可以啊？
莫非Parity本来就不用单独处理？？

[ 本帖最后由 aubell 于 2011-2-12 16:18 编辑 ]

作者: aubell 时间: 2011-2-9 12:16:11

这一层要完成stage1。

作者: aubell 时间: 2011-2-9 12:18:00

这一层将要完成stage2。

作者: aubell 时间: 2011-2-9 12:20:24

这一层要完成stage3

作者: aubell 时间: 2011-2-9 12:21:54

这一层要完成stage4

作者: aubell 时间: 2011-2-9 12:23:32

这一层把1234粘和起来。
欢迎支持

作者: Xwam 时间: 2011-2-9 13:14:29

不太明白，等代码出来了。。。。

作者: 529160821 时间: 2011-2-9 13:51:07

等结果出来………………

作者: 奇趣屋toys 时间: 2011-2-9 13:58:37

我慢慢的等结果出来。

作者: aubell 时间: 2011-2-11 20:49:35

.我当前的程序同其它程序的比较：
第七届最少步还原赛
http://bbs.mf8-china.com/viewthread.php?tid=70304&extra=page%3D1
Scramble ：L2 R B2 D' B' R2 F2 U' B' L2 F L2 U2 L2 R' D B' R2 (18f)

Tomas Sirgedas
F' B2 R' D F B L' B2 U L D' B2 L U' F2 R2 U' R2 U L2 U' F2 D F2 L2 U2 F2 L2 F2 R2 B2 U2 ( 32 f )

Pochman
U' B' R D U2 F' U' B2 U F2 R D2 L' U2 B2 U' F2 B2 R2 U' B2 D F2 U' B2 U2 R2 U2 L2 F2 U2 F2 ( 32 f )

Jaap
D U F' U2 L B D2 L U2 L B2 R D' L D L2 D L2 B2 D B2 D' R2 U B2 U2 L2 B2 U2 F2 U2 F2 L2 F2 ( 34 f )

我的程序
L B U' R' D' B L2 U L U' L D R L2 U2 B2 U' R2 U B2 D2 R2 D' F2 L2 U2 L2 B2 U2 B2 F2 L2 F2 U2 F2 D2 ( 36 f )

要改进提高。因为“手动”的人们已经在25步徘徊了。

[ 本帖最后由 aubell 于 2011-2-11 20:51 编辑 ]

作者: aubell 时间: 2011-2-11 20:54:56

顺便奉劝手动的人们不要学习“Thistlethwaite“方法了。
因为初级的电脑程序才35步的水平。
除非真的可以手动 2-phase。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)