魔方吧·中文魔方俱乐部

标题: “解集球” [打印本页]

作者: yukunlin 时间: 2008-8-20 10:08:25 标题: “解集球”

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

作者: 汪小光 时间: 2008-8-20 10:17:13

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

作者: junior_sky 时间: 2008-8-20 10:24:21

我不喜欢文章

作者: yukunlin 时间: 2008-8-20 10:37:12 标题: 对于任意一种复原方法（竟然没抢到自己的沙发）

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

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

作者: 魔鱼儿 时间: 2008-8-20 10:41:31

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

作者: pengw 时间: 2008-8-20 10:53:17

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

作者: yukunlin 时间: 2008-8-20 16:00:28 标题: 没有啊没有啊

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

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

作者: pengw 时间: 2008-8-20 16:19:03

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

作者: yukunlin 时间: 2008-8-20 18:09:30 标题: 回楼上

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

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

作者: pengw 时间: 2008-8-20 19:12:18

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

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

作者: pengw 时间: 2008-8-20 19:13:53

我认为还是用一颗树来组织更合适，任意状态之间的关系都可以使用同一颗树，这个道理是不言而喻的

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

作者: 独树 时间: 2008-8-20 19:26:17

好长的文章看着就头晕......

作者: 刘超 时间: 2008-8-20 19:34:33

通俗点了，这样我不懂的

作者: kexin_xiao 时间: 2008-8-20 19:46:17

树状结构,这个看明白了

作者: pengw 时间: 2008-8-20 20:13:41

树的问题最早由乌木提出来，后被乌木否决，我又接着分析，认为可行，去年我就发表算法了，权衡方方面面，树应该是概念最清晰，使用最直观，占用资源最少，表达最自然。球面网好看，但可能不好组织，甚至不好用，占用资源惊人，只是我个人的看法，再次讨论也是一件有益之事。

作者: yukunlin 时间: 2008-8-20 23:31:11

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

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

作者: pengw 时间: 2008-8-21 00:15:04

可能你没有看过我以前的算法。重复之前已被剪枝，沿根一直向上，到任何一个节点都是最短路径，或任者结点或叶一直下树到根都是最短路径，弯路回路都没有，这不是比球面简单直观很多？你可能要问我，其它任意二个结点的的最短路径又该怎么办，很简单，还是在同一颗树上找，仍然是直上或直下，不可能吧？完全可能！具体怎么做你会想明白的，这里我不便说明，不想为一些白痴做铺垫。
 
 
至于球面，我很想听你描述这个球面是如何不重复就搭建完毕，更想听你描述是如果展开最小步搜索。

[ 本帖最后由 pengw 于 2008-8-21 00:18 编辑 ]

作者: bbshanwei 时间: 2008-8-21 22:18:23

这让我想起了计算机的编码结构。

作者: 知Shmily足 时间: 2008-8-21 22:20:50

配个图解释解释吧！！

作者: noski 时间: 2008-8-21 22:40:12

原帖由 pengw 于 2008-8-21 00:15 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=219255&ptid=12838" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 可能你没有看过我以前的算法。重复之前已被剪枝，沿根一直向上，到任何一个节点都是最短路径，或任者结点或叶一直下树到根都是最短路径，弯路回路都没有，这不是比球面简单直观很多？你可能要问我，其它任意二个结点的的最短路径又该怎么办，很简单，还是在同一颗树上找，仍然是直上或直下，不可能吧？完全可能！ ...

是不是求任意两个结点的最短路径的时候，用一个简单的转换，把这两个结点中的一个转换为树的根？

作者: yukunlin 时间: 2008-8-21 23:40:48 标题: 没错，从任意节点看整颗树，都是一样的，任意一点都可以成为根节点

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

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

作者: pengw 时间: 2008-8-21 23:42:51

回20楼，很对

作者: pengw 时间: 2008-8-21 23:43:31

而球面网包括太多的同构

作者: pengw 时间: 2008-8-21 23:56:35

回21楼，正是因为每一个状态都可以是根，所以树相对球才具有更大的优势

作者: Cielo 时间: 2008-8-22 12:37:56

呵呵楼主厉害！
 
你所说的“解集球”其实就是群论中的凯莱（Cayley）图。
 
对于普通3阶魔方群（也就是说不考虑中心块方向）来说，每个状态就是这个群的一个元素，共有n约等于4.3*10^19个元素。复原态就是单位元，用 I 来表示。而这个群的生成元组为复原态分别经过U、D、R、L、F、B操作后得到的6个状态。
此时我们可以用一个生成元的序列，比如U，UR等等来代表该状态，注意：同一个状态有无数种不同的序列表示方法，但因为生成元之间会满足一些关系比如U^4=I，(UR)^105=I等等，所以不同的序列是可以代表同一个状态的。
 
那么我们可以在空间里或者平面上画出n个点，每个点代表一个状态，也就是群里的一个元素。
 
生成元U、D、R、L、F、B再加上它们的逆U'、D'、R'、L'、F'、B'构成一个集合{U、D、R、L、F、B、U'、D'、R'、L'、F'、B'}，如果一个状态可以通过该集合中的一步变为另一个状态，那么就把这两个状态用一条线连起来。这样就得到了一个图，这就是群论中的凯莱图，楼主能自己想出来确实厉害！
 
另举一例：对于整数加法群来说，0是单位元，1是生成元。{1，-1}是生成元及其逆组成的集合。
在平面上画出若干个点，它们可以与整数一一对应起来。点A所代表的整数如果通过加上集合中的一个数得到点B代表的整数，那么点AB就用线连起来。这样恰好得到数轴，这就是整数加法群的凯莱图！

作者: yukunlin 时间: 2008-8-22 14:04:02 标题: 啊啊

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

作者: 乌木 时间: 2008-8-22 18:03:36

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

态态关系网的最小网眼.JPG

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

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

附件: 态态关系网的最小网眼.JPG (2008-8-22 18:03:36, 11.78 KB) / 下载次数 22
http://www.mf8-china.com/forum.php?mod=attachment&aid=MjM4MTl8Y2U2MTA5ZmR8MTcxNjU1OTQxNHwwfDA%3D

作者: yukunlin 时间: 2008-8-22 22:50:39 标题: 树的指向只能是同向的

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

作者: 乌木 时间: 2008-8-22 23:39:49

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

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

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

附件: 态态关系网的最小网眼－2.JPG (2008-8-22 23:39:49, 20.69 KB) / 下载次数 23
http://www.mf8-china.com/forum.php?mod=attachment&aid=MjM4Njl8ZGY3Y2VhNWR8MTcxNjU1OTQxNHwwfDA%3D

作者: kexin_xiao 时间: 2008-8-23 12:03:25

学习！

作者: 知Shmily足 时间: 2008-8-25 20:23:22

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

作者: S!x.. 时间: 2009-1-25 12:18:28

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

作者: jackytsz 时间: 2009-6-14 01:55:44

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

作者: noski 时间: 2009-8-1 10:30:58

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

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

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

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

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

作者: boy314 时间: 2009-8-2 17:58:56

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

欢迎光临魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)