二阶魔方的最远状态 (第11步)

noski

我还是赞同3674160这个结果，另一个结果我也没想清楚是怎么算出来的。<BR>
<BR>
我计算的时候都是固定一个角块还消同态的。比如二阶，固定BLD块，则只能进行F、U、R三个操作（因为拧L面就等价于拧R面，其它同理）。除了BLD块的七个块，用排列组合算出来就是7！x 3^6，即3674160。<BR>
<BR>
而且状态数与90还是180应该没有关系。ggglgq的结果比黑王子的结果小了将近一半，可能是除去了镜像的状态吧。2*1841970 - 3674160＝9780，我没验证，这个数很可能就是左右对称的状态个数。

乌木

<P>噢，这问题细究起来颇多内容啊。</P>
<P>&nbsp;</P>
<P>还有，怎么两种不同的统计步数的方法中，最远态的步数会一样的，都是11步呢？不好理解。</P>
<P>&nbsp;</P>
<P>好比，两地距离是一定的，但用公里记数和用英里记数，数值应该不同。这比喻恰当吗？</P>
<P>&nbsp;</P>
<P>继续请教。</P>
<P>－－－－－－－－－－－－－－</P>
<P>我搞错了。两种不同的统计步数的方法中，最远态的步数是不一样的，一为11步，另一为14步，没错。</P>

[ 本帖最后由 乌木 于 2007-12-27 19:27 编辑 ]

乌木

<P>这80楼内容看起来蛮吃力的。</P>
<P>&nbsp;</P>
<P>我想，“状态A做一个R操作”——一定得到A的子代之一，记作A2吧。把A2当作老祖宗，走同样的11步T(11)的话，得到的态距离A是12步了。但A的最远态仅11步，所以实际上是越过了A的最远态集（2644个态）之后又倒退回一步，回到属于A的10步子孙集（623800个态）了。（此说似乎有点问题？一时也理不清什么问题）。</P>
<P>&nbsp;</P>
<P>80楼的另一些内容一时还未看明白，慢慢再说吧。</P>

[ 本帖最后由 乌木 于 2007-12-23 19:37 编辑 ]

noski

这么一说。。<BR>
如果这样理解：比如R2可以看成两个R，所以带R2这种180度操作的11步其实相当于12步，那么这些状态就是“虚假的”最远状态，而只用11步90度旋转得到的才是“真正的”最远状态。<BR>
那么，前面列出的那2644个状态的转法应该都能找到不含180度操作的公式，用11步完成（因为10步完成的话前面会搜索出来）。<BR>
又想到，如果最远状态的转法不唯一，是因为180度操作的存在的话，那只用90度操作的转法是唯一的么？

乌木

好像1楼的歩骤不仅仅是一连串90°，也含有180°的，而且把180°算作一步。否则，某一态的180°转某一表层所得的后代岂不漏计入状态总数了吗？

乌木

<P>83楼我说，“ ‘状态A做一个R操作’——一定得到A的子代之一，记作A2吧。把A2当作老祖宗，走同样的11步T(11)的话，得到的态距离A是12步了。但A的最远态仅11步，所以实际上是越过了A的最远态集（2644个态）之后又倒退回一步，回到属于A的10步子孙集（623800个态）了。（此说似乎有点问题？一时也理不清什么问题）。”</P>
<P>&nbsp;</P>
<P>&nbsp;现在初步想想，此说可能错在：A的2644条路线之一T(11)，使A变成2644中的某一态。但是，A经过[ R＋T（11）]不见得一定“越过”那2644个态之一再倒退一步什么的，甚至说不定在某一半途就叉到不知什么地方去了呢？此事得有理论论证才清楚。 </P>
<P>&nbsp;</P>
<P>所以，noski的思路别受我干扰才好。</P>

[ 本帖最后由 乌木 于 2007-12-23 19:54 编辑 ]

noski

啊。。80楼的说法有很大问题，不对。。

ggglgq

期末杂事颇多，以后如果不能及时回复大家的帖子，也请大家谅解！

非常欢迎大家探讨魔方的最少步算法及其深刻的循环变换理论。

首先，正六面体二阶魔方的总状态数为 3674160 。
从复原态出发，其分布如下（旋转 180° 按一步计算）：
复原态 1
第01步 9
第02步 54
第03步 321
第04步 1847
第05步 9992
第06步 50136
第07步 227536
第08步 870072
第09步 1887748
第10步 623800
第11步 2644
第12步 0
-----------------------------
总 数 3674160



其次，正六面体二阶魔方“考虑角块绝对位置”的总状态数为 88179840 。
从复原态出发，其分布如下（旋转 180° 按一步计算）：
复原态 1
第01步 18
第02步 243
第03步 2874
第04步 28000
第05步 205416
第06步 1168516
第07步 5402254
第08步 20775972
第09步 45391890
第10步 15139920
第11步 64736
第12步 0
-----------------------------
总 数 88179840

[ 本帖最后由 ggglgq 于 2009-1-8 09:17 编辑 ]

ggglgq

本人开发 正六面体二阶魔方最远状态软件 时采用了 48 “同态”优化技巧。
在此“技巧”下，本人开发的程序只需计算总状态数的约 1 / 48 个状态，就可以
完成正六面体二阶魔方最远状态的计算。下面是 48 “同态”优化技巧下的结果。

正六面体二阶魔方经过 48 “同态”后的“不同状态”的总状态数仅为 77802 。
从复原态出发，其分布如下（旋转 180° 按一步计算）：
复原态 1
第01步 2
第02步 5
第03步 19
第04步 68
第05步 271
第06步 1148
第07步 4915
第08步 18364
第09步 39707
第10步 13225
第11步 77
第12步 0
------------------------------
总 数 77802 ≈ 3674160 / 48


正六面体二阶魔方“考虑角块绝对位置”的“不同状态”的总状态数仅为 1841970 。
从复原态出发，其分布如下（旋转 180° 按一步计算）：
复原态 1
第01步 2
第02步 9
第03步 71
第04步 637
第05步 4449
第06步 24653
第07步 113073
第08步 433709
第09步 947300
第10步 316616
第11步 1450
第12步 0
---------------------------------
总 数 1841970 ≈ 88179840 / 48

[ 本帖最后由 ggglgq 于 2009-1-8 09:18 编辑 ]

ggglgq

先送大家一个《正六面体二阶魔方-48“同态”图解》软件（点击下载）。

下面简单介绍一下本人的 48 “同态”优化技巧：

1.对于每一操作，都存在一个“左右镜像（对称）操作”（只考虑一个，不要考虑太复杂）

2.对于正六面体二阶魔方的每一操作 T ，都存在 4 * 6 个相对位置的操作态。相当于：
把 n 号位置移到“后左上 0 位置”后再进行操作 T ，共有 4 * 6 个相对位置的操作态。

由 1、2 即可得到 正六面体二阶魔方每一操作的 48“同态”操作。详见
《正六面体二阶魔方-48“同态”图解》

由 正六面体二阶魔方 48 “同态”优化技巧可知，知道 正六面体魔方 的一个操作 T ，
就可以知道它的 48 个“同态”操作 T48 ，效率提高了近 48 倍！ 48 “同态”优化技巧
可以大大缩短程序的运行时间，提高程序的运行效率。

UID93 帖子1298 精华6 积分3956 阅读权限100 在线时间198 小时 注册时间2004-6-1 最后登录2009-1-8 查看详细资料 编辑用户 禁止用户 编辑 引用 使用道具 报告 评分 回复 TOP

[ 本帖最后由 ggglgq 于 2009-1-8 09:21 编辑 ]