魔方吧·中文魔方俱乐部

标题: [原创]基于N阶定律的三阶最远状态计算分析 [打印本页]

---

作者: pengw    时间: 2015-2-18 09:49:31     标题: [原创]基于N阶定律的三阶最远状态计算分析



要研究魔方最远状态，如果选择的方法是与魔方状态数较劲，是相当不理智的，不幸的是，这样的事一直在发生，且执迷不悟，事实上，改变一下思路，处理方法则要简单很多。魔方从来就是，为头脑清淅，逻辑严密，善于归纳总结的玩家准备的，然而，仍然随处可见到，概念定义似是而非，逻辑倒错，似乎可以解决所有问题又无法证明的描述，事实上，魔方就像一面镜，从中可以对人的一些能力给预一个判断或评估。

探讨最远状态,如同面对一个没有地图说明的公路网,要想知道了解任何二地的最短距离,其难度可想而知,然而,如果我们知道任意二地的经纬度,则可以合理推断出最少须要行驶段多少距离就可以完成行程,基于这个思路,偿试分析一下三阶的最远状态.

基本思路

分析1步转式能构造的状态数，再分析2步转式构造的状态数，如果能找到一个长度为n的转式，正好能构构造出所有魔方状态,那么最小的n 值就是最远状态,.在这里,我们假定所有长度为n的转式正好与魔方状态数一一对应,由于魔方状态数可以准确计算出来，因而可以倒推出一个长度为n的转式，显然，由于存在不改变魔方状态的无效转式( 仅当 n是偶数，为什么?谁能解答?)和生成同一状态的等效转式，因而，这个算出来的长度为 n的转式生成的状态数总是小于魔方状态数的一半，这个n的意义是，说明魔方的的最远状态的长度至少大于n。

这个思路在过滤无效转式与等效转式方面还有极大的优化可能,优化的结果是更逼近真实值。满足魔方一半的状态被构造出来的最小n值最少有2个，分别代表偶数步最远状态和奇数步最远状态，其中最大者就是魔方最远状态，由于奇数步转式不含无效转式，预计，奇数步最远状态比偶数步最远状态更短，因此，魔方最远状态可能由偶数步转式生成。

定义

最远状态:从复原魔方到任意状态的最短步数构成一个集合,这个集合中步数最长者对应的状态称为最远状态,在这里,90度转算一步，本文中，结合上下文相关性，最远状态也指生成该状态的最短转式的长度

