魔方吧·中文魔方俱乐部

标题: 有没有这样的循环？ [打印本页]

作者: 山游008 时间: 2008-1-29 17:49:48 标题: 有没有这样的循环？

会不会存在一种循环，可以使魔方从一个状态，开始，经过每一个状态，然后再回到这个状态？

作者: 乌木 时间: 2008-1-29 18:51:31

这问题很有意思，各位不妨各抒己见。
 
我认为，普通三阶魔方（“三阶纯色魔方”）共有4千多亿亿个状态（初步的议论可参看：<A href="http://bbs.mf8-china.com/viewthread.php?tid=2624&extra=page%3D2" target=_blank>http://bbs.mf8-china.com/viewthread.php?tid=2624&extra=page%3D2</A>），别说它们各自不同，就它们之间的相互关系而言，任何两个状态都是有路可通的，因为，哪个态不是一步步拧出来的？它们可是一个“大家庭”啊！此外，任何两个态之间，有许多许多条路子可通！好像这些情况就够了，即，如果所说的循环不加什么条件限制的话，不难理解：1楼的问题的答案是肯定的。你们以为如何？
 
至于循环加上什么限制的话（譬如，限定每个态只能经过一次或若干次，等等），不知该如何考虑。

[ 本帖最后由乌木于 2008-1-29 18:59 编辑 ]

作者: w-inds. 时间: 2008-1-29 22:20:09

如果限定每个态只能经过一次或若干次,我觉得应该可以循环..
因为每一个态都从上个态变出来的,而且每个不同态之间都有联系,这样的话不同的态可以一直循环下去.
不知有没想错.

作者: 乌木 时间: 2008-1-30 00:27:12 标题: 回复 3# 的帖子

四千亿亿个态的关系并不是直线状的一长串，也不是无头无尾的一个大圆环。它们构成一个复杂的网络。譬如，态0，分别经UU'U2FF'F2RR'R2……共18种动作，得到18个第二代态；但是每个二代态的18个动作之中，必有一个就是态0。（考察反过来的变化时，就是说明这18个态的所有“后代”中至少具有18个同态－－态0，在那反过来变化的系统中，统计状态总数时必须消去17个同态。）故三代态有18×17个。再下去会有别的同态现象，并不是每一代数量的增加都是乘以17的。先是增加多于消同态引起的减少，后来反过来，减少多于增加。这是从状态数量之变化上来说的情况。虽然计算状态数量时采用消同态而避免了重复计算，但是，正因为有同态现象，所以某一个态及其一大帮后代完全可能既是这一态的后代，同时又是那一态的后代，甚至同属多个态的后代。由此，“编织”成复杂的“关系网”。
 
上面我说1楼问题的答案是肯定的，现在想想也仅是一种模糊猜想。因为，否则的话，岂不是这四千亿亿个状态除了出自同一个“老祖宗”外，后来会区分成两个或若干个互相不搭界的网－－犹如有人说存在多个互不相通的宇宙一般？
 
从咱们的烟兄那里买来一个魔方，可以相信它能拧出四千亿亿（记为N）个态中的任何一个；从N个态中的任一个出发，应该能拧出另外N－1个（其中包括一个复原态）态中的任一个，或分别拧出另外N－1个态。所以，我想1楼的答案不会是否定的吧？

[ 本帖最后由乌木于 2008-1-30 11:06 编辑 ]

作者: 山游008 时间: 2008-1-30 12:09:38

设第一个态是态0，则它的后代，也就是第二态和以后的态，会有跟态0相似的地方，就是遗传吧！而且相似处会逐渐减小，那么到最后是完全不同呢？还是完全一样？如果是完全不同那么这个循环是不存在的。相反则存在。
如果把这样的循环放到生物中，那么不是会出现大家共同的那个祖先了吗？
还有太极，太极生两仪，两仪生四像，四像生八卦，八卦又归太极。这也属于这种循环

[ 本帖最后由山游008 于 2008-1-30 12:15 编辑 ]

作者: 乌木 时间: 2008-1-30 14:25:06 标题: 回复 5# 的帖子

这和遗传、返祖之类好像不同吧？魔方的任何两个态可以互为上下代关系－－在某一“老祖宗”时，态a是态b的前辈；换了另一“老祖宗”时，有可能态b是态a的前辈。
 
