个人写的一个魔方还原软件

jshyhzj

个人写的一个魔方还原软件，请各位鉴赏，有问题可以直接联系我：QQ 45904680
http://www.telossoft.com.cn/OtherRubikCube.php
  介绍 公司中突然很多同事玩起魔方，所以来了兴趣，决定写个程序搞定这个问题。

这个软件实现了一个标准的搜索算法，向您演示了计算机搜索的基本过程与特点：源状态和目标状态的建立、建立搜索树并不断扩展、如何识别已经搜索过的点、当搜索范围过大后如何修剪搜索树，仅搜索最有价值的点等。

jshyhzj

这个是提供源代码的,你可以下载源代码后将平台改为.net 4.0, 编译后性能又可以提高50%

jshyhzj

补充下，在程序运行目录下有个文件：RubikCubeV4.cfg，调整其中的参数可以让程序跑的飞快，如我调整到如下：
EvaluateWidth=1000
EvaluateMax=90
则搜索的结果如下，5秒不到搜索到结果：
EvaluateWidth: 1,000    EvaluateMax: 90
Deep: 0   Width: 1
Deep: 1   Width: 18
Deep: 2   Width: 243   RunTime: 17毫秒   平均价值: 27
Deep: 3   Width: 3,240   RunTime: 23毫秒   平均价值: 26
Deep: 4   Width: 1,099   RunTime: 295毫秒   平均价值: 41
Deep: 5   Width: 1,238   RunTime: 105毫秒   平均价值: 47
Deep: 6   Width: 1,526   RunTime: 123毫秒   平均价值: 51
Deep: 7   Width: 1,470   RunTime: 195毫秒   平均价值: 55
Deep: 8   Width: 1,538   RunTime: 141毫秒   平均价值: 58
Deep: 9   Width: 1,831   RunTime: 151毫秒   平均价值: 60
Deep: 10   Width: 1,422   RunTime: 180毫秒   平均价值: 63
Deep: 11   Width: 1,425   RunTime: 159毫秒   平均价值: 65
Deep: 12   Width: 1,425   RunTime: 139毫秒   平均价值: 67
Deep: 13   Width: 1,557   RunTime: 136毫秒   平均价值: 68
Deep: 14   Width: 1,444   RunTime: 148毫秒   平均价值: 71
Deep: 15   Width: 1,701   RunTime: 155毫秒   平均价值: 72
Deep: 16   Width: 1,461   RunTime: 164毫秒   平均价值: 74
Deep: 17   Width: 1,558   RunTime: 141毫秒   平均价值: 75
Deep: 18   Width: 1,437   RunTime: 159毫秒   平均价值: 77
Deep: 19   Width: 1,582   RunTime: 186毫秒   平均价值: 78
Deep: 20   Width: 1,629   RunTime: 152毫秒   平均价值: 80
Deep: 21   Width: 1,591   RunTime: 160毫秒   平均价值: 82
Deep: 22   Width: 1,754   RunTime: 155毫秒   平均价值: 83
Deep: 23   Width: 1,580   RunTime: 169毫秒   平均价值: 85
Deep: 24   Width: 1,511   RunTime: 156毫秒   平均价值: 87
Deep: 25   Width: 1,353   RunTime: 151毫秒   平均价值: 89
Deep: 26   Width: 1,394   RunTime: 155毫秒   平均价值: 90
Deep: 27   Width: 1,397   RunTime: 149毫秒   平均价值: 92
Deep: 28   Width: 1,461   RunTime: 159毫秒   平均价值: 92
Deep: 29   Width: 1,860   RunTime: 183毫秒   平均价值: 92
Deep: 30   Width: 1,660   RunTime: 289毫秒   平均价值: 95
Deep: 31   Width: 1,846   RunTime: 267毫秒   平均价值: 95
Deep: 32   Width: 216   RunTime: 8毫秒   平均价值: 98
======== 搜索节点总数: 295,031 ========
======== 搜索总耗时: 4,762毫秒 ========

要是用我自己的笔记本估计4秒内就可搞定

[ 本帖最后由 jshyhzj 于 2009-8-27 21:33 编辑 ]

william_khs

期待樓主可做出4階的還原軟件...

jshyhzj

"需要建“库”！ "----这其实违背了软件的初衷，表明你已经知道了问题的解决策略，类似于写一个把口诀做进去的软件，没有意义的。

我所要做的就是让计算机仅知问题的定义，靠蛮力战胜人类可笑的智力。

这类问题有意思的就是算法，如果参考或学习别人的算法那剩下的仅是体力活了，不值得我劳神的哈。

[ 本帖最后由 jshyhzj 于 2009-8-25 18:45 编辑 ]

ggglgq

　　
　　
  
    楼主 的程序的确很快，但是，正如 5 楼所说，楼主需要学习一下
  
                               Cube Explorer
  
的 Two phase 等算法。 “蛮算”是不可能精确算出“最少步”的！需要建“库”！
  
    对本主题 “加亮” 支持，希望楼主不断完善这个程序！
  
    楼主 亦可参考本人的《循环变换算法》优化您的程序！
  
    http://bbs.mf8-china.com/viewthread.php?tid=30650&page=3#pid678184
  
　　
　　
　　

[ 本帖最后由 ggglgq 于 2009-8-12 12:51 编辑 ]

jshyhzj

当然我这个比专业选手做的差远了

jshyhzj

在目前PC机上想搜全是不可能的哈，必须裁剪的

xh176233756

lz精神可嘉，但是问题还是有的。

首先向你推荐一个软件Cube Explorer。你干的事它都干了。
从搜索树的规模来看，你的节点好像没有搜全，这也导致了你在搜过了23步后仍然没有找到解法。
另外Cube Explorer除了BFS外还有一种Two phase解法，可以在很短时间内找到一个24步以内的非最优解。非常强大。
他的算法可以在帮助文件内找到。lz可以去研究，祝lZ做出更加强大的cube solver.

天花板上吊着猫

真巧啊。。。昨天不知道怎么摸到你的网站然后就下载下来了。。。