转式：一个有限长度的转动序列a1,a2,...an,1=<an<=12(在三阶上执行90度/步，共有12种情况）

长度为1的转式有：L1=12^1种
长度为2的转式有：L2=12^2种
长度为n的转式有：Ln=12^n种

分析

1。基于N阶定律，魔方的状态数可以准确计算出来
2。N阶定律预言，奇数步状态数与偶数步状态数各占一半，互无交集
3。分析可知，如果n是奇数，Ln可以转达出Lk的所有状态，其中K是奇数，1=<K<=n
4。分析可知，如果n是偶数，Ln可以转达出Lk的所有状态，其中K是偶数，2=<K<=n

计算

基于以上分析，可以列出以下算式:

三阶纯色:

三阶纯色魔方状态数T=8!/2*12!/2*3^7*2^11*2，T/2=3^7*8!*12!*2^9=21626001637244928000

Ln=12^n=T/2=3^7*8!*12!*2^9=21626001637244928000

n=17.91

Ln构造的所有纯色魔方状态中，显然存在重复状态，也就是说，步长约为17的所有转式并不能构造出一半的魔方状态，但由此计算可以准确地给出一个极限值，即，最远状态至少大于17步(90度/步)。在此基础上，对于奇数步最远状态的合理推断应该是不小于19，偶数步最远状态不小于18

三阶全色:

三阶全色魔方状态数T=8!/2*12!/2*3^7*2^11*4^5*2*2，T/2=3^7*8!*12!*2^9*4^5*2
Ln=12^n=T/2=3^7*8!*12!*2^9*4^5*2

n=20.98

Ln构造的所有全色魔方状态中，显然存在重复状态，也就是说，步长约为20的所有转式并不能构造出一半的魔方状态，但由此计算可以准确地给出一个极限值，即，最远状态至少大于20步(90度/步)。在此基础上，对于奇数步最远状态的合理推断应该是不小于21，偶数步最远状态不小于22

国外对三阶纯色魔方，动用了庞大的计算资源，历经20多年努力，得出的最终结果是20，而这里采用严密又又极其简单的计算法,算出的非优化结果是不小于19，二者是不是非常接近?作者是非常害怕与天文单位的状态数迎头对决,但,确实有人敢于面对.很多事情,只要愿意,经耐心细至地分析,总能找出更为巧妙的解决方法.这里采用的方法,稍加变更,可用于N阶最远状态推断.


算法

在上面的分析计算的基础上，可以构造一个相当简单而又精确的算法:

1.设转式长度初值(奇数或偶数)为这里的合理推断值n
2.构造一个n重循环，每层循环初值是1终值是12，由些生成所有长度为n的转式
3.将长度为n的每个转式在复原魔方上分别执行一次，产生一个状态，将此状态与已经产生的状态比较，记录新状态，丢弃重复产生的状态
4.转式执行完后(也许没有执行完，所有状态都生成了,此时可以退出，但是有可能无法找出所有状态的最短生成转式），检查生成的状态数，如果状态数与奇数步或偶数步状态数相等,则这个n就是魔方的奇数步或偶数步最远状态,否则，转式长度加2,回到第一步
5.比较的奇数步与偶数步最远状态,最大者就是魔方的最远状态

说明

相信，稍有编程经验的玩家，都很容易将上面的算法变成代码。上面的算法中,可以设置无效转式(不改变魔方状态的转式)和等效转式过滤器，改善算法效率，当然这不是必须的.此算法只适用于二阶与三阶.显然，这个算法一定会精确找出三阶的最远状态。显而易见，这个算法，可以把任务分摊到多台计算机上去独立运算，比如，奇数步转式与偶数步转式可分开独立运算，同类型的转式又可以拆分成多多个段独立运算,状态数据库也可以独立创建2个,分别对应奇数步转式与偶数步转式.对于有限的资源,可以分次分批逐步完成.

这个算法似乎只能找出最远状态长度，然而，改进一下第三步，则可以找出所有状态的最短生成转式(可能不止一个)，只须增加转式的优化,记录，对比，丢弃较长的。一但建立起状态及其对应的最短生成转式数据库，剩下的所有问题仅仅是查询数据库。

作者向来认为,寻找任意二个魔方状态之间的最短转式这类与魔方状态数迎头对决的游戏不好玩,也没有多少含金量,形同背交通地图.


推广
二，三阶只有二个扰动状态，状态数等分二类，转式分为偶数步与奇数步二类；四阶五阶有四个扰动状态，状态数等分为四类，转式也分为四类；N阶有2^init(n/2)扰动状态，状态数等分为2^init(n/2)类，转式也分为2^init(n/2)类，每类转式都能构造1/（2^init(n/2))种状态,虽然每类转式构造的状态数完全相同且无交集,但是,与二三阶单一性质的转层(等效之后,仅有表层)相比,四阶及四阶以上,转层的性质已多样化,转层由表转层及性质不同的内转层构成，因此导致分析变得复杂，而二三阶由于转式结构的单一性,转式长度的奇偶互斥性,及长转式以下的所有短转式是长转式的子集（如，长度为分别为1，3，5的转式是长度为7的转式的子集，长度为分别为2，4，6的转式是长度为8的转式的子集），使得二三阶问题的处理相对简单，不过，处理三阶的思路和原则，为处理三阶以提供了重要的线索，N定律为构造计算方法提供了极其重要指导性原则。四阶及以上，相对复杂，但仍然可以处理，至少，被处理时间以分钟计，而不是年，后面再做描述。

---

作者: 黑白子    时间: 2015-2-18 18:55:23

纯色魔方每步90度，最远状态不会大于24。

---

作者: 黑白子    时间: 2015-2-18 19:02:48

这个思路到时很新颖，是否能推广到n阶魔方呢？

---

作者: pengw    时间: 2015-2-18 20:44:42

完全可以推广到N阶，进行一步分析发现，一楼的算法也不准确，更新中。。。

---

作者: pengw    时间: 2015-2-18 21:37:37

回2楼，不知道你的结论是不是有正式的证明，我的推导应该不会小于40(90度/1步 ），也不知道现在证明的最小步数是多少，有理由相信，一楼分析是有依据的。如n=24,12^24远小于魔方状态数的一半，应该是错误的。

由于没有很好的消同态算法，最远状态是42(90度/1步 ），应该是相对合理的判断。

---

作者: pengw    时间: 2015-2-18 22:10:27

一楼上我算错了，已更正为:17.91

---

作者: 黑白子    时间: 2015-2-18 22:26:49

pengw 发表于 2015-2-18 21:37
回2楼，不知道你的结论是不是有正式的证明，我的推导应该不会小于40(90度/1步 ），也不知道现在证明的最小步 ...

没有，我说的话不严谨。情况是这样的，我在使用软件计算五色棋盘最远状态时，发现用24步就足够了，更令人惊奇的是，除12棱块翻转外，我再也没找到用大于或等于24步的状态。于是，有了下面的猜想：三阶纯色魔方每步90度，最远状态不大于24步。
[java3=300,300]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]U B L' F U' B D F U D' L D D F' R B' D F' U' B' U D'R' U[/param]
  [param=initScrpt]U B L' F U' B D F U D' L D D F' R B' D F' U' B' U D'R' U[/param]
[/java3]

---

作者: 黑白子    时间: 2015-2-18 22:33:05

详细可参考这个帖子
http://bbs.mf8-china.com/forum.p ... page%3D4&page=2

---

作者: pengw    时间: 2015-2-18 23:16:43

五楼回复是错误的，N值算错了，一楼已更正

---

作者: 铯_猪哥恐鸣    时间: 2015-2-19 13:28:16



纯色魔方，每步90度，其上帝之数已被证明为26。http://cube20.org/qtm/

最远状态如下：

[java3=300,300]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]U U F U U R' L F F U F' B' R L U U R U D' R L' D R' L' D D[/param]
  [param=initScrpt]U U F U U R' L F F U F' B' R L U U R U D' R L' D R' L' D D[/param]
[/java3]

这是迄今为止发现的唯一一个需要26步才能复原的状态。


另外，楼主的结论其实可以进一步加强，因为12^n这些转动中其实有很多是无效的，例如如果出现了“R' R”，那显然这个序列应该被去除，另外“R L”和“L R”是同一个转动，被计算了两次。将此类废步去掉后结果可以进一步被加强（因为给定转动数n，可以达到的状态会少很多）。

在国外，无上述废步的转动序列一般称为canonical move sequence。在 http://cubezzz.dyndns.org/drupal/?q=node/view/301 这个帖子中给出了n阶魔方转动k步后可能的canonical move sequence个数。再结合n阶魔方状态数，即可给出n阶魔方上帝之数的下界。部分结论可参考：http://cubezzz.dyndns.org/drupal/?q=node/view/236

---

作者: 黑白子    时间: 2015-2-19 16:28:33

铯_猪哥恐鸣 发表于 2015-2-19 13:28
纯色魔方，每步90度，其上帝之数已被证明为26。http://cube20.org/qtm/

最远状态如下：

后两个链接怎么打不开?另外,25步的状态是36?26步的状态是3?问号是什么意思?

---

作者: 黑白子    时间: 2015-2-19 16:30:19

铯_猪哥恐鸣 发表于 2015-2-19 13:28
纯色魔方，每步90度，其上帝之数已被证明为26。http://cube20.org/qtm/

最远状态如下：

能否把这个资料翻译成中文?这个结论是2014年8月得出的吗?

---

作者: pengw    时间: 2015-2-19 18:18:10



回十楼，你说的很对。  从12^n中清除同态是一楼最终走向精确的关键，很多同态单从转式结构上就很容易判断，如你举的例子。再比如，一个长度为7的转式，U U‘BB‘XYZ，其中XYZ是随意的，那么这个转式共有4！个等效转式，因此，关键是如何找出一种针对转式的算法，从12^n中清除所有同态，如果做到这点，即可精确找出最远状态的长度，一楼的计算值取整加3应该是一种合法的做法，离目前已证明结论仍然有3的差距，但处理方法相对简单。有一点是显而易见的，即，转式越长，同态越多。

---

作者: 黑白子    时间: 2015-2-21 16:46:55

链接里写了什么，打不开呀?

---

作者: 天方魔    时间: 2015-2-21 23:04:42

各种云里雾里。。。

---

作者: 至尊达哥    时间: 2015-2-24 12:15:11

黑白子 发表于 2015-2-21 16:46
链接里写了什么，打不开呀?

等网络好了就能打开了。

---

作者: 黑白子    时间: 2015-2-24 13:08:44



铯_猪哥恐鸣在10楼说：在国外，无上述废步的转动序列一般称为canonical move sequence。在 http://cubezzz.dyndns.org/drupal/?q=node/view/301 这个帖子中给出了n阶魔方转动k步后可能的canonical move sequence个数。再结合n阶魔方状态数，即可给出n阶魔方上帝之数的下界。部分结论可参考：http://cubezzz.dyndns.org/drupal/?q=node/view/236。
就是这里给出的两个链接始终无法打开，有谁知道是怎么回事？

---

作者: 黑白子    时间: 2015-2-24 13:13:23

至尊达哥 发表于 2015-2-24 12:15
等网络好了就能打开了。

我一回都没打开过？

---

作者: 铯_猪哥恐鸣    时间: 2015-2-24 14:15:58

黑白子 发表于 2015-2-24 13:13
我一回都没打开过？

显然是被墙了。我记得站务区还是闲聊区有讲怎么翻墙的帖子的。

---

作者: 至尊达哥    时间: 2015-2-24 14:41:18

黑白子 发表于 2015-2-24 13:13
我一回都没打开过？

你叫他截个图。

---

作者: pengw    时间: 2015-2-24 14:47:28

一楼纯色魔方最远状态非优化的推导值19已非常接近20，有谁愿意去弄一个无效转式与等效转式过滤器？

---

作者: pengw    时间: 2015-2-24 14:49:28

四阶及以上也可以计算了，有谁愿意给个独立算法或思路?

---

作者: 黑白子    时间: 2015-2-24 14:49:41

铯_猪哥恐鸣 发表于 2015-2-24 14:15
显然是被墙了。我记得站务区还是闲聊区有讲怎么翻墙的帖子的。

能否把资料粘贴到网上?

---

作者: pengw    时间: 2015-2-24 14:52:48

只须把无效转式与等效转式过滤处法贴出来就行了,再不贴,我可是要发自已的,哈哈哈

---

作者: 铯_猪哥恐鸣    时间: 2015-2-24 19:40:17

pengw 发表于 2015-2-24 14:52
只须把无效转式与等效转式过滤处法贴出来就行了,再不贴,我可是要发自已的,哈哈哈

没事，你发一下你自己的吧，这样两边可以对比着看，以免出现外国人错了结果我们先入为主了的情况。

---

作者: pengw    时间: 2015-2-24 21:40:47



回25楼，24楼是在开玩笑，只有初步设想，大致是，清除无效转式与等效转式(偶数步转试)，或只清除等效转式(奇数步转式),有些仅分析转式就能确定,而另外一些是从转式上无法分析出来,目前主要方向还放在构造N阶下界的计算方法上,经测算,四阶纯色的A‘B1‘(A簇与B1簇同为奇态簇)类状态的最远状态不小于22,另外三个扰动关系(,A‘B1,AB1‘,AB1)尚未计算

---

作者: 黑白子    时间: 2015-2-24 23:25:43

十分期待最远状态的结果。

---

作者: pengw    时间: 2015-2-25 07:11:39



4阶:
扰动关系   纯色最远状态不小于   全色最远状态不小于
AB1            22                               26
AB1'           23                               27
A 'B1          23                               27
A'B1'          22                               26

5阶:
纯色:35
全色:41

---

作者: pengw    时间: 2015-2-25 07:48:55

有时间，再详述计算方法

---

作者: 黑白子    时间: 2015-2-25 23:27:04

铯_猪哥恐鸣 发表于 2015-2-19 13:28
纯色魔方，每步90度，其上帝之数已被证明为26。http://cube20.org/qtm/

最远状态如下：

那个网页在26步的状态后面写的是3?是否指好像有3个26步的状态?若是，另外2个是什么?
25步是36个吗？

---

作者: 黑白子    时间: 2015-2-25 23:43:07

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

---

作者: pengw    时间: 2015-2-26 15:50:10

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

---

作者: pengw    时间: 2015-2-26 15:54:57



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

---

作者: 铯_猪哥恐鸣    时间: 2015-2-26 16:01:56

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

---

作者: pengw    时间: 2015-2-26 18:13:37



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

---

作者: 铯_猪哥恐鸣    时间: 2015-2-26 19:07:14

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

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

---

作者: pengw    时间: 2015-2-26 19:52:10



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

---

作者: 铯_猪哥恐鸣    时间: 2015-2-26 20:21:52

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

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

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

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

---

作者: pengw    时间: 2015-2-26 21:04:15



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

---

作者: 铯_猪哥恐鸣    时间: 2015-2-26 22:16:08

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

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

---

作者: pengw    时间: 2015-2-27 05:29:48

如果把转式成度放到X轴，状态数放到Y轴，则这条坐标线是，最完状态之前(约20步)之前是一直上升,之后变成与X轴平行,已可以准确计算出非常逼近最远状态的下限值,若能找出上限值计算方法,基本大功告成.楼主的目的,在地用简单方法计算出最远状态或极其逼近的上下限值,而不是一个一个找出最远状态,如果真要去寻找,我认为这不是什么好玩的事情,必须有强大的计算与存贮力支持.

关于存贮量:
角块:编号3位，位置3位，色向2位
棱块:编号4位，位置4位，色向1位
中块:编号3位，色向2位

即22位可表示一个三阶全色状态，17位可以表示一个纯色状态。因此纯色状态的存贮容量是约10^20 bit,约10^8T

状态数据库可分为独立的二个

--------------------------------------

转式可分为独立的很多组,单独执行,例如,长度为2的转式,可分为十组独立操作：
1(1-12)
2(1-12)
...
12(1-12)

当然，如果资源足够，还可以进一步细分

数据库只能建一个

---

作者: 黑白子    时间: 2015-2-27 09:45:21

楼主的算法和下面这个帖子中的算法一样吗？（虽然铯_猪哥恐鸣曾指出这篇论文前5步的结果好像还是错的），那篇文章得出的结论也是不小于19步。
从网上找到一篇讨论三阶魔方的文章http://bbs.mf8-china.com/forum.p ... 65&fromuid=4575

---

作者: pengw    时间: 2015-2-27 11:49:23

回楼上:
其计算显示是错误，二步最多做出114种状态，而该文是123，显然，在排除无效及等效转式方面发生错误，其基本思路跟多年前，我发过一个短贴很相似，群论我不懂，因此，无法做出评论，而该文似乎没有区别对待偶数步与奇数步，忙中，暂说这些。

---

作者: pengw    时间: 2015-2-27 12:06:46

计算思路显然不一样，1楼计算只是初步，之后，会有转式优化后的计算结果，显然，计算方法要简单很多，利用群论应该算得更准才对

---

作者: pengw    时间: 2015-2-27 12:06:47

计算思路显然不一样，1楼计算只是初步，之后，会有转式优化后的计算结果，显然，计算方法要简单很多，利用群论应该算得更准才对

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 13:01:25



“数据库只能建一个” 这样的话整个算法的瓶颈会在数据库这边，因为这一部分是无法做上述并行的，这将直接导致计算所需要的时间达到几年甚至几百年这个数量级。而且10^8T级别的数据库的搭建应该是个很困难的问题，能否详述如何解决这么大个数据库的搭建、管理、架构等？（即便数据库分2个，每个数据库也是10^8T级别的，我不认为这是个可接受的数量级）

---

作者: pengw    时间: 2015-2-27 14:38:12



从最新计算可知，转式优化后，三阶纯色最远状态不小于20，简单地作了以下转式优化:

1.无效转式:不改变魔方状态，处理方法，丢弃
2.对称等效转式,如LR,RL,处理方法，保留一个
3.180等效，如LL，L‘L‘，处理方法，保留一个
4.逆转式，如RLL‘R‘，处理方法，丢弃
5同层等效转式，如，L'与LLL,L与L‘L‘L‘，处理方法，丢弃

具体处理方法，以后再细说，总之，优化后，精度提高一步，从不小于19到达不小于20

---

作者: pengw    时间: 2015-2-27 14:54:05

回46楼，所以说，找出所有最完状态，不好玩老外也没有全部玩出来

---

作者: pengw    时间: 2015-2-27 14:54:40

回46楼，所以说，找出所有最完状态，不好玩老外也没有全部玩出来

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 15:04:02

pengw 发表于 2015-2-27 14:55
回46楼，所以说，找出所有最远状态不好玩，老外也没有全部玩出来

是的，找出所有最远状态确实不好玩。然后关于求上帝之数，你给出的算法确实能给出上帝之数的一个下界（比如大于19之类的结论），但我们想知道的是，上帝之数到底是多少？根据你给出的算法，你除了找出所有最远状态，也确实没什么更有效的办法了对吧？

---

作者: pengw    时间: 2015-2-27 17:40:42



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

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 18:36:39

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

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

---

作者: pengw    时间: 2015-2-27 19:12:47

昨天，突然有灵感，弄出了一种优化方法，有22%的效果,如果优化的结果是,每一个转式都最短转式(即这个转式就是自已生成状态的唯一最短转式),那问题简单多了，正在完善中。

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

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 19:31:29

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

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

---

作者: pengw    时间: 2015-2-27 20:08:12



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

---

作者: pengw    时间: 2015-2-27 20:15:59

回54楼，你认为，长度不大于N的所有转式(要么偶数步,要么奇数步)的有效（每一个都是某状态的唯一最短转式)百分比是多少?

---

作者: 黑白子    时间: 2015-2-27 20:29:02

看来，寻找最远状态好比寻找素数公式那样的难，除非有新的魔方理论或数学工具诞生。

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 20:30:57

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

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

---

作者: pengw    时间: 2015-2-27 22:03:37



回58楼：

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

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 22:06:10

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

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

---

作者: pengw    时间: 2015-2-27 22:13:29

确认26是最终值?有资料链接?

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 22:17:49

pengw 发表于 2015-2-27 22:13
确认26是最终值?有资料链接?

http://cube20.org/
他们声称是26，我没法证明或者证伪。

---

作者: 黑白子    时间: 2015-2-27 22:32:57

铯_猪哥恐鸣 发表于 2015-2-27 22:17
http://cube20.org/
他们声称是26，我没法证明或者证伪。

26步的状态是1个还是3个?他们写的是3?

---

作者: pengw    时间: 2015-2-27 22:34:04



490,000,000个20步中，有没有不含180/步的20步?还是每个20步都必含180/步?没有说明,如果没有说明,凭什么确定90/步,26步就是最远状态?

---

作者: pengw    时间: 2015-2-27 22:37:14

如果UU2算二步，UUU算三步，U‘算一步，站在状态的角度，应该算几步?

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 22:43:29

pengw 发表于 2015-2-27 22:34
有没有不含180/步的20步?还是每个20步都必含180/步?没有说明,如果没有说明,凭什么确定90/步,26步就是最远状 ...

这个问题你问我没用，我无法回答你，反正他们声称26步就是最远状态，并且也给出了这个状态，我前面用java贴了。

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 22:44:10

pengw 发表于 2015-2-27 22:37
如果UU2算二步，UUU算三步，U‘算一步，站在状态的角度，应该算几步?

应该算1步，这个是国内外公认的。

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 22:46:06

黑白子 发表于 2015-2-27 22:32
26步的状态是1个还是3个?他们写的是3?

这三个状态是互为同态，无非就是打乱方向改一下。后面的问号表示他们也不确定是否只有这一组状态需要26步。

---

作者: pengw    时间: 2015-2-27 22:48:50



如果存在一个20步，比"F U' F2 D' B U R' F' L D' R' U' L U B' D2 R' F U2 D2"再多或少一个180/步，是不是可以认为25，26，27（90/步)都是最远状态?

