“解集球”

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>

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 编辑 ]

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 编辑 ]

yukunlin

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

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

yukunlin

<P>其实，我引入球的概念并不是改进算法</P>
<P><BR>首先<BR>关于点是否要分布到球的内部的问题<BR>我在定义的时候，将“解集球”定义为超四维球<BR>这就是想让点都分布在球面上<BR>因为维数的多少对计算机不存在任何思考的障碍<BR>然后，人脑就可以把球当成三维，点当成在球面上思考</P>
<P>再者<BR>树和图的差别其实也不大<BR>特别是对广度搜索<BR>只要在扩展节点的时候注意规避重复<BR>算法基本是一样的</P>
<P><BR>我之所以提出“解集球”<BR>其黄金价值在于对任意解法的研究（人的解法）<BR>以研究能否有更适合人的解法<BR>（比CFOP）</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>问一下</P>
<P>我的球上的数据是没有任何一点重复的</P>
<P>反而我觉得树是一定会有重复的</P>
<P>能否解释一下你是怎么想的？</P>
<P>&nbsp;</P>
<P>为什么树的空间复杂度“解集球”小呢</P>
<P>我怎么觉得“解集球”反而更小呢</P>
<P>&nbsp;</P>
<P>能否解释一下</P>
<P>谢谢</P>

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

yukunlin

<P><IMG src="http://www.newhuaxue.com/UploadFiles/2006-3/20063119222425491.gif" border=0></P>
<P>&nbsp;</P>
<P>这是足球烯 一种碳的同素异型体分子结构</P>
<P>他的每个节点是3度的</P>
<P>“解集球”类似这个结构</P>
<P>只不过是12度的</P>
<P>用它可以证明：</P>
<P>任意一个公式重复操作，一定可以恢复原状态</P>

[ 本帖最后由 yukunlin 于 2008-8-21 23:43 编辑 ]

yukunlin

不好意思，竟然跟先哲的思想重复了

yukunlin

<P>习惯上从上到下</P>
<P>而且节点之间有严格的父子关系</P>
<P>图 就不存在，</P>
<P>节点是平等的 </P>
<P>恩，还是不要把180度算成一步吧，</P>
<P>这样会把问题复杂化</P>
<P>&nbsp;</P>
<P>&nbsp;所以没有三边形网眼</P>
<P>谢谢</P>