cube-explorer核心算法

风流沙驼

讨论下，我尽量使用LZ所表述的语言来表述我的看法。
我之前写过A*，刚才看了看IDA*，感觉LZ把A*和IDA*搞混了。
1.队列是用在广度优先搜索（BPS）中的，使用BPS遍历树节点时，遍历节点根据遍历的先后顺序依次入队，而A*是将节点以“期望距离”的优先顺序插入到队列中。IDA*本身是一种深度优先搜索，深搜用到的就是迭代，迭代的过程用的是栈而不是队列。
2.我个人理解的IDA*只是深度遍历那些“期望距离”小于等于给定深度Depth的子节点，直到找到目标解，如果找不到，则将给定深度Depth+1，重新搜索。IDA*结合了深搜和广搜的优点。
3.关键的关键，对于魔方而言，要找出最好的LZ所谓的“一部分需要还原的最少步数”，只有找到最好的“一部分需要还原的最少步数”，才能真正提高效率，并且找到最优解。。
4.对于提高算法效率方面，IDA*应该是目前最完善的搜索方法，进步一提效只有两个途径：改进算法和代码优化，改进算法现阶段是困难了，只剩代码优化了，除了代码本身执行效率的优化，还有更彻底的方法，就是用汇编，LZ如果有时间可以试着用汇编来实现该算法（当然这个难度很大，我是达不到这种境界了，：）  ），我个人认为，CE应该是高级语言开发的，貌似是JAVA，没具体研究，如果是JAVA，那么C会比它快。
不知道我的看法和LZ的差别大不，可以继续讨论下

[ 本帖最后由 风流沙驼 于 2010-3-6 03:37 编辑 ]

风流沙驼

原帖由 铯_猪哥恐鸣 于 2010-3-6 09:52 发表 回7楼：对于你所说的1,2，我本来也是以为它应该是DFS+减枝（注意到是减枝而不是启发），但是通过对几个复杂状态（比如棱方向全反这种20步的状态）的内存使用分析，确实应该是A*的实现，而且如果真是前者的话我倒是更 ...

恩，我也认为CE普通搜索用的是DPS+剪枝（即ID）或者是IDA*，而使用option用的是A*，不过无论A*和IDA*，构造代价函数是最重要的，你有没有什么好的思路？我没研究，就凭空想了想，有些难度，想听听你的见解