魔方吧·中文魔方俱乐部

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

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

Rank: 8Rank: 8

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

魔方理论探索者 八年元老

发表于 2015-2-27 17:40:42 |显示全部楼层
本帖最后由 pengw 于 2015-2-27 17:49 编辑

1楼推导上帝之数的本质,就是用假设特定长度的转式Ln的数量与状态数一一对应,事实上,Ln存在大量不改状态的无效转式及生成同一状态的等效转式(优化后,前者可以直接丢弃,后者取其一),这将导致我们的计算值偏小,所须必须优化算式,目前,我能做到是过滤掉约占总量22%的无效/等效转式,使得精度前进了一步,现在是不小于20,理想的结果是,优化掉全部无效/等效转式,那么计算结果就不是什以下限了,直接就是上帝之数,关键还是优化算法,做得好,就根本无须去漫步状态空间,也无须去计算所有的最远状态。经不同方法计算,发现,优化与否,差距不超过一步,这也可以理解,天文单位的状态空间的稀释作用,使得无效/等效转式引起的计算误差几乎可以忽略。

使用道具 举报

Rank: 7Rank: 7Rank: 7

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

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

发表于 2015-2-27 18:36:39 |显示全部楼层
pengw 发表于 2015-2-27 17:40
1楼推导上帝之数的本质,就是用假设特定长度的转式Ln的数量与状态数一一对应,事实上,Ln存在大量不改状态的 ...

但是从现在我们对魔方的认识,包括N阶定律及群论来看,“优化掉全部无效/等效转式”的复杂度和直接找出所有最远状态的复杂度是一样的,甚至前者的复杂度,特别是实际实现的困难程度还会更高一些。

使用道具 举报

Rank: 8Rank: 8

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

魔方理论探索者 八年元老

发表于 2015-2-27 19:12:47 |显示全部楼层
昨天,突然有灵感,弄出了一种优化方法,有22%的效果,如果优化的结果是,每一个转式都最短转式(即这个转式就是自已生成状态的唯一最短转式),那问题简单多了,正在完善中。

显然,那怕是转式总量10%有效,误差也不超过一步,这就是魔方现实,各位惦量惦量.

使用道具 举报

Rank: 7Rank: 7Rank: 7

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

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

发表于 2015-2-27 19:31:29 |显示全部楼层
pengw 发表于 2015-2-27 19:12
昨天,突然有灵感,弄出了一种优化方法,有22%的效果,如果优化的结果是,每一个转式都最短转式(即这个转式就 ...

“如果优化的结果是,每一个转式都最短转式”,如何判断某一个长度为20的转式为最短转式这件事情的计算量就已经非常大了,何况你需要判断10^19这么多个转式……

使用道具 举报

Rank: 8Rank: 8

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

魔方理论探索者 八年元老

发表于 2015-2-27 20:08:12 |显示全部楼层
本帖最后由 pengw 于 2015-2-27 20:09 编辑

42楼提到文档中,计算最远状态的方法,基于这样的假设:
1。一步状态有12种
2。二步状态有12*11,注:其中一种回逆,若干年前,我也这样列过个算式
3。N步状态有12*11^(n-1)
4。把每一步的状态数累加起来
事实上,由于该文作者对魔方状态奇偶性了解不足,其累加操作是与魔方性质冲突的,正确的做法是,要么累加奇数步转式或对应状态数,要么累加偶数步转式或对应状态数,累加值最终是与魔方状态数的1/2比较而不是全部,看上去计算与1楼计算一致,实为,天文单位的状态数将其错误稀释到几乎可以忽略,那怕转式总量10%有效,误差也不超过一步,这就是魔方现实

使用道具 举报

Rank: 8Rank: 8

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

魔方理论探索者 八年元老

发表于 2015-2-27 20:15:59 |显示全部楼层
回54楼,你认为,长度不大于N的所有转式(要么偶数步,要么奇数步)的有效(每一个都是某状态的唯一最短转式)百分比是多少?

使用道具 举报

Rank: 4

积分
2547
帖子
2221
精华
1
UID
4575
兴趣爱好
其它

十四年元老

发表于 2015-2-27 20:29:02 |显示全部楼层
看来,寻找最远状态好比寻找素数公式那样的难,除非有新的魔方理论或数学工具诞生。

使用道具 举报

Rank: 7Rank: 7Rank: 7

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

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

发表于 2015-2-27 20:30:57 |显示全部楼层
pengw 发表于 2015-2-27 20:15
回54楼,你认为,长度不大于N的所有转式(要么偶数步,要么奇数步)的有效(每一个都是某状态的唯一最短转式)百 ...

应该和N有关,对于比较小的N,有效转动的比例应该很高(因为不同的转式转出同一个状态的情况比较少),但如果N接近上帝之数,那么这个比例很可能不到1/100甚至1/10000

使用道具 举报

Rank: 8Rank: 8

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

魔方理论探索者 八年元老

发表于 2015-2-27 22:03:37 |显示全部楼层
本帖最后由 pengw 于 2015-2-27 22:10 编辑

回58楼:

当前算出的值 n>=20,如果是1/100,n>=22,如果是1/10000,n>=24, 当前,国外计算出的上帝之数的准备值是多少?

使用道具 举报

Rank: 7Rank: 7Rank: 7

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

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

发表于 2015-2-27 22:06:10 |显示全部楼层
pengw 发表于 2015-2-27 22:03
回58楼,当前,国外计算出的上帝之数的准备值是多少?


对于三阶纯色魔方,180度算2步的话,26

使用道具 举报

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

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

GMT+8, 2022-6-28 01:12

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部