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

黑白子

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

pengw

这里的19步是在没有过滤无效转式的前提下算出的，因此计算值自然要小于实际值。如果少一步低于状态数，多二步(为什么要多二步?）超过状态的2倍，你认为实际值该是多少?

pengw

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

铯_猪哥恐鸣

我又仔细看了下1楼。以三阶纯色魔方为例，在算法的步骤4中，为了求得n，需要产生m=12^n个不同的转式。这些转式会产生一堆状态，其中有一些是相同的，也有一些是不同的。如果每个状态都在这m个转式产生的状态中出现，才能证明n就是魔方的奇数步或偶数步最远状态，我没理解错吧？

pengw

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

铯_猪哥恐鸣

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

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

pengw

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

铯_猪哥恐鸣

pengw 发表于 2015-2-26 19:52
单机,每秒亿次，可能要几年，哈哈,不过,由于算法可以分割到很多电脑上去并行执行,乐欢地估计,不会超过一个月 ...

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

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

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

pengw

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

铯_猪哥恐鸣

pengw 发表于 2015-2-26 21:04
最新分析结果，对于给定长度转式，可以至少优化掉20%；最小收索,偶数步转式:2.1791E+20;奇数步转式:2.42122 ...

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