此外，态0的子代不是仅仅一个，而是18个；第三代消了同态（和态0一样的态）后还有18×17个，这18×17个第三代中是否还有什么同态要消，我懒得去细查了。如果还有，在统计时也要消去重复的。以后每转出一个态，都要考察它是否属于此前已有的哪个态的同态，工作量极大。据说有些魔方类问题电脑也来不及计算。

[ 本帖最后由乌木于 2008-1-30 14:37 编辑 ]

作者: w-inds. 时间: 2008-1-30 18:41:49

这个问题够经典...看了乌木先生的解释觉得有道理.想了半天也不知道答案到底是能还是不能..

作者: 乌木 时间: 2008-1-30 20:21:02 标题: 回复 7# 的帖子

我不懂有关的理论，只能胡思乱想。不妨设想把魔方态态之间的变化路径用金属导线联接，每个结点即一个态。每个态都是同一老祖宗拧出来的，因此任何两个态之间都是可导通电流的。不管其间的电流具体是如何流动的，只要导通，就有理由认为：电源的一个输出端固定于某一态，电源的另一端依次去接触一个个结点。每一次都是“导通”，“导通”，……，历遍所有态就是完成了1楼所问的那种循环。我这么想没问题吧？

作者: 乌木 时间: 2008-1-30 20:30:44

其实，还可以进一步想想如何找出任意两个态之间的最短路线，这问题更有意义。据说至今还未解决。对这个问题所给出的答案当然要有理论证明，证明它的确是一条最短路线。这涉及数学，我是更不懂了。

作者: 山游008 时间: 2008-1-30 22:28:37 标题: 回复 6# 的帖子

扯到生物，是拿来比喻，乌木先生说的不是没有道理，从不同的态出发，情况就有可能相反。
也就是说不同的第一个态，走的路径都不相同，每一个太都有它特定的路径，那么有共用的吗？可以考虑一下这种路径``

作者: 乌木 时间: 2008-1-30 23:17:38

任意两个态之间的变化路径是很多的，具体例子就不必举了。其中哪一条算“特定路径”，似乎还没有定论。其中什么样的一条或若干条路径算是最短路径，至今尚未解决。
 
至于“共用路径”，那就是对付各种情况的“公式”嘛！任何状态代入某个公式，执行之后，所发生的的变化模式（！）都是一样的，所以才把那种路径专门叫作“公式”。这里所说的是变化模式，并不是说任何态代入某公式后都变成同一态了！

作者: pengw 时间: 2008-1-31 09:00:10

存在这样的一个公式，可以遍历所有状态，公式只能运行一次，中间状态必有重历，我不知道执行一次首尾同态的公式是否叫着公式循环，至少我不认为是公式循环，仅仅只有一次。一个公式的中间状态不重复，又能遍历所有状态的公式不可能存在，状态之间的关系是以树结构组织的，爬上一个树枝要想不退回来又去爬另一个树枝是不可能的。
 
另外，首尾同态的公式常被人盗用概念称为解决最小步问题的循环变换，其本质就是简简单单的相似变换，与最小步没有直接关系。

[ 本帖最后由 pengw 于 2008-1-31 09:08 编辑 ]

作者: 乌木 时间: 2008-1-31 12:20:35 标题: 回复 12# 的帖子

态树的结构应是一门不大不小的学问吧，我是没学过。我想，魔方态树比一般概念的树状结构复杂，由于同态现象，这一拨树枝完全可能和另一拨树枝有若干处因“合并”而“跳帮”式关联。大概示意如下：
 
 消同态成为跳帮状.GIF

[ 本帖最后由乌木于 2008-1-31 13:48 编辑 ]

附件: 消同态成为跳帮状.GIF (2008-1-31 13:19:32, 12.17 KB) / 下载次数 80
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTIyMTZ8YTNlYTQ4NDJ8MTc2MTg4MTA5NnwwfDA%3D

附件: 消同态成为跳帮状－2.GIF (2008-1-31 13:48:29, 8.46 KB) / 下载次数 82
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTIyMTl8ODI0MTc3MmZ8MTc2MTg4MTA5NnwwfDA%3D

作者: pengw 时间: 2008-1-31 13:12:46

我的分析结论是：以任意状态为根，所有的状态都可以上树。只要建立这颗树的数据库，即可推算出任意其它状态为根的情况。不过这颗树实在是太大了，三阶或以上恐怕就是挪用全球的存贮都难胜任。对仅有3百万左右状态的二阶，就是一个小学生也能用遍历法写程序完成所谓的最小步求解，根本无须相似变换（也称循环变换）帮助，哈哈哈。

