魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 699712|回复: 26

cube-explorer核心算法 [复制链接]

Rank: 7Rank: 7Rank: 7

积分
3923
帖子
2556
精华
6
UID
15558
性别
保密
WCA ID
2008CHEN27
兴趣爱好
理论

魔方理论探索者 国家(地区)纪录(NR) 十年元老

发表于 2010-3-6 00:55:50 |显示全部楼层
最近一直在研究计算机解魔方最少步,然后在吧里看了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 编辑 ]
已有 6 人评分经验 收起 理由
一叶知秋 + 20 精品文章!赞~~~
ggglgq + 10 支持!希望楼主开发更优秀的软件。
kexin_xiao + 20 精品文章
臭虫 + 10 原创内容
证明题 + 20 精品文章,too
superacid + 20 精品文章

总评分: 经验 + 100   查看全部评分

Rank: 7Rank: 7Rank: 7

积分
2520
帖子
3072
精华
7
UID
62890
性别

中国纪录 八年元老

发表于 2010-3-6 01:02:57 |显示全部楼层
占沙发慢慢看
19events = 644days
PB (2 3 4 5)B = 1200seconds
北大魔方爱好者QQ群74893945
mf8最少步讨论群:RP与公式的绝佳配合QQ群5652935

使用道具 举报

Rank: 6Rank: 6

积分
6032
帖子
4213
精华
3
UID
25480
性别

六年元老

发表于 2010-3-6 01:03:58 |显示全部楼层
做板凳上看看
要的就是性能!
最近出现了假木瓜,用我的名义忽悠了很多人,请各位亲们不要上当

使用道具 举报

粉魔

CCA

Rank: 5Rank: 5

积分
4758
帖子
2497
精华
0
UID
7127

八年元老

发表于 2010-3-6 01:06:51 |显示全部楼层
不错!

PS:就是没看懂...


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

说到穷举....

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

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

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

使用道具 举报

红魔

nmG

Rank: 4

积分
1421
帖子
1227
精华
0
UID
74891
性别
保密
发表于 2010-3-6 01:33:57 |显示全部楼层
真的不懂!!!

使用道具 举报

铜魔

007

Rank: 8Rank: 8

积分
13803
帖子
13083
精华
2
UID
101677
性别

四年元老 八年元老 十年元老

发表于 2010-3-6 02:44:10 |显示全部楼层
CE的出现就是个神话。。。
魔方收藏群 123380874

使用道具 举报

红魔

多啦A梦成员

Rank: 4

积分
1759
帖子
717
精华
7
UID
93493
性别
发表于 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 编辑 ]
已有 1 人评分经验 收起 理由
臭虫 + 5 热心参与

总评分: 经验 + 5   查看全部评分

欢迎访问鲁比克DIY网(持续建设中...):http://www.rubiksdiy.com/

使用道具 举报

红魔

Atato!

Rank: 4

积分
2339
帖子
2004
精华
1
UID
26065
性别

六年元老

发表于 2010-3-6 06:52:12 |显示全部楼层
支持,我记得有个中间状态的?
如果最初的想法不是荒谬的, 那么它就毫无希望.
                                                                      -阿尔伯特·爱因斯坦

使用道具 举报

Rank: 3Rank: 3

积分
996
帖子
868
精华
0
UID
1242458
性别
发表于 2010-3-6 07:13:19 |显示全部楼层
占楼慢慢研究。。。

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
3923
帖子
2556
精华
6
UID
15558
性别
保密
WCA ID
2008CHEN27
兴趣爱好
理论

魔方理论探索者 国家(地区)纪录(NR) 十年元老

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

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-29 04:32

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部