魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: pengw

[原创]基于N阶定律的三阶最远状态计算分析 [复制链接]

Rank: 4

积分
2557
帖子
2231
精华
1
UID
4575
兴趣爱好
其它

十四年元老

发表于 2015-2-25 23:43:07 |显示全部楼层
1楼有一句话:国外对三阶纯色魔方,动用了庞大的计算资源,历经20多年努力,得出的最终结果是20,而这里采用严密又又极其简单的计算法,算出的非优化结果是不小于19,二者是不是非常接近?
我记得国外专家算出的20步是把转动180度也算作一步了,而这里的19步是把180度算作了二步。因此,二者没有可比性。

使用道具 举报

Rank: 8Rank: 8

积分
4825
帖子
2795
精华
7
UID
383
性别

魔方理论探索者 八年元老

发表于 2015-2-26 15:50:10 |显示全部楼层
这里的19步是在没有过滤无效转式的前提下算出的,因此计算值自然要小于实际值。如果少一步低于状态数,多二步(为什么要多二步?)超过状态的2倍,你认为实际值该是多少?

使用道具 举报

Rank: 8Rank: 8

积分
4825
帖子
2795
精华
7
UID
383
性别

魔方理论探索者 八年元老

发表于 2015-2-26 15:54:57 |显示全部楼层
本帖最后由 pengw 于 2015-2-26 16:00 编辑

31楼的提问触发了楼主一个很美妙的的针对上界的思路,以至,似乎靠简单计算,从二端可以非常接近真实值

使用道具 举报

Rank: 7Rank: 7Rank: 7

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

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

发表于 2015-2-26 16:01:56 |显示全部楼层
我又仔细看了下1楼。以三阶纯色魔方为例,在算法的步骤4中,为了求得n,需要产生m=12^n个不同的转式。这些转式会产生一堆状态,其中有一些是相同的,也有一些是不同的。如果每个状态都在这m个转式产生的状态中出现,才能证明n就是魔方的奇数步或偶数步最远状态,我没理解错吧?

使用道具 举报

Rank: 8Rank: 8

积分
4825
帖子
2795
精华
7
UID
383
性别

魔方理论探索者 八年元老

发表于 2015-2-26 18:13:37 |显示全部楼层
本帖最后由 pengw 于 2015-2-26 18:17 编辑

回上楼:
你的理解基本上是正确的,但有一点,你可能没有注意看分析,没有一个定长转式可以转出所有魔方状态,偶数步转式与奇数步转式转出的状态互不相同而数量相同,这是N阶定律所预言的,你可以试一下2步转式可否转出一步转式的状态(复原状态是初态),因此准备地讲,长度为n 的转式最多只能转出一半的魔方状态,最小的n值就是最远状态,三阶有二类最远状态,即奇数步最远状态与偶数步最远状态

使用道具 举报

Rank: 7Rank: 7Rank: 7

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

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

发表于 2015-2-26 19:07:14 |显示全部楼层
pengw 发表于 2015-2-26 18:13
回上楼:
你的理解基本上是正确的,但有一点,你可能没有注意看分析,没有一个定长转式可以转出所有魔方状态 ...

好的。然后也就是说需要枚举的转式至少有21626001637244928000个,你认为现在的计算机枚举完这么些转式大约需要多久?

使用道具 举报

Rank: 8Rank: 8

积分
4825
帖子
2795
精华
7
UID
383
性别

魔方理论探索者 八年元老

发表于 2015-2-26 19:52:10 |显示全部楼层
本帖最后由 pengw 于 2015-2-26 20:17 编辑

单机,每秒亿次,可能要几年,哈哈,不过,由于算法可以分割到很多电脑上去并行执行,乐欢地估计,不会超过一个月。别外说明一下,转式优化与非化(过滤无效与等效)对最远状态的影响还不超过一步,有时间再发布优化算法,有意常简单的优化方法,至少可以去除16%的无用转式

使用道具 举报

Rank: 7Rank: 7Rank: 7

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

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

发表于 2015-2-26 20:21:52 |显示全部楼层
本帖最后由 铯_猪哥恐鸣 于 2015-2-26 20:28 编辑
pengw 发表于 2015-2-26 19:52
单机,每秒亿次,可能要几年,哈哈,不过,由于算法可以分割到很多电脑上去并行执行,乐欢地估计,不会超过一个月 ...


能否详述一下如何分割到很多电脑上进行计算?特别是如何分配计算量、各计算节点如何处理、以及如何整合各电脑的计算结果?

另外,我们以10000台电脑1个月来算(实际上我估计下来应该远远不止这点计算量),实际使用的计算耗时其实是800多CPU年(国外那个35 CPU年的结果也是这么算的,否则就变成比谁电脑多了)

至于说除去无用转式,我觉得会有用,但根据1楼的描述和前面的推论,总状态搜索量不可能小于21626001637244928000。

使用道具 举报

Rank: 8Rank: 8

积分
4825
帖子
2795
精华
7
UID
383
性别

魔方理论探索者 八年元老

发表于 2015-2-26 21:04:15 |显示全部楼层
本帖最后由 pengw 于 2015-2-26 21:10 编辑

最新分析结果,对于给定长度转式,可以至少优化掉20%;最小收索,偶数步转式:2.1791E+20;奇数步转式:2.42122E+19

使用道具 举报

Rank: 7Rank: 7Rank: 7

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

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

发表于 2015-2-26 22:16:08 |显示全部楼层
pengw 发表于 2015-2-26 21:04
最新分析结果,对于给定长度转式,可以至少优化掉20%;最小收索,偶数步转式:2.1791E+20;奇数步转式:2.42122 ...

是的,但我不觉得这是个可接受的搜索量。而且如何分配到不同的电脑上计算、如何整理、储存计算结果和中间结果才是这个算法的关键。毕竟当前硬盘的大小最大也就TB数量级,即10^12字节。

使用道具 举报

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

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

GMT+8, 2024-3-29 05:20

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部