---

作者: 黑白子    时间: 2015-2-27 22:51:29

pengw 发表于 2015-2-27 22:34
有没有不含180/步的20步?还是每个20步都必含180/步?没有说明,如果没有说明,凭什么确定90/步,26步就是最远状 ...

20步和26步没有关系，二者标准不同。
20步是无论90度、180度还是270度都算一步，以层为旋转单位。
26步每步都是90度，无论正负90度都是1步，只有U‘，没有UUU，否则就不是最少步了。

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 22:54:29

pengw 发表于 2015-2-27 22:48
如果存在一个20步，比"F U' F2 D' B U R' F' L D' R' U' L U B' D2 R' F U2 D2"再多或少一个180/步，是不是 ...

70楼替我回答了这个问题。20步和26步没有关系，两个结果是分别算出来的。比如20步好几年前就算出来了，26步则是去年暑假才算出来的。计算它们用的时间也不同，前者是35CPU年，后者是29CPU年。

---

作者: 黑白子    时间: 2015-2-27 22:55:56

站在状态的角度，UUU算三步，U‘算一步。通俗地说，步数就是2个状态之间的交通路线。

---

作者: pengw    时间: 2015-2-27 22:59:51

通过69楼的质疑，可以看出，180度/步换算成90度/步之后的荒谬，即便是不改定义，那么是否可以认为不含180/步的20步与含180/步的20等长?

