魔方吧·中文魔方俱乐部

标题: cube-explorer核心算法 [打印本页]

作者: 铯_猪哥恐鸣 时间: 2010-3-6 00:55:50 标题: 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 时间: 2010-3-6 01:02:57

占沙发慢慢看

作者: 木瓜 时间: 2010-3-6 01:03:58

做板凳上看看

作者: 时空 时间: 2010-3-6 01:06:51

不错！

PS：就是没看懂...

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

说到穷举....

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

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

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

作者: nmliutao 时间: 2010-3-6 01:33:57

真的不懂！！！

作者: Paracel_007 时间: 2010-3-6 02:44:10

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

作者: 风流沙驼 时间: 2010-3-6 03:32:00

讨论下，我尽量使用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 时间: 2010-3-6 06:52:12

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

作者: mengfl 时间: 2010-3-6 07:13:19

占楼慢慢研究。。。

作者: 铯_猪哥恐鸣 时间: 2010-3-6 09:52:50

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

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

作者: zbyxzh 时间: 2010-3-6 10:08:22

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

作者: 铯_猪哥恐鸣 时间: 2010-3-6 10:34:54 标题: 回复 8# 的帖子

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

作者: 任逸 时间: 2010-3-6 11:54:06

顶铯 .

作者: superflip 时间: 2010-3-6 12:28:40

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

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

作者: 铯_猪哥恐鸣 时间: 2010-3-6 13:49:02 标题: 回复 14# 的帖子

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

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

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

作者: superflip 时间: 2010-3-6 14:32:47

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

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

作者: 铯_猪哥恐鸣 时间: 2010-3-6 15:11:26 标题: 回复 16# 的帖子

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

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

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

作者: superflip 时间: 2010-3-6 15:50:27

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

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

作者: 风流沙驼 时间: 2010-3-6 22:35:02

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

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

作者: ggglgq 时间: 2010-3-9 00:23:04

　　
　　

感谢楼主提供的关于 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 楼）
  　
　　
　　

作者: ggglgq 时间: 2010-3-9 00:23:29

　　　
　　
（上页接 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
　
希望有更多的魔友参与各类魔方最少步（最优解）各种算法的研究及优化探讨，

共同推动我国魔方最少步（最优解）算法理论的发展。
　　
　　
　　　　
　　
　　

作者: Cielo 时间: 2010-3-9 10:26:43

支持楼主，到时候做的程序简称就是CS吧

（比如Cube Solver……）

作者: aubell 时间: 2010-3-14 23:26:47

支持楼主！
为楼主加油。

作者: rjhabc 时间: 2010-7-21 10:39:57 标题: 回复 1# 的帖子

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

作者: ggglgq 时间: 2010-7-22 13:55:50

　　
　　

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


　　
　　

作者: 打败Erik 时间: 2011-5-5 22:39:17

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

作者: 小明的马甲 时间: 2012-4-23 03:22:54

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

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)