魔方吧·中文魔方俱乐部

标题: 纠正错误，关于CE最少步算法 [打印本页]

作者: 铯_猪哥恐鸣 时间: 2010-3-9 11:01:51 标题: 纠正错误，关于CE最少步算法

在之前一篇帖子中，我根据某篇国外论文对魔方求解的研究，认为CE的最短步数算法是基于BFS思路的常规A*算法。但是昨天花了半个晚上的时间一行行分析了CE的核心代码（可能是前几年的版本）后发现原来所谓的IDA*算法就是纯BFS加减枝，当然大致的思路还是正确的。基于这点发现，在现在看来，其实CE所谓的IDA*算法和A*根本没什么关系，只是常规的减枝罢了，有理由相信很快就能找到一个更优的，基于用空间换时间的思想的算法。

名词解释：
BFS：广度优先搜索，优先搜索步数短的节点，即先尝试所有步数为1的状态，然后2，然后3等等。
DFS：深度优先搜索，优先进行下一步转动（就是先一通乱转），当然在搜索魔方的时候根据上一个帖子的说明限定了转动步数上限。
剪枝：即在搜索的过程中适当的放弃一些不可行的解。（比如已经转了24步了，那这个状态显然没有继续的必要了）

另注：关于对称性的研究，我所看的CE代码里面并没有处理搜索时碰到的对称性，我认为如果加上这块，程序的效率会提高48倍左右，当然具体还在思考中。
同时提出一个很久远的问题：有没有一个合适的状态表示方法，使得诸如RUR'与F'U'F这类对称的状态有些相同表示

作者: mengfl 时间: 2010-3-9 11:13:41

占楼，等会了再找。。。

作者: 溪风 时间: 2010-3-9 12:43:38

最少步还没学习。。。先看着

作者: superflip 时间: 2010-3-9 13:27:49

现在的CE版本肯定加了空间对称性，但是好像没有加inverse状态，应该还能很轻易的时间/2, 不过现在研究最小步为20步的那人已经做过了（如果我没记错）。

祝你早日找到更好的空间换时间的算法，期待~

作者: 铯_猪哥恐鸣 时间: 2010-3-9 16:54:06 标题: 回复 4# 的帖子

好像只是在初始化剪枝表的时候加了对称性的东西，具体搜索的时候我没看到有相关的代码。。。

作者: superflip 时间: 2010-3-9 17:39:29

我想我4#理解错了你的意思，是的，CE应该只是利用对称简化了table的大小，在搜索时没有利用对称性对扩展节点的动作取舍，你可以试着做，估计会很难，而且离增加48效率差很远。

作者: 铯_猪哥恐鸣 时间: 2010-3-9 18:19:32 标题: 回复 6# 的帖子

我已经想到一个可以在扩展时候就考虑对称性的一个算法了，只不过效率不会有48倍那么多，但是5-6倍的效率应该还是有的

作者: Paracel_007 时间: 2010-3-9 18:25:59

论坛里能看懂这个的绝对极少数。。。
我会用。。。剩下的不懂。。。

作者: superflip 时间: 2010-3-9 20:08:46 标题: 回复 7# 的帖子

这么快，可否说一下大概思想。

我看了下CE的help，怎么又觉得它用table包含对称性已经足够用了，基本可以去除对重复的对称空间的搜索。

我认为做更好的table更实际些，比如：保存多个相关性小，用不同方式得到的table，以满足各种 ”判断困难“ 情况。

ps：是否把此帖转到 “最小步区“ 更合适，让那里的大牛指导一下理论。

作者: 铯_猪哥恐鸣 时间: 2010-3-9 20:41:59 标题: 回复 9# 的帖子

他那个说明书里的东西其实和代码完全不同的。。我看了好几天说明书差点被误导。。后来一行行分析算法才恍然大悟。。。

作者: superflip 时间: 2010-3-9 22:02:33 标题: 回复 10# 的帖子

你不会看的是他网页给的简易算法实现吧，我觉得他的help写的非常好啊，实际版本应该就是照这思路做的，他没有必要瞎说啊~

你能说说help哪里说法不对吗？共同探讨。

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