---

作者: pengw    时间: 2015-2-27 23:02:37

事实上，90/步是改变魔方的最小单位，使用90/步，才能避免69楼中的荒谬

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:04:18

pengw 发表于 2015-2-27 22:59
通过69楼的质疑，可以看出，180度/步换算成90度/步之后的荒谬，即便是不改定义，那么是否可以认为不含180/步 ...

在HTM意义下它们确实等长，但在QTM意义下它们是不等长的，这并不是矛盾。另外，我不是很能理解什么叫“再多或少一个180度”？多或少一个180度状态就变了，而很有可能达到这个状态只能恰好有这么些个180度也未必对吧？

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:04:57

pengw 发表于 2015-2-27 23:02
事实上，90/步是改变魔方的最小单位，使用90/步，才能避免69楼中的荒谬

是的，我把你这句话理解为，你认为HTM不合理，应该使用QTM，除此之外的讨论依然是没问题的，对吧？

---

作者: pengw    时间: 2015-2-27 23:06:43

照70楼的定义，OK，20步(90/步)同样也是最远状态,也就是说,20步,21步,22步...40步(这里都是90/步)全是等价的最远状态,是这样吗?

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:08:10

pengw 发表于 2015-2-27 23:06
照70楼的定义，OK，20步(90/步)同样也是最远状态,也就是说,20步,21步,22步...40步(这里都是90/步)全是等价的 ...

