离初始状态最远的图案 - 第5页 - ★ 计算机最少步理论版 (Software Solver Theory) - 魔方吧·中文魔方俱乐部

lsshao 发表于 2007-5-24 09:33:17

“电算还原法”费事的魔方图案，“经典还原法”也许容易。反之亦然：“经典还原法”费事的魔方图案，“电算还原法”也许容易。必须具体问题具体分析，不可一概而论。如果是角块不变化，每一边块，就是12个边块全部在原地翻面的魔方图案，用“经典还原法”是很快的。这个魔方图案熟手判读用不了10秒钟，判读完毕立即开始还原，还原需要58步，如果手稍快，在1秒钟之内转2次以上，不到30秒就还原了。加上观察，总时间也不过40秒。而且应该是可以背转的。有现成的上层4个边块原地翻面的旋转程序，很快就可完成这层的4个边块原地翻面，用17或18步。这套旋转程序如下：右反，左正，前2，右正，左反，上2，右反，左正，前正，右正，左反，上2，右反，左正，前2，右正，左反，（上反）。[用外国字表示为：R'LF2RL'U2R'LFRL'U2R'LF2RL'（U'），错了吗？]要是仅用于上层边块翻面，上述程序的最后一步，即括号中的那步，是可以视情况省略的。这套旋转程序的名称是“二二夹一”。熟手记住“二二夹一”，就可运用自如了，用不着背程序的烦琐内容。中间层的4个边块，调到上层后再用“二二夹一”
翻面。调动和返回各用3步，与“二二夹一”联动时可以合并，省下2步。当然,这58步远多于电脑算的最少步数,只是可以立即得到还原的结果。

zhaohal 发表于 2008-3-18 14:32:27

怎么看不到。。。。

wennywong 发表于 2008-4-8 12:26:22

谢谢,要好好学习

463976379 发表于 2008-6-1 19:57:34

五彩十字还原最少要多少步啊

yjw44 发表于 2008-7-9 00:19:26

cube319?好东西?去下载看看...

leftleft 发表于 2008-7-9 18:44:30

又发现好东西了，谢谢楼主！~

zengyoutry 发表于 2008-7-25 08:46:50

刚刚从网上载了CUBE319，还不会用，但对其原理很感兴趣呀！

yukunlin 发表于 2008-8-19 22:12:52

数据结构与算法

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

[ 本帖最后由 ggglgq 于 2008-8-20 22:02 编辑 ]

yukunlin 发表于 2008-8-19 22:13:26

为什么不换行啊

为什么不换行啊啊啊啊啊

ggglgq 发表于 2008-8-20 22:06:28

48 楼的帖子为您编辑好了。        呵呵，不错，支持一下。  请您参考：<A href="http://bbs.mf8-china.com/viewthread.php?tid=153&extra=page%3D1&page=6">循环变换球面网 59 楼以后的内容 </A>        <A href="http://bbs.mf8-china.com/viewthread.php?tid=153&extra=page%3D1&page=6">http://bbs.mf8-china.com/viewthread.php?tid=153&extra=page%3D1&page=6</A>  59 楼以后的内容             

[ 本帖最后由 ggglgq 于 2008-8-20 22:08 编辑 ]

页: 1 2 3 4 [5] 6 7

魔方吧·中文魔方俱乐部's Archiver

数据结构与算法

为什么不换行啊