纠正错误，关于CE最少步算法
在之前一篇帖子中，我根据某篇国外论文对魔方求解的研究，认为CE的最短步数算法是基于BFS思路的常规A*算法。但是昨天花了半个晚上的时间一行行分析了CE的核心代码（可能是前几年的版本）后发现原来所谓的IDA*算法就是纯BFS加减枝，当然大致的思路还是正确的。基于这点发现，在现在看来，其实CE所谓的IDA*算法和A*根本没什么关系，只是常规的减枝罢了，有理由相信很快就能找到一个更优的，基于用空间换时间的思想的算法。名词解释：
BFS：广度优先搜索，优先搜索步数短的节点，即先尝试所有步数为1的状态，然后2，然后3等等。
DFS：深度优先搜索，优先进行下一步转动（就是先一通乱转），当然在搜索魔方的时候根据上一个帖子的说明限定了转动步数上限。
剪枝：即在搜索的过程中适当的放弃一些不可行的解。（比如已经转了24步了，那这个状态显然没有继续的必要了）
另注：关于对称性的研究，我所看的CE代码里面并没有处理搜索时碰到的对称性，我认为如果加上这块，程序的效率会提高48倍左右，当然具体还在思考中。
同时提出一个很久远的问题：有没有一个合适的状态表示方法，使得诸如RUR'与F'U'F这类对称的状态有些相同表示 占楼，等会了再找。。。 最少步还没学习。。。 先看着 现在的CE版本肯定加了空间对称性，但是好像没有加inverse状态，应该还能很轻易的时间/2, 不过现在研究最小步为20步的那人已经做过了（如果我没记错）。
祝你早日找到更好的空间换时间的算法，期待~
回复 4# 的帖子
好像只是在初始化剪枝表的时候加了对称性的东西，具体搜索的时候我没看到有相关的代码。。。 我想我4#理解错了你的意思，是的，CE应该只是利用对称简化了table的大小，在搜索时没有利用对称性对扩展节点的动作取舍，你可以试着做，估计会很难，而且离增加48效率差很远。回复 6# 的帖子
我已经想到一个可以在扩展时候就考虑对称性的一个算法了，只不过效率不会有48倍那么多，但是5-6倍的效率应该还是有的 论坛里能看懂这个的绝对极少数。。。我会用。。。剩下的不懂。。。
回复 7# 的帖子
这么快，可否说一下大概思想。我看了下CE的help，怎么又觉得它用table包含对称性已经足够用了，基本可以去除对重复的对称空间的搜索。
我认为做更好的table更实际些，比如：保存多个相关性小，用不同方式得到的table，以满足各种 ”判断困难“ 情况。
ps：是否把此帖转到 “最小步区“ 更合适，让那里的大牛指导一下理论。
回复 9# 的帖子
他那个说明书里的东西其实和代码完全不同的。。我看了好几天说明书差点被误导。。后来一行行分析算法才恍然大悟。。。
页:
[1]
2