应该这么理解：
在HTM意义下，必须使用20步才能达到的所有状态都是最远状态。
在QTM意义下，必须使用26步才能达到的所有状态都是最远状态。
而在HTM意义下的最远状态在QTM意义下并不一定是最远状态，反之亦然。

也就是说，在讨论最远状态之前，我们首先需要定义怎么算一步，如果不定义怎么算一步的话显然没法讨论。
20步是最远状态的前提是我们把180度或90度都作为1步，如果没有这个前提，那么20步这个结论是没有意义的。

根据你的观点，很显然180度应该算两步，也就是说只有90度才算1步。那么在这个前提下，他们通过计算，得到了26这个数字，这个结果和之前的20没有任何关系。

---

作者: pengw    时间: 2015-2-27 23:10:30



难到最远状态还有多重互不兼容的定义?

---

作者: pengw    时间: 2015-2-27 23:14:21



若180/步,ULF,ULF2,U2L2F2等长,且遍历的状态也相同,对吗?

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:15:06

pengw 发表于 2015-2-27 23:10
难到最远状态还有多重互不兼容的定义?

当然有，既然说“远”，那么其实你已经在魔方状态中定义了一个“距离”的概念。即如果两个状态可以通过n步相互转换，则它们的“距离”为n。如果没有“距离”的概念，“远”或“最远”是没意义的。然后最远状态显然与“距离”的定义有关。比如我完全可以定义距离为“两个状态转化成54个颜色后不同颜色的数量”，那最远状态显然也是可以定义的，只是和我们讨论的又完全不一样了。

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:15:40

