cube-explorer核心算法

铯_猪哥恐鸣

最近一直在研究计算机解魔方最少步，然后在吧里看了N多帖子，始终没能找到有哪个帖子说了CE最核心算法的，所以为了普及知识，还是单独把这块拿出来说下。
1、二阶段搜索法
一般情况下都是在这个模式下工作的，而且吧里也有很多这块的帖子，该方法有点是效率高，缺点是结果不一定是最少步。而且这一块吧里也有足够多的帖子讨论了这个算法，我就不再多解释了。
2、最短步数解法（就是optimal那个地方打上勾以后）（IDA*算法，听名字巨强，后来看看。。也确实挺强的，只是下面的表述方法可能能让大家更方便的了解这个算法，就略去了具体实现过程了。虽然其实那个才是程序的关键。。。）
根据源代码分析，解法的思路是这样的：
1、从打乱状态进行穷举，每转动到一个状态，都从表中查到该状态的一部分需要还原的最少步数，加上当前以进穷举到的深度，将这个和作为“期望距离”后放入待穷举队列。
2、每次要继续穷举的时候优先从“期望距离”比较短的状态开始穷举。

Q：什么叫一部分需要还原的最少步数
A：就是只关心这个魔方的某些部分的还原。比如，对于某个魔方，它的角块总可以看做二阶魔方，如果这个二阶魔方至少需要8步才能还原，那原来那个三阶魔方也一定至少需要8步才能还原。（当然CE不会很简单的用二阶这块来做）

在这样的定义下，很显然“期望距离”一定会大于等于真正还原所需的距离，所以很容易知道，如果所有节点的“期望距离”都大于某个值（比如14），那么该打乱的魔方是不可能在这个值以下还原的（即魔方的最大步数一定大于等于15）。同时以也可以发现，虽然我们知道了额14这个数字，但是事实上程序并没有搜完所有14步状态（这也是不可能的，因为现在全球最好的结果就是某人花了10天借了台超级计算机算到了13步，因为状态数实在太多了），甚至在平均情况下只搜索了6~7步，借助于这个部分还原表查到当前枚举到的状态的“期望距离”


太晚了，就先写那么多，写得稍微乱了点不知道大家能不能看懂，有什么因为跟帖提出吧，我再组织语句来重新写一遍。。。

//ps:我个人觉得，在最少步数这块，应该有希望做出比CE更快更高效的软件。。。只是需要尝试。。。至少通过我对二阶魔方的研究，现在基本已经“拿下”二阶魔方，三阶的话还在思考中= =b

========================================================
关于“搜索”。刚前面时空版主问了这个是什么问题，就在这单独解释下。搜索，其实就是穷举。魔友们要深刻认识到一点：计算机除了记忆量、计算速度比人快之外其他什么都不会。所以对于求魔方最短步数这个问题，计算机什么都不会，只会枚举。说白了就是，先尝试从F,F',F2...这些，一直转完18种转法，发现无法还原，然后尝试2步的转动，FR,FR2,FR'等等，几十或者几百种转法，发现又无解，那么再尝试3步，等等。无论是CE，还是别的什么算法，只要是稍微好点的，基本都是穷举（模拟人脑的基本都只能得到40步之外的解法，和最少步数无关，不在考虑范围）。
所以CE也不可避免的使用了搜索，只不过如前所说，它不是盲目的进行搜索，它是根据魔方的“打乱情况”进行分析，感觉哪些个状态可能离目标比较近的就先搜索，使得很快它就能知道多少步之内肯定无解。具体可以在回顾上文所所。

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

小明的马甲

据说我发现原来当年我也那么2过。。。

打败Erik

我只会用CE来解十字和最少步，算法看不懂，要学数学才能看懂么？

ggglgq

　　
　　
  
    楼主应该只有 Cube Explorer 公开的 C 语言的部分源代码。
  
  
　　
　　

rjhabc

楼主说“根据源代码分析，解法的思路是这样的：...”，楼主有CE的源代码？！

aubell

支持楼主！
为楼主加油。

Cielo

支持楼主，到时候做的程序简称就是CS吧 （比如Cube Solver……）

ggglgq

　　　
　　
（上页接 20 楼）
　　
　
　　
　　
　　
  
    对于 各类魔方 最少步（最优解）算法的研究探讨、方法技巧也是五花八门！
  
我这里还是给大家推荐 最前沿、最富发展潜力 的 最少步（最优解）算法：
  
    [原创]魔方循环变换理论
    http://bbs.mf8-china.com/viewthread.php?tid=153
   
    八个循环变换 锁定魔方 “任意两状态” 的 最少步变换（最优解）实例
    http://bbs.mf8-china.com/viewthread.php?tid=30650&page=3#pid678184
   
    魔方 循环变换球面网 探究
    http://bbs.mf8-china.com/viewthread.php?tid=34872  
　  
希望有更多的魔友参与各类魔方 最少步（最优解）各种算法的研究及优化探讨，
  
共同推动我国魔方 最少步（最优解）算法理论的发展。
　　
　　
　　　　
　　
　　

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 楼）
  　
　　
　　

风流沙驼

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

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