“解集球”

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>

boy314

很复杂，我看不懂，但是大家比我聪明，一定会懂

noski

原帖由 乌木 于 2008-8-22 23:39 发表


不妨比较一下：网络改为树形后，态3何去何从？莫非态树上将保留多多的同态？如果态3任意取两个位置之一，另一处少了一个儿子，这态树反映的信息还完整吗？或许，没有同态的态树在探求“树高”－－最远态的步数、 ...

您的配图还真有趣，哈哈！

虽然在一棵树中，一个子态只存在于一个父态之下，与其它父态的信息被省略，但这态树反映的信息是完整的，几个父态稍加判断就可以得出。

比如从子态出发走一步，可以走到12个不同的相邻态，那么只要判断一个这12个相邻态是哪一代的，就可以推断出这个子态的父态有哪些了。

jackytsz

我不知道我理解對不對...
如果不以長度 而是以箭頭的數量
豈不是知道最少步數(在已經有這"球"後)
那180度也算一步 就加多一個箭頭
距離不平均的問題就解決了

S!x..

天啊..
好晕..
实在不懂呃.....

知Shmily足

LZ能不能再简单地概括一下呢？

kexin_xiao

学习！

乌木

原帖由 yukunlin于 2008-8-22 22:50 发表   习惯上从上到下而且节点之间有严格的父子关系……

不妨比较一下：网络改为树形后，态3何去何从？莫非态树上将保留多多的同态？如果态3任意取两个位置之一，另一处少了一个儿子，这态树反映的信息还完整吗？或许，没有同态的态树在探求“树高”－－最远态的步数、树的各层的态数等问题上还是有用的。
            

[ 本帖最后由 乌木 于 2009-1-25 17:33 编辑 ]

yukunlin

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

乌木

是不是这样的图不是树形，而是网络形的？是不是最小的“网眼”是四边形的？好像不可能有三边形的“网眼”，对吗？比如：

                       
如果180°转算一步，倒是有三边形网眼了，比如上图，再增加两条对角线即可。如果考究一点，两条对角线不许相交的话，那就要“立交”，二维不够了，得三维描述。

[ 本帖最后由 乌木 于 2009-1-25 17:31 编辑 ]