pengw 发表于 2015-2-27 23:14
若180/步,ULF,ULF2,U2L2F2等长,且遍历的状态也相同,对吗?

是的，在HTM意义下它们等长。当然根据您的观点，我们应该采用QTM来定义距离更合适。那么在QTM意义下它们三者的步数分别是3步，4步和6步，它们不等长。

---

作者: pengw    时间: 2015-2-27 23:24:22



如果以改变魔方状态的最小转量的绝对值做为距离单位,http://cube20.org/的上帝之数就太有问题了,所以你说26是最远状态,我无法认可,因为照cube20.org的定义,也可以同时说20,21,25,26.27...40都同为等长最远状态

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:27:07

pengw 发表于 2015-2-27 23:24
如果以改变魔方状态的最小转动做为距离单位,http://cube20.org/的上帝之数就太有问题了,所以你说26是最远状 ...

cube20.org并没有定义180度为1步，而是给出了两种不同的定义：QTM或HTM。前者与我们的讨论一致，后者180度算作1步。
若采用QTM，cube20.org给出了26步的结论。
若采用HTM，cube20.org给出了20步的结论。

对我们来说我们只关心26，直接无视20这个结果就好了。

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:31:58

pengw 发表于 2015-2-27 23:24
如果以改变魔方状态的最小转量的绝对值做为距离单位,http://cube20.org/的上帝之数就太有问题了,所以你说26 ...