[ 本帖最后由 pengw 于 2008-1-31 13:15 编辑 ]

作者: 山游008 时间: 2008-1-31 17:47:23 标题: 回复 11# 的帖子

这里的变化模式是指每一种不同的开始态,变化后而得到的态于上一个态的关系是一样的吧```我是这样理解的.态0与态1有一定的关系,态1和态2之间的关系就像态0与态1之间的关系,如此,最后态X又回到态0.

[ 本帖最后由山游008 于 2008-1-31 17:51 编辑 ]

作者: 乌木 时间: 2008-1-31 19:59:47 标题: 回复 15# 的帖子

你说的“态0与态1有一定的关系,态1和态2之间的关系就像态0与态1之间的关系,如此,最后态X又回到态0.”基本上属于公式的循环问题。如果去掉“态X”两个字，就说成“……最后又回到态0”，则就是说的公式循环问题。（详见：<A href="http://bbs.mf8-china.com/viewthread.php?tid=794&extra=page%3D1" target=_blank>http://bbs.mf8-china.com/viewthread.php?tid=794&extra=page%3D1</A>）
 
这样的公式循环（那怕循环上无数次），和楼主说的历遍所有态的特殊循环，差得太多太多，仅仅在四千亿亿个魔方态海洋中走了极小极小的一个小圈子。除非这个公式本身已经历遍所有态，那么，它做一遍就完成周游列国的任务了！无须考虑什么公式循环了，它就变成楼主所探索的东西了。

[ 本帖最后由乌木于 2008-1-31 20:22 编辑 ]

作者: 乌木 时间: 2008-1-31 21:22:17 标题: 回复 13# 的帖子

再看看“隔代同态”情况，也表明“态树”结构不同于普通树结构：（图没画全，仅作一些示例。）
 
 180°算一步，隔代同态.GIF

[ 本帖最后由乌木于 2008-1-31 21:35 编辑 ]

附件: 180°算一步，隔代同态.GIF (2008-1-31 21:30:01, 14.73 KB) / 下载次数 83
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTIyNDB8MTIwZjMzZGF8MTc2MTg4MTA5NnwwfDA%3D

作者: pengw 时间: 2008-1-31 22:35:16

只要任选一个状态做根构造一个状态树就行了，无须为每个状态构造一棵树，关键是这颗树的构造算法，及这颗树的规模，方法其实很简单，暂时不想说得太多，免又被某位大师说成是发扬光大他的理论。当初我的公式循环原理一文就被某大师说成是光大他的循环变换，而公式循环原理与相似变换是牛头不对马嘴，奇阶魔方没有同态，偶阶魔方在发牙之间就将同态剪掉。遍历仍然是最糟的最小步算法。

[ 本帖最后由 pengw 于 2008-1-31 22:41 编辑 ]

作者: 山游008 时间: 2008-1-31 23:00:08 标题: 回复 16# 的帖子

不太理解乌木先生的话,我是这样想的.
设魔方的所有状态数为N,起始态为态1,经过一定的路径{公式}得到态2,态2也经过这一个路径能得到态3,如此,态N再经过这个路径就能回到态1,在回到态1时已经把所有态走完.那么这样的路径不就是一个最大的循环,一个能走过所有态的循环了吗?

作者: 乌木 时间: 2008-1-31 23:30:59 标题: 回复 19# 的帖子

我说的是分别（！）每一转（！）即得到一个新态。消了同态之后，剩下总共4千亿亿个态。你说的“态1经过一个公式，……”，那么，做一遍这公式时一路上经历了多个态，继续再做一遍，又经历多个态，…………做这个公式若干遍之后，一定（！）能回到态1的！虽然这样总共也经历了很多态，但是一般而言，远远没有历遍4千亿亿个态。楼主问的是历遍4千亿亿个态的步骤。当然，目前没人能给出具体答案，只能从概念上议论议论。
 
比如，<A href="http://bbs.mf8-china.com/viewthread.php?tid=5499&extra=page%3D1">http://bbs.mf8-china.com/viewthread.php?tid=5499&extra=page%3D1</A>这一帖中那个12步公式循环6930遍后复原，只历遍了6930×12＝83160个态，远远没有4千亿亿个！

[ 本帖最后由乌木于 2008-2-1 12:02 编辑 ]

作者: 乌木 时间: 2008-1-31 23:41:42 标题: 回复 18# 的帖子

我上面举的两个示例性的图，并没有给定第一代是什么样的具体状态，也就是并没有“为每个状态构造一棵树”。的确，无须这样，因为，有了态树后，任何一个态都有资格上去当老祖宗的，其余的态可以各自对号入座。所以，“关键是这颗树的构造算法”，诚哉斯言！

作者: pengw 时间: 2008-2-1 10:35:47

原帖由 山游008 于 2008-1-31 23:00 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=77426&ptid=5509" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 不太理解乌木先生的话,我是这样想的. 设魔方的所有状态数为N,起始态为态1,经过一定的路径{公式}得到态2,态2也经过这一个路径能得到态3,如此,态N再经过这个路径就能回到态1,在回到态1时已经把所有态走完.那么这样的路 ...

始于同一状态的最短路径树：
----------------------
1。从根出发不回逆，到达的任意分枝状态或叶状态的路径都是最短路径
2。距根最远的叶是根的最远状态
---------------------
 
三阶最短路径树培育方法：
-----------------------
0。从固定方位，以90度转为单位
1。第二层，有12状态
2。第三层，12*11个状态（除去一个回逆），每一个状态与下层（仅与下层）进行比较除去重复状态，余下的状态进行横向比较除去相同状态
。。。
 
3。直到根与分枝点及叶的合等于三阶状态数。
 
------------
 
楼主的命题在树上攀爬，显然是要回退的，没有一个公式可以避免故地重游，不仅是要重游，而且是大量的重游。面对一颗最短路径树，凡学过数据结构的人，都会明白如何用最短的路径遍历整颗树。
 
-----------
建议不要去走什么球面，网面，空间路径，这是人为地将事情复杂化。魔方的基本问题都很简单
 
 
 

[ 本帖最后由 pengw 于 2008-2-1 13:18 编辑 ]

作者: pengw 时间: 2008-2-1 10:54:23

探讨最小步数问题，请注意一个关键问题，每一个簇都有最短路径树，如何让尽可能多的簇尽可能同时沿最短路径走向根，才是最小步求解的关键问题。再次提醒那些个所谓的最小步循环大师注意，一个没有簇概念的最小步理论，如同没有牛律定律的物理学，极其极其可笑。

作者: 乌木 时间: 2008-2-1 12:30:35 标题: 回复 22# 的帖子

“0。从固定方位，以90度转为单位。1。第二层，有11状态，除去一个回逆状态。2。第三层，11*11个状态，……” 冬兄恐怕有笔误吧？头三层是不是如下图这样：
 
 头三层态树确切为…….GIF

[ 本帖最后由乌木于 2008-2-1 12:32 编辑 ]

附件: 头三层态树确切为…….GIF (2008-2-1 12:32:12, 8.2 KB) / 下载次数 89
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTIyNTN8MjBhODJkY2J8MTc2MTg4MTA5NnwwfDA%3D

作者: pengw 时间: 2008-2-1 13:13:36

有笔误，第二层应该是12，第三层L'正是要除去的那个回逆，所有的状态应该可以在树上占据一个位置（注：尚没有严格论证过），只有树这种结构比较好处理，其它，如球面，网面，空间路径可能很难找到有效的处理方法

[ 本帖最后由 pengw 于 2008-2-1 13:21 编辑 ]

作者: pengw 时间: 2008-2-2 09:21:32

从N阶的角度，无论是奇阶还是偶阶，同一阶所有状态都可以上树，所有状态的同态（偶阶）也上树，一点都不奇怪，这颗树就是短路径树。任意状态做根就足够了，解决所有最短径问题只须要一颗树，这个问题很好理解。至于那些个用什么二阶平面纸片魔方的什么球面模型，极其可笑。
 注意，从三层开始，层间，本层只跟相邻下层的下层进行状态比较,如果有相同状态,则去掉本层的状态。层内，进行横向状态比较，若有相同状态，只保留一个。
 我想这足以构造一颗最短路径树。我预言，GGGLGQ马上要声明，这是对他的什么相似变换理论的发扬光大，哈哈哈。

[ 本帖最后由 pengw 于 2008-2-2 16:54 编辑 ]

作者: 乌木 时间: 2008-2-2 23:29:14

画个图看看三阶魔方头三代态树情况（局部）或许直观些。设180°转算两步，即180°转所得的态属于“孙子”辈了（这无非是捣鼓方法之一罢了）。消同态之后，第三代只有123个态了。
 
 三阶部分态树.GIF

[ 本帖最后由乌木于 2008-2-2 23:48 编辑 ]

附件: 三阶部分态树.GIF (2008-2-2 23:29:14, 16.26 KB) / 下载次数 95
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTIyODh8NDgxYTEyNGN8MTc2MTg4MTA5NnwwfDA%3D

作者: pengw 时间: 2008-2-3 08:48:22

第三层幸存的状态必然是须要二步才能到达的状态,第N层幸存的状态必然是须要N-1步才能到达的状态.对于N层任意一个状态,执行一次90转动,结果要么后退一层,要么前进一层,二者必居其一,直到上树的状态总数等于三阶状态数.注意,三阶没有同态问题,生长中只存在相同状态问题,由剪枝来处理.生长原理很简单,但很费事,编程处理才是正确选择.生长方法适合于N阶,有没有时间看到结果就不好说了,至少对付二阶是很容易的事.还有更妙的规律正在分析中.
 
 ---------------- 
 
乌兄如果觉得生长中有什么不能克服的问题,请明示,经过严格分析,我认为不会有,问题只能是时间和空间.这种算法不会再有跳楼问题,最短路径树明显优于如同迷宫的球面/网面模型.
 
-----------------
 
在GGGLGQ的神经病治好以前,谢绝GGGLGQ参与理论区学术讨论

[ 本帖最后由 pengw 于 2008-2-3 08:56 编辑 ]

作者: pengw 时间: 2008-2-3 08:59:42

乌兄: 
 
你看能不能开一个专贴讨论:三阶状态最短路径生长树培育方法?
 
------
 
此方法去年这个时候就成形了,只是觉得实用价值不高,所以闲置在大脑中,当然也是不想诱发某些大师的癫痫发着.

[ 本帖最后由 pengw 于 2008-2-3 09:03 编辑 ]

作者: 乌木 时间: 2008-2-3 12:27:19

其实，不懂有关理论的我对这种专门学问是深入不下去的，只能一般想想而已。哪位想专门探讨的话，是得另开一帖的。
－－－－－－－－－
前面提到的回到上一代的消同态时，和消态一起，有关路径自然也没了，就相当于“剪枝”。我想想，同一代之间的消同态就不同了，有两种办法：若只统计态总数时，剪枝不剪枝无所谓，剪了的话，态树简洁一点。如果不仅为了统计总数，还要利用它做别的事情，尤其是与路径有关的工作，比如寻找某两个态之间的最短路径等等，就不能“剪枝”了，要的就是完整的态态路径关系，所以，合并同态时保留路径是至关重要的吧？
示意如下图：
 
 三阶部分态树－2.GIF

[ 本帖最后由乌木于 2008-2-3 12:33 编辑 ]

附件: 三阶部分态树－2.GIF (2008-2-3 12:33:47, 18.78 KB) / 下载次数 92
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTIzMzl8YjM4NzJkOWF8MTc2MTg4MTA5NnwwfDA%3D

作者: pengw 时间: 2008-2-3 16:14:04

构造最短路径树的目的就是求得一个状态到达其它状态的最短路径,凡路径等长的状态一定位于同一层,我觉得同层剪枝应该没有什么影响,反而可以使得树要稀疏很多,并且没有重复状态. 
 
当然也看个人喜好,我更喜欢简洁无冗的树. 树生长到第三层,手工操作可能就有点难受了,层再升高恐怕就不是手工可以应对了,哈哈哈.
 
只要足够细心和耐心,这就是久久渴求的最短路径树. 树一长成,所谓最小步和最远状态也仅仅只是查表的问题.
 
------------ 
 
养树的方法真的很简单,养不养得起那就不一定了,不妨编程试试二阶.我真是不明白那些个云中半仙弄了几年都没有明白这么一个如此浅显的道理,极其可笑.

[ 本帖最后由 pengw 于 2008-2-3 16:16 编辑 ]

作者: pengw 时间: 2008-2-3 16:26:12

搞最短路径分析,千万不要钻进什么球面/网面,这叫自投罗网,显然,树的简洁性是不容置疑的,有些什么仙为了遮掩自身的无知,常常将一个极其简单的问题弄得复杂无比,似乎只有GGGLGQ这种比肩爱因斯坦的高人才可能触及,实在是太有意思了.弄了半天最小步理论,结果变成相似变换,为什么这些个教导别人的大师总是在犯入门级错误,现在的老师真是不敢恭维.

作者: 乌木 时间: 2008-2-3 19:39:32 标题: 回复 30# 的帖子

继续胡思乱想下去。下面有两种态树，统计魔方状态的总数时，两者一样。但从左边不简洁的态树，可以看出态a和态b之间距离为一步；右边的态树，简洁是简洁了，可态a和态b之间的捷径被“剪枝”剪掉了，它们之间不得不走上三步。这就是我对“剪枝”的担心所在。（当然这里设定态态之间要按照态树中的路线走，否则，U'U'U'＝U就是了。当复杂一点的路线的场合，还这样抛开路线而计算的话，那是另一种分析法了。）
 
 三阶部分态树－3.GIF

[ 本帖最后由乌木于 2008-2-3 20:14 编辑 ]

附件: 三阶部分态树－3.GIF (2008-2-3 19:40:23, 16.41 KB) / 下载次数 97
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTIzNDh8M2Q5MWMzYzl8MTc2MTg4MTA5NnwwfDA%3D

作者: 立 时间: 2008-2-3 23:35:59

好深奥..........那个RUR'U'算不算的?

作者: pengw 时间: 2008-2-4 08:54:40

回30楼: 
 
最短路径树只考虑从根出发到任意结点的最短路径,因而不进行根以外的任意二个结点的路径比较,而任意结点可以做根,所以乌兄的担心是不必要的.以往为什么会出现球面/网面?就是因为进行这种不必要的根以外的任意二结点路径比较,实质上又是无意中掉进了着色陷井中.
 
如果有人问,如何求得任意二个状态的最短路径?这个问题实在很机智和技巧,凭那颗树和一些着色技巧立马可以解决.此问题留给大家解迷.

[ 本帖最后由 pengw 于 2008-2-4 09:05 编辑 ]

作者: pengw 时间: 2008-2-4 09:01:23

回34楼:
 
 其实很简单,计算机专业数据结构中的树结构而已,魔方的本质问题都很简单,只是天文单位的状态数让人被吓住了.理解魔方,如同学习组合原理,只要记住用于组合的基本原素和组合规则,任意一个组合都逃不脱你的预言.

作者: 乌木 时间: 2008-2-4 10:48:39 标题: 回复 35# 的帖子

您说：“最短路径树只考虑从根出发到任意结点的最短路径,因而不进行根以外的任意二个结点的路径比较,”
 
这是有关理论的规定吗？如果是的，那么，我的“担心”似乎没必要了。
 
因为，上面我那例子中为了求态a到态b的距离，在剪枝后的简洁的态树中，不能直接在态树上“爬”（否则如上面所述的会绕远路），应该让态a作为第一代（即态树的根），其余的态让它们自动对号入座（当然是一种想像），那么，态b必定乖乖地落到态树的第二代位置之一，态a与态b的距离当然就是一步了。
 
如果我说对了，态树（及其使用法）还是简洁式的好。对吗？

[ 本帖最后由乌木于 2008-2-4 10:51 编辑 ]

作者: 乌木 时间: 2008-2-4 10:56:10

原帖由 立 于 2008-2-3 23:35 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=79109&ptid=5509" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 好深奥..........那个RUR'U'算不算的?

我只是画了态树的局部，第二代的其余“枝”类推，上面我说过这一代“同辈”中共消去9个同态。

作者: pengw 时间: 2008-2-4 11:02:24

回36楼: 
 
不是理论规定的,而是我设计的最短路径树规定的,在这样一颗树上,只能一直上树,而不能后退.横向计算不能确保是最短路径,例如:
 
 一个最远状态(假设是22步),从第一枝得到一个,另一个从第二分枝得到,如果走树的路径,二个最远状态的距离是44步,显然非常荒谬.
 
 算法本身只能确保一直向上的路径到达的结点与根之间的路径最短.之所以这样设计算法,就是为了避开球与网这种从数据结构上讲极难处理的类型(为什么现代数据库称为关系数据库,就因为这个原因)同时对最短路径处理没有任何影响.横向计算只是一个从根出发且不后退又略有一点技巧计算方法,一定会想明白的,哈哈哈.
 
为什么会选择树结构?因为树结构没有回路即没有网格,魔方的复杂性要求我的思路尽量从简而不是一头扎进原有的复杂性中.

[ 本帖最后由 pengw 于 2008-2-4 11:37 编辑 ]

作者: pengw 时间: 2008-2-4 11:41:28

如果GGGLGQ在得来全不费功夫的最短路径树还有前面的状态定律的帮助下还无所作为,真是说不过去了,哈哈哈.

作者: 乌木 时间: 2008-2-4 13:48:53 标题: 回复 39# 的帖子

原来如此。
 
其实，纯粹“爬树”法找路径一般是不现实的，真正要找任意两个态之间的最短路径，还得靠计算。把其中一个态作为根，据“简洁式”态树以及相应的运算规则，应该可以计算出来。至于态树过大造成的问题，是另外一个问题。
 
如果要看看“剪枝”前的另一条路径，是否可以这样：被剪的路径存在“仓库”中备用，需要时取出，就是另一条等价的路线了。也就是，需要时，态树可以隐去一部分而显示等价的另一部分。
 
哈，有点“无事忙”。

[ 本帖最后由乌木于 2008-2-4 16:07 编辑 ]

作者: pengw 时间: 2008-2-4 15:33:27

错，无须计算，只须从选定的终态一路下树下到根即可。至于任意二个状态，如何弄成根与枝或叶的关系，容我保留一下，其实非常简单，细想一定会明白。

作者: 乌木 时间: 2008-2-4 17:05:49 标题: 回复 42# 的帖子

嗯。这么说来，我索性展开地想想，众多快手、高手和更多的初学者，利用各种复原方法，各显神通，广义上无不属于计算法，实在是一种“曲线救国”运动。因为，一不知所面对的混乱态属于态树的什么位置；二不知下树的路径，乃不得已而为之啊。对此，理论工作者目前还无法给出下树捷径等等。这样来议论魔方运动的现状对吗？

[ 本帖最后由乌木于 2008-2-4 17:39 编辑 ]

作者: pengw 时间: 2008-2-4 17:33:41

乌兄啊你又在幽默俺，对于已经构造好的最短路径树，从树上任意一点下树（一路下，不上升），只有唯一条路径而且是最短路径，不是吗？哈哈哈哈

[ 本帖最后由 pengw 于 2008-2-4 23:21 编辑 ]

作者: 乌木 时间: 2008-2-4 17:44:17 标题: 回复 44# 的帖子

不是幽默谁。我的意思是总有这么一天的吧，最短路径问题可谓任重道远。对吧？

[ 本帖最后由乌木于 2008-2-4 17:55 编辑 ]

作者: pengw 时间: 2008-2-4 23:03:16

对最短路径树，总体上讲： 
1。是一颗包含所有状态的最短路径树 
2。适合于任意二个状态最短路径求解 
3。所谓最短路径和所谓最远状态求解，只是一个查表问题，最高的叶就是最远状态
4。只要构造一颗树即可满足所有要求
5。根一直向上，到达任意一个结点的路径都是最短路径 
6。这颗树即是经过最严格的剪枝也过于巨大 
7。这种方法仍然是最傻的最短路径和最远状态求解 
8。相对而言，这种方法远远优于球面或网面模型 
------------------
这颗树存在的意义就是描述最短路径问题（即一个状态与其它所有状态的最短距离关系），并不包括也没有必要包括所有路径，只有最短路径。算法至少给出了一个实用的究研最短路径的状态组织方式，尚没有对这颗树的规模问题完全失望，还有新的思路在分析论证中。
 
 

[ 本帖最后由 pengw 于 2008-2-4 23:20 编辑 ]

作者: lvanqi 时间: 2008-2-5 18:27:26

我是想问问怎么玩魔方？？？？？？？？？？？？？？？？？？<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/victory.gif" border=0 smilieid="14">

作者: pengw 时间: 2008-2-5 19:15:00

你的问题可大可小，要看你是以什么方式来玩

作者: 乌木 时间: 2008-2-5 21:51:08 标题: 回复 47# 的帖子

多数人是玩如何把一个打乱了的魔方拧回六面分别同色的复原态。为此，你可先看看复原篇的菜鸟入门。

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