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