你的推论并不准确。如果改成以下的说法就准确多了（准确，但不一定正确）：
根据cube20.org的定义，HTM意义下的最远状态在QTM意义下可能是20, 21, ..., 40步。也就是说QTM意义下的20, 21, ..., 40都有可能是HTM意义下的最远状态。当然这和QTM意义下的最远状态无关。

---

作者: pengw    时间: 2015-2-27 23:33:19

cube20.org找出的众多20步中,是不是还存在大于26步的?28？30?最大应该是40，哈哈

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:34:46

pengw 发表于 2015-2-27 23:33
cube20.org找出的众多20步中,是不是还存在大于26步的?28？30?最大应该是40，哈哈

并没有，一个状态在HTM意义下是最远状态，我们只能说在QTM意义下它至少需要20步才能还原。但需要20，还是21, 22, ...，我们并不知道。所以他们才继续花了29CPU年的额外计算，完全抛弃之前计算的20步的结果，得到了QTM意义下26步的结论。

请你注意，是先定义的距离，再去求解的。比如我一开始定义HTM，那么之后我在计算的时候会肆无忌惮的使用180度转动，那在这种情况下我算出来的公式（注意，是公式，而不是状态）在QTM意义下确实可能比较长，比如大于30步，但这和我们在QTM意义下计算最远状态没关系。

