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 编辑 ]

superacid

占沙发慢慢看

木瓜

做板凳上看看

时空

不错！

PS：就是没看懂...


===============================

说到穷举....

想起最早玩魔方的时候，我是用本子画的....

用了两个笔记本（纸的...每本厚度大概1厘米）........现在回想那时候可真笨，真固执~~

[ 本帖最后由 时空 于 2010-3-6 01:39 编辑 ]

nmliutao

真的不懂！！！

Paracel_007

CE的出现就是个神话。。。

风流沙驼

讨论下，我尽量使用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 编辑 ]

Atato

支持，我记得有个中间状态的?

mengfl

占楼慢慢研究。。。

铯_猪哥恐鸣

回7楼：对于你所说的1,2，我本来也是以为它应该是DFS+减枝（注意到是减枝而不是启发），但是通过对几个复杂状态（比如棱方向全反这种20步的状态）的内存使用分析，确实应该是A*的实现，而且如果真是前者的话我倒是更有信心把CE“干掉”

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