cube-explorer核心算法

zbyxzh

看到了CS前几天的人人状态，似乎有改进CE的希望哦……回头再看一遍帖子先

铯_猪哥恐鸣

在二阶段模式下确实有一个中间状态，这个帖子没有讨论这块，因为得到的解不是最优解

任逸

顶铯                                          .

superflip

楼主有源代码？ 我想应该就是简单的DFS+减枝吧？

我不是学计算机的，只学过一点编程，不知 你说的队列排序怎么做，队列需要多大的容量？

铯_猪哥恐鸣

很简单，因为关键字只有1~20这20种情况，所以根本不用做常规的排序，直接基数排序即可，时间也基本可以忽略不计。内存方面由于实际搜索时候搜索到的节点量相当少（只有6、7步的节点量），基本可以忽略不计。当然以上这些也只是我的假设以及之前看到一篇Princeton上相关论文的推论，具体CE的实现方法、包括语言等等还都是并不是那么明确

==========================================================================
那个说一下我也不是学计算机的。。只是高中的时候稍微有点基础，最近也在学C语言，顺便通过魔方这个问题“练练手”的

[ 本帖最后由 铯_猪哥恐鸣 于 2010-3-6 13:50 编辑 ]

superflip

我已经被你说糊涂了~  你说的IDA*算法 核心是基于DFS还是BFS的算法？如果是DFS，用队列何用？

ps：能说下如何跟踪内存以确定用到队列了吗？

铯_猪哥恐鸣

我个人认为CE应该是基于BFS算法。至于跟踪内存，我是直接看windows任务管理器的。。。不知道是否足够说明问题。。。虽然前后变化只有几十M，但我个人觉得应该足够说明它申请了内存了吧。。。

还有，我认为IDA*应该不会只是按步数剪枝那么简单，不然也就不会叫做“IDA*”了，直接说“DFS+剪枝”岂不是更好。

[ 本帖最后由 铯_猪哥恐鸣 于 2010-3-6 15:13 编辑 ]

superflip

不会吧，我刚试了，启动CE时内存增加几十M，是load算好的table，之后计算不会加大块内存了啊。

我感觉名字大概是唬人的~ ，我没学过IDA*算法，也不懂与“DFS+剪枝”的区别，希望板上的编程牛人解释一下，有简单伪代码最好~

风流沙驼

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

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

ggglgq

　　
　　
  
    感谢楼主提供的 关于 Cube Explorer 软件 算法探讨 的心得体会。同时欢迎
  
更多魔友参与各类魔方 最少步（最优解）算法进行优化研究探讨！
  
    对于 正六面体三阶魔方 最少步（最优解）算法研究的文章和软件，本论坛
  
中文版（着重介绍和运用“两阶段搜索算法”）的主要有：
   
    [注意] 两阶段搜索算法
    http://bbs.mf8-china.com/viewthread.php?tid=720
   
    RCube历史版本汇总
    http://bbs.mf8-china.com/viewthread.php?tid=47427
  
同时，对于楼主“在最少步数这块，应该有希望做出比CE更快更高效的软件。”
  
的观点予以肯定和支持！更希望楼主开发出比 Cube Explorer 更优秀的软件。
  
  　
　　
　　
　　　
　　
（下页续 21 楼）