“解集球”

yukunlin

<P>首先尝试用树来构建魔方的解</P>
<P>&nbsp;将复原的魔方看成根节点</P>
<P>&nbsp;第一转有12种可能，根节点有12个孩子域</P>
<P>&nbsp;第二转以及以后，为了避免与上一转抵消，一共有11重转法</P>
<P>&nbsp;所以从树的第二层开始，就是11叉树</P>
<P>&nbsp;但是一直这样发展下去，一定会有重复的节点</P>
<P>&nbsp;而且树的模型不能很好的反映状态之间的相邻关系</P>
<P>&nbsp;</P>
<P>&nbsp;那么用图</P>
<P>&nbsp;魔方约4。3×10^21种情况（实际要小一点）</P>
<P>&nbsp;平面上有这么多个点构成的图</P>
<P>&nbsp;每个点是12度的 即有12个点与之相连，权值为1，相邻的点表示可以一步互相转换的状态</P>
<P>&nbsp;最小还原方法就是某一点到复原点的最小路径</P>
<P>&nbsp;让我们想象一下一个超四维球体</P>
<P>&nbsp;它的表面上均匀分布着4。3×10^21个点</P>
<P>&nbsp;每个点与它临近的12个点相连（类似足球），我将这个球称作“解集球”</P>
<P>&nbsp;那么最小还原路径就是球体上两点的优弧，</P>
<P>显然“最远状态”这取决于相应球体的“直径”</P>
<P>&nbsp;由于球上的点是离散的，所以优弧和“直径”只是近似的等于最小还原路径和最远状态</P>
<P>&nbsp;同时可能存在并列最优的情况，比如12步是最短路径，有两种解法都是12步</P>
<P>&nbsp;</P>
<P>“解集球”的引入，我认为可以解决很多问题</P>
<P>比如，能否一次性遍历所有状态而不重复</P>
<P>根据一笔画问题，显然是可以的</P>
<P>它还可以给许多定义提供方便</P>
<P>比如：最远状态就是在“解集球”上关于球心对称的两点</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>最短路径的搜索方法：</P>
<P>&nbsp;因为要搜索短路径，所以用广度优先算法</P>
<P>&nbsp;用广度优先算法可以保证第一个得到的解一定是最优解（之一）</P>
<P>&nbsp;广度优先在“解集球”上的搜索范围相当于以初始状态为圆心的圆 </P>
<P>确切的说是 球冠的曲面 </P>
<P>如果初始状态是“最远状态”，</P>
<P>那么算法要翻越整个“解集球”，遍历所有情况，才能获得解</P>
<P>&nbsp;中途最多要保存“‘解集球’的‘大圆’的‘周长’”个状态 </P>
<P>这显然是不可忍受的</P>
<P>&nbsp;随着初始状态到复原状态的距离越来越远，要搜索的面积越来越大，</P>
<P>在定义域单调递增 它跟“解集球”的球冠的弧面的面积是成正比的，</P>
<P>导函数先曾后减 所以，路径越长，搜索时间越长</P>
<P>&nbsp;</P>
<P>&nbsp;我尝试用双向搜索 从初始状态和末状态同时搜索 </P>
<P>虽然如果初始状态仍然是“最远状态”，搜索的范围一样是整个“解集球”</P>
<P>&nbsp;那么双向搜索就没有起到它的优势 但是，对于不是“最远状态”的所有初始状态</P>
<P>，双向搜索的范围（正如它在平面上的优势一样）大大减小</P>
<P>&nbsp;所以双向搜索的平均否搜索范围要比单纯广度搜索小</P>
<P>&nbsp;同时他还有一个优点：</P>
<P>&nbsp;从末状态搜索出的中间状态可以长期保留，</P>
<P>方便以后用 从而降低时间复杂度</P>
<P>&nbsp;这次先说这么多</P>
<P>&nbsp;下次在深入的想一下</P>

汪小光

……没听懂……太强了，我慢慢理会理会……

junior_sky

我不喜欢文章

yukunlin

<P>对于任意一种复原方法</P>
<P>都有一个共同的特点</P>
<P>就是分段</P>
<P>比如CFOP就分成了C-F-O-P四段</P>
<P>&nbsp;由于每一步的各种公式的长度都比较近似</P>
<P>比如PLL都是十多步，我们暂且视作13步</P>
<P>那么在“解集球”上，所有PLL状态离复原状态的距离都近似的接近13 </P>
<P>也就是说，所有PLL状态都分布在以复原状态所在“解集球”直径上一点为圆心的圆上</P>
<P>且圆上每一点离复原状态的距离近似13 </P>
<P>由于近似，所以这个圆的圆弧是有宽度的</P>
<P>同理，C-F-O也都是这样的有宽度的圆</P>
<P>&nbsp;如果把地球的北极看成复原状态，南极看成最远状态</P>
<P>那么C-F-O-P就近似的是地球的4根纬线 </P>
<P>&nbsp;</P>
<P>所有的复原方法都符合这个性质</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>（这贴需要一点数据结构与算法的知识）</P>

[ 本帖最后由 yukunlin 于 2008-8-20 10:39 编辑 ]

魔鱼儿

楼主的文章不错,不过看着不大明白,,楼主的树状结构到是网络连接的一种方式 ,,能用到魔方上楼主也真是高人啊,呵呵

pengw

楼主的文章很有创意，我提一个问题，你是如何断定一个状态只有一个最远状态？如果是多个，又如何球心对球心？

yukunlin

<P>不一定只有一个最远的啊 </P>
<P>我有一次看到一个贴</P>
<P>说是证明了从最远到复原至少有12个最短路径</P>
<P>他说，因为是最远，所以随便转一下都更接近复原</P>
<P>所以至少有12种最短路径</P>
<P>&nbsp;我觉得，不一定</P>
<P>有可能有并行的几个最远状态</P>
<P>而且他们几个之间形成一个环行，</P>
<P>相邻的两个可以一步转换</P>
<P>&nbsp;原文中的确不太严谨</P>
<P>加上这句：</P>
<P>最远状态等于1或大于2</P>

[ 本帖最后由 yukunlin 于 2008-8-20 16:09 编辑 ]

pengw

我在想
1。这个球面能不能拉得园
2。结点能不能匀分

yukunlin

<P>1在三维空间，我不感肯定<BR>但是多维一定可以</P>
<P>圆是肯定的<BR>魔方有其特殊的对称性<BR>即，你 处于任何状态看别的状态，都是一样的<BR>你可以想象一下，把魔方转乱，再把贴纸撕下来，贴成复原状态<BR>每个状态其实都可以看成复原状态<BR>正是由于这种对称性，球一定是圆的，只有球才符合从任意角度看都是一样的</P>
<P>2由于每个点都是12度的所以也一定是均匀的</P>

[ 本帖最后由 yukunlin 于 2008-8-20 18:11 编辑 ]

pengw

回9楼，即是这个球可以组织成功，你是依据距离远近来组织的，也就是说，相对一颗树来说，你会有大量几乎是天文单位的重复数据，我担心。形象地举一个例子，如同让每个状态做根，将<FONT face="Times New Roman"> 8.85801*10<SUP>22</SUP></FONT>颗树根向外，冠向内编成一个巨球，这样一个球是不可能是单层的，有惊人的重复，事实上，一颗树就足够了。

[ 本帖最后由 pengw 于 2008-8-20 19:24 编辑 ]