注意我前面一再强调是“公式”而非“状态”。比如某个状态，可能存在一个24步的且没有180度的转动序列可以达到它，但为了证明HTM意义下的上帝之数，我必须找到一个不超过20步的，甭管有没有180度转的公式。很可能这个公式里180度转很多，以至于在QTM意义下这个公式可能有30步，但这并不意味这这个状态在QTM意义下须要30步才能达到。

---

作者: pengw    时间: 2015-2-27 23:38:19

我一直认为，180/步，是自欺欺人的定义，这种定义导致的问题还不止上面这些，甚至还模糊了状态的奇偶性，导致某些描述变得似是而非，自相矛盾，以后再讨论

---

作者: pengw    时间: 2015-2-27 23:40:15

建议cube20.org还是定义距离单位是90/步!

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:41:41

pengw 发表于 2015-2-27 23:38
我一直认为，180/步，是自欺欺人的定义，这种定义导致的问题还不止上面这些，甚至还模糊了状态的奇偶性，导 ...

我再次强调，cube20.org中关于26步部分的定义完全基于90度为1步，180度为2步的前提，与我们的讨论完全一致。请你不要陷入20步的误区，这完全是两次不同的独立的计算，完全没有任何关系。

并且鉴于我们都认为180度为1步没有意义，应该记为2步，在之后的讨论中我不希望再看到20这个最远距离的值，这个数字在我们的讨论中没有任何意义。

---

作者: pengw    时间: 2015-2-27 23:42:49

我现在只能相信26步是较远状态而非最远状态,哈哈

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:44:10

pengw 发表于 2015-2-27 23:42
我现在只能相信26步是较远状态而非最远状态,哈哈

请你看一下我90楼的回复，在 cube20.org/qtm 中确实是以90度为1步，180度为2步进行的计算和分析，与我们应该是达成共识的。至于180度为1步的部分我认为和我们的讨论没关系，可以直接跳过。

---

作者: pengw    时间: 2015-2-27 23:50:24

那么他们标出的大大的20又是什么意思?

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:52:00

pengw 发表于 2015-2-27 23:50
那么他们标出的大大的20又是什么意思?

那是HTM意义下的计算结果。如果你是想问HTM存在的意义？我可以给你的一种解释是：
那是给玩速拧的那帮人看的。对他们来说转180度和转90度一样快，自然希望转的步数越短越好。而且很显然，魔方圈子里玩速拧的人肯定比玩理论的人多多了。作为研究理论的我们直接跳过这部分好了。

当然除了HTM，QTM还有别的定义呢，比如R L'也记为1步的STM等等。很多时候只是为了满足各种需求（比如机器人解魔方等等情况下过于频繁地换转动轴其实很坑的）。

---

作者: pengw    时间: 2015-2-27 23:54:47

看过QTM,这才是正确的方向,问题是,他们也只算出13步的状态就停止了

---

作者: pengw    时间: 2015-2-27 23:57:32

看过QTM,这才是正确的方向,最近状态才三个?

---

作者: 铯_猪哥恐鸣    时间: 2015-2-27 23:57:55

pengw 发表于 2015-2-27 23:54
看过QTM,这才是正确的方向,问题是,他们也只算出13步的状态就停止了

那是两列，你看仔细一点。不过总之人家给出了26步的结论，而且讨论的背景和前提与我们是一致的，我认为他们的部分结论还是可以参考的。下一步是时候进一步讨论你在1楼给出的算法了。

---

作者: 铯_猪哥恐鸣    时间: 2015-2-28 00:00:20

pengw 发表于 2015-2-27 23:57
看过QTM,这才是正确的方向,最近状态才三个?

根据他们的说法，最远状态至今为止他们只发现了3个，并且还是具有同态关系的3个，所以说是只有1个也不为过（因为这三个在结构上是一样的）。只有到底是不是三个，是否有可能漏了别的没发现的最远状态，我也不得而知了。

---

作者: 黑白子    时间: 2015-2-28 08:37:00

铯_猪哥恐鸣 发表于 2015-2-28 00:00
根据他们的说法，最远状态至今为止他们只发现了3个，并且还是具有同态关系的3个，所以说是只有1个也不为过 ...

把另外两个也贴出来吧，让我看看什么样子。

---

作者: 黑白子    时间: 2015-2-28 08:39:38

我有点不明白了，一个状态不是具有48个同态吗？他们怎么说只有3个同态呢？

---

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

Powered by Discuz! X2