魔方吧·中文魔方俱乐部

标题: 关于魔方的状态表示方式？ [打印本页]

作者: 铯_猪哥恐鸣 时间: 2010-3-20 10:12:00 标题: 关于魔方的状态表示方式？

首先声明我发之前那个帖子的原因之一就是：我在研究计算机解魔方的时候发展了魔方的另外一种表示形式，但在那种“理论”下所有关于魔方的性质都变得和现在认为的理论有出入。看来也确实很难让人接受一个和现有理论矛盾的想法，所以这里只是希望和大家一起探讨下。
现在状态表示一个很大的分歧就是：整体转动魔方算不算不同的状态？我本身也认为应该不算，但也就引出了另外一个问题，48同态算不算同一个状态？
对于三阶魔方，当前的理论认为根据中心块相对位置的不变，其余块围绕这中心块变换，并且认为48同态是不同的状态，这一系列观点在一开始我写程序的时候确实提供了很大的帮助，但是在最近希望快速处理对称态的时候发生了很大的问题。

所以我发这个只是希望吧里有人可以对魔方状态表示进行更深入的探讨，如果能在状态表示方面就省略掉部分对称态，那从各方面将都将是一个突破。即使最终表示后的状态数与4.3*10^19有很大出入也并不奇怪（对某人认为算对魔方状态数才算理论的观点表示观望），不仅限于置顶理论的表示方式，希望可以找到一个表示方式，在转动，对称处理上有着同样的效率，尽管这并不是很容易做到。
对魔方状态表达有自己见解的欢迎发表自己的想法。

作者: 夜雨听风 时间: 2010-3-20 10:26:30

同LZ，个人认为整体翻转不算一种状态，LZ的意思是希望我们给出三阶状态计算步骤(方法)？

作者: smok 时间: 2010-3-20 10:26:49

以二阶为例,说说你的48同态是如何定义

作者: 铯_猪哥恐鸣 时间: 2010-3-20 10:33:14

回楼上，这点可以看ggglgq的关于同态的帖子，我的意思是，就比如二阶魔方，如果认为同态是同一个状态的话那总状态数只有7万多，比3674160小了两个数量级。从搜索的角度上绝对是质的飞跃

作者: smok 时间: 2010-3-20 10:37:55

哦,你的意思是指同构不同块,简称同构异块,以全色三阶为例,唯一中心块转了180,中心块有6种选择,即这种状态有六种,复原状态根本找不到同构异块,怎么看也跟48不达界,更不要说什么对称,是不是镜子中的魔方也算一个状态?

你还是须要将48的来路说清楚

[ 本帖最后由 smok 于 2010-3-20 10:42 编辑 ]

作者: likaio0 时间: 2010-3-20 10:39:15

高端计算机解魔方~厉害！等高手解释吧·

作者: 铯_猪哥恐鸣 时间: 2010-3-20 10:44:16

同态用CE作者的意思就是：转了RUR'和FUF'后的状态本质上是同一个，只是因为初始方向不同罢了

作者: smok 时间: 2010-3-20 10:48:50

举个JAVA例子,或请乌木帮你做一个例子

作者: smok 时间: 2010-3-20 10:51:44

如果仅以视始方向不同来看,一个魔方最多有24个初始方向,因此一个状态最多有24个同构异块图案,根本与48不达界,你还是没有说清楚,你能不能用一个最简单的状态来说明它的48同态?

[ 本帖最后由 smok 于 2010-3-20 10:53 编辑 ]

作者: 铯_猪哥恐鸣 时间: 2010-3-20 10:54:06

24个方向，再加上左右镜像对称的情况以及相应的24种同态。。。当然有的状态由于本身的对称性没那么多同态罢了

作者: smok 时间: 2010-3-20 10:58:18

你认为一个状态在镜子中的状态也算一个同态?你的镜子放在哪个位置?有事离开几个小时,总之,你的48同态如果在魔方上找不到一一对应关系,我建议你还是去学习魔方理论,如果你不屑于当前魔方理论,你至少先花时间独立总结一套与当前理论等价的理论后才去编程

[ 本帖最后由 smok 于 2010-3-20 11:16 编辑 ]

作者: happyyu 时间: 2010-3-20 11:17:02

太深奥！我觉得转整体魔方不如换手法

作者: 铯_猪哥恐鸣 时间: 2010-3-20 11:18:59

好吧，毕竟您是搞理论的，“镜像状态”和速拧中意义都不同，比如RUR'的镜像为：L'U'L

作者: 小波 时间: 2010-3-20 11:34:46

囧= =要不就矩阵表示吧，适用于任意阶

作者: smok 时间: 2010-3-20 11:43:12

请楼主正面回答我的问题:魔方当前状态与其在镜子中的状态是不是互为同态?

作者: 夜雨听风 时间: 2010-3-20 11:49:10

六色三阶就24态，如果算镜像，那样的话配色不是要换

作者: smok 时间: 2010-3-20 11:49:49

原帖由 铯_猪哥恐鸣 于 2010-3-20 11:18 发表
好吧，毕竟您是搞理论的，“镜像状态”和速拧中意义都不同，比如RUR'的镜像为：L'U'L

你这个说法,只是等价于将魔方绕Z轴转动180度再执行公式RUR',你仍然必须回答你的48是何含意?据现实分析可知，一个状态最多24个异块同构状态，你的48从何而来？

作者: 铯_猪哥恐鸣 时间: 2010-3-20 11:51:07

恩，我考虑过矩阵，但是矩阵的运算太慢了。。。

作者: smok 时间: 2010-3-20 11:53:27

即便将三阶所有状态分为24个一组的异块同构状态（事实上绝大多数状态根本没有24个同构状态），也即意味着将三阶总状态除以24，这能帮助你减少多少工作量？四阶五阶N阶又如何？你以为这是在凭空想象吗？

[ 本帖最后由 smok 于 2010-3-20 11:55 编辑 ]

作者: smok 时间: 2010-3-20 11:58:02

如果连基本的魔方问题都没有弄清楚，还奢谈什么计算手段？你说你在研究数学则罢了，但是，你在研究魔方，你能回避魔方自身固有的变换规则吗？不要本末倒置，不管你喜欢与否，当前已有的魔方理论会步步约束你的行为，不信的话，你可以试试。我倒是真的希望看到你弄出一个与现有理论完全对立的魔方理论，这将是理论区的一大盛事。

[ 本帖最后由 smok 于 2010-3-20 12:03 编辑 ]

作者: 铯_猪哥恐鸣 时间: 2010-3-20 12:00:14

回17楼，真的等价吗？

作者: 铯_猪哥恐鸣 时间: 2010-3-20 12:06:23

我的目标是搜索单个状态的最短步，对于这个问题，48倍的优化还是很必要的，至于你说的高阶，不论程序什么想法，至少理论没有给出任何一个可行的最优解算法

作者: superflip 时间: 2010-3-20 12:11:06

旋转群如smok所说24个元素，乘以镜像2元素，共有48元素。

所以相当于镜子可以放在24个地方~

说他们同态是因为它们很多性质相同，最主要用到的就是它们拥有同样的置换结构，需要相同的最小步数还原。

逆向态也有这性质，所以有96元素。

请您再想一想对于每个态，还有什么方式可以得到“需要相同的最小步数还原”这一性质的态，这么分类的目的是利于搜索~

当让对于高阶确实意义不大，不知你有何建设性意见对于求解高阶最小步。

不要老说别人怎么样，你真的以为别人对魔方只会“脚”拧，版主的魔方理论还是很不错的，思路很清晰，可是这个区的讨论氛围实在是，动不动就~

作者: smok 时间: 2010-3-20 15:23:48

哈哈哈...哈哈哈...我就知道你会这样回答，你不妨用二个一模一样的全色三阶，1号魔方转出任意状态做正像，再在2号魔方上转出1号的镜像，我想你一定能完成这个工作，哈哈哈，请把你完成的工作用java表示出来。

[ 本帖最后由 smok 于 2010-3-20 15:26 编辑 ]

作者: smok 时间: 2010-3-20 15:27:46

原帖由 铯_猪哥恐鸣 于 2010-3-20 12:00 发表
回17楼，真的等价吗？

你认为不等价吗？

作者: smok 时间: 2010-3-20 15:32:01

你连48同态的定义都没有拿捏清楚，还讨论什么问题。这样，为了更进一步简化问题，你找一个最简单的状态，同时列出它的48同状如何？实在弄不出来，给出24同态也行，哈哈哈

作者: smok 时间: 2010-3-20 15:35:14

要你正面回答问题，你又躲躲闪闪，爱口失羞，真不明白你是什么意思，你到底想说明什么嘛，列举一个48同态全家福对你来说有困难吗？

作者: superflip 时间: 2010-3-20 16:16:59

smok：我在23#讲了96态的来历，你不会不明白的，不要再无聊发帖灌水了。

版主也出来说句话吧，需要的是实在的讨论：如何描述一个3阶魔方的状态有利于寻找最小步算法~

作者: smok 时间: 2010-3-20 16:28:43

superflip:你真以为你可以做得出镜子中的状态？别搞笑了，这已经是N年前讨论过的低级问题了。以三阶换心图为例，你能找出48个不同的换心图？再这样争睛说瞎话就没有意思了，除非你的确不太了解魔方

smok请注意说话的语气！不过，我也有兴趣知道superflip是如何转出镜子中的状态，superflip不妨正面解答这个问题

[ 本帖最后由 pengw 于 2010-3-20 16:39 编辑 ]

作者: superflip 时间: 2010-3-20 17:08:34

和换心图没关系，那个是以外部块为框架，只有12种换心。

我是看的CE的help，他是这么说的：
In general, two cube permutations A and B are equivalent, if there is a symmetry S of the cube with
B = S-1*A*S

In Cube Explorer, these 48 symmetries are generated by four "basic" symmetries:
S_URF3, a 120 degree turn of the cube around an axis through the UDF-corner and DBL-corner,
S_F2, a 180 degree turn of the cube around an axis through the F-center and B-center,
S_U4, a 90 degree turn of the cube around an axis through the U-center and the D-center
S_LR2, a reflection at RL-slice plane.

最后一个S_LR2就是镜像，就是把你的打乱公式中的U, U', D, D', F, F', B, B', R, R', L, L' 分别改为镜像动作U‘, U, D’, D, F‘, F, B’, B, L‘, L ,R', R, 得到的状态就越是他的镜像状态，比如lz举例的 RUR' 与 L'U'L 互为镜像状态。可以很明显的知道镜像状态“需要同样的最小步数还原”。同理 RUR' 的逆态 RU'R' 也有这性质。所以我说有96态。这对于计算机减小搜索状态空间有好处。

版主的理论更多的是研究魔方转动能产生哪些态，多少态，也就是将魔方散架后瞎装上去是否能复原。而计算机搜索就是按普通人一样“一转”，“一转”的每步执行层的旋转，不会产生还原不了的态的。

[ 本帖最后由 superflip 于 2010-3-20 17:24 编辑 ]

作者: pengw 时间: 2010-3-20 17:49:33

原来你的48同态来自二阶段搜索算法,那么,我提一个问题,你如何从状态空间(N阶定律制约)中分辩出那些是48同态状态?

如果你将N阶定律简单地理解成只是计算状态数和指导如何组装魔方,那未免太过偏执,事实上N阶定律还能告诉你更多,哪些变换可行,哪些不可行,公循环周期如何计算,复原算法如何构造,不同状态之间转换公式步数的奇偶性等等.公式不可能告诉你状态空间大小,对吧,如果你不知道状态空间大小,你又如何评估你的搜索难度?

二阶段搜索算法只是一个基于经验的较短路径算法,而非最短路径算法,

[ 本帖最后由 pengw 于 2010-3-20 17:51 编辑 ]

作者: pengw 时间: 2010-3-20 17:55:54

从公式到状态,这很好办,但从状态到公式就难办了,事实上你面临的就是这个问题.正如前面smok所言,就算将三阶状态T分成96 个/组,即你的搜索空间大小是F=T/96,你还要为这F个组中的每一个确定的最小步公式模板，我认为这几乎等于是没有效果.

[ 本帖最后由 pengw 于 2010-3-20 17:59 编辑 ]

作者: superflip 时间: 2010-3-20 18:28:55

哈哈，终于回到正常的讨论了，CE既能2阶段搜索，也能求最小步，点一下optimal即可~

你上楼的担忧恰恰就是为什么现在CE能算最小步，就是能从一个已知的状态知道他的48个同态，而不需要记住已知的那个状态是用什么公式打乱得来的~

很简单，不是吗？（但是楼主认为CE这块的处理还是不够高效，所以才来问你们是否理论上有更好的状态表示方法有利于求解3阶最小步！你们是否也应该去看看ce的算法呢~ 和楼主讨论就更充分了）

ps：我前面只是举例你的理论主要能干什么，不可能面面俱到，但是你也曾说过，会计算N阶的状态数不就相当于理解核心理念了吗？

[ 本帖最后由 superflip 于 2010-3-20 18:34 编辑 ]

作者: pengw 时间: 2010-3-20 18:41:16

问题是你真的认为你理解了N阶状态数计算的全部意义了？

据我所知，二阶段法的思想是，有一个环形岛链，外围的鱼船总能得到一个靠得最近的小岛，这些小岛之间比此又有较短的路径，因此二个鱼船的较近距离通过借岛链来间接取得。

问题是，如果二个鱼船比此靠得很近，还须要借助岛链吗？

澄清一点，二阶段算法并不是最短路径算法，只不过通过将状态分为外围与岛链二组，间接缩小搜索空间之权宜之计

[ 本帖最后由 pengw 于 2010-3-20 18:43 编辑 ]

作者: pengw 时间: 2010-3-20 18:46:04

N定律可以立即断定任意二个状态之间的最短路径是奇数步还是偶数步，奇怪吗？

作者: superflip 时间: 2010-3-20 18:47:41 标题: 回复 34# 的帖子

CE既能2阶段搜索，也能求最小步，点一下optimal即可~

晕倒~ 版主用过CE吗？箭头旁边有个optimal的单选框，可以求解真正的最小步，不是2阶段，但是楼主觉得他的算法还有很大改进余地，所以才来理论区问你们的。

作者: superflip 时间: 2010-3-20 18:49:06

回35#：这有啥奇怪的，你的一步是以90度为一步的吧~

作者: pengw 时间: 2010-3-20 18:51:18

如何证明你的结果是最小步？

作者: 目方 时间: 2010-3-20 18:53:54

提示: 作者被禁止或删除内容自动屏蔽

作者: superflip 时间: 2010-3-20 18:54:30

额的神啊，我是来普及CE软件的~

他就是剪枝穷举~你说会不是吗？所以少48倍空间才使得计算有效多了~

[ 本帖最后由 superflip 于 2010-3-20 18:55 编辑 ]

作者: superflip 时间: 2010-3-20 18:57:19

版主有不是穷举的方法吗？你的最小步导论实在从字面上看是行不通的，也许你有言外之意我们没有读懂~

作者: pengw 时间: 2010-3-20 19:10:46

原来用的俺提出来的剪枝穷举，不过你的剪枝空间是不是太大了一点？如何让人信服你的算法没错？至少你应该将你的剪枝算法详细描述一遍

作者: superflip 时间: 2010-3-20 19:33:52

又出每小时发帖限制，无语~

呵呵，变成你提出的剪枝穷举了，你的导论里剪枝至少字面意思看是不对的~

他用空间换时间，存表查表了，而且实际算的确实比较慢，小时量级，所以才要改进，你说呢？

你要是信不过去看他的HELP里的算法描述或源码吧，也许确实有小bug，但基本不会错的，不光CE，还有很多人验证过了，目前正在计算证明最小步为20步的那人就是其中一个~

希望版主也深入了解一下CE算法，这样也能更好的讨论出从理论层面或算法层面的一个提升~

作者: pengw 时间: 2010-3-20 19:40:18

剪枝穷举算法后来有过多次讨论,并不局限于导论内容.要让大家信服,你还得将你的剪枝穷举算法详细地描述清楚,我不喜欢看代码,看算法我就明白了

作者: pengw 时间: 2010-3-20 19:44:36

只要有足够的存贮空间,够快的CPU,不难将所有状态保存在数据库中，再用最小步连接这些状态，余下的问题只是查表，其实穷举法是很蠢的一种方法，基本上没有理论层面的价值，只要肯花力气，都能做出来。

[ 本帖最后由 pengw 于 2010-3-20 19:47 编辑 ]

作者: superflip 时间: 2010-3-20 19:49:21 标题: 回复 44# 的帖子

你连help也舍不得看一下~

基本意思就是假如角色相需要5步还原，那整体还原至少需要五步。最简单的剪枝，没有任何理论，所以效率不高，所需空间也大，所以需要48同态。

如果你要我一步一步讲解他状态怎么表述，为什么存的下，我就放弃了，你花少许时间看下help吧，不是程序代码，只是精简的描述与解释~

作者: superflip 时间: 2010-3-20 19:51:00

原帖由 pengw 于 2010-3-20 19:44 发表
只要有足够的存贮空间,够快的CPU,不难将所有状态保存在数据库中，再用最小步连接这些状态，余下的问题只是查表，其实穷举法是很蠢的一种方法，基本上没有理论层面的价值，只要肯花力气，都能做出来。

不得不说版主你说出这话我。。。。

绝对的真理就如同这些话，有建设性的提高吗~

你有理论能让程序少“蠢”一些吗？这正是为什么讨论的关键啊！

[ 本帖最后由 superflip 于 2010-3-20 19:56 编辑 ]

作者: 乌木 时间: 2010-3-20 20:13:00

[java3=200,200]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt] [/param]
  [param=initScrpt]U [/param]
[/java3] [java3=200,200]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt] [/param]
  [param=initScrpt]U' [/param]
[/java3]

两者不是互相对称的状态，是同一魔方的两个不同的魔方状态；但是，分别从复原态出发，一个做了U，另一个做了对称动作U'，两者的变化过程是对称的，以致在有关处理中，两个状态可以“一视同仁”－－这并不妨碍两个态依然是非对称态。
变化好之后的静态之比较是一回事，变化的过程之比较是另一回事，两者不必混为一谈，更不必相互打架。
我这样认识妥否？

[ 本帖最后由乌木于 2010-3-20 20:32 编辑 ]

作者: superflip 时间: 2010-3-20 20:21:44 标题: 回复 48# 的帖子

呵呵，乌木前辈一直比较开明，版主已经理解了ce对同态的定义了，剩下的是：能否找到理论指导如何改进ce算法。

作者: pengw 时间: 2010-3-20 21:24:53

遗憾的是，同一公式作用于所有方位加上公式内部左右转层对称置换、其它转层顺逆置换再作用于所有转层，恐怕很难找齐真正的48同态。

比方说，有一个公式让全色三阶唯一一个中心块转了180度，你就是穷尽所有力气，也只能得到6种状态

作者: pengw 时间: 2010-3-20 21:30:02

与其说是状态同态，不如说是公式转层镜像，如是公式转层镜像，何止48种镜像！上下，左右，前后都可以镜像，每一个镜像公式又对应24个作用方位，为什么单单只选左右公式镜像？道理何在？

建议楼主就不要提什么48同态，用公式镜像更为准确，以免别人误以为是魔方状态

[ 本帖最后由 pengw 于 2010-3-20 21:32 编辑 ]

作者: pengw 时间: 2010-3-20 21:35:17

如果楼主愿意，请将CE help贴到理论区

作者: pengw 时间: 2010-3-20 21:59:32

如果继续沿用穷举，我到是有更好的算法，一棵自然生长树，位于同一层的状态与根的最短路径长度相同，最高层的叶就是根的最远状态。

当然你会问，这只能说明根到各结点的最短路径，那么任意二个状态又如何去算，目前我只想告诉你，这颗树在计算最短路径/最远状态方面是万能的。

一次性完成树构造，终身受益，余下的事，只是查表而已，对任意阶都适用，只不过，对于四阶以上，你可能买不起那么大阵列柜

作者: 铯_猪哥恐鸣 时间: 2010-3-20 22:02:10

回楼上，你先试试用用看CE吧

作者: 铯_猪哥恐鸣 时间: 2010-3-20 22:04:09

恩，其实三阶的死枚举就已经没有可行性意义了，而你提到的树，正是搜索的基本模型

作者: 铯_猪哥恐鸣 时间: 2010-3-20 22:05:33

另外，至少在现在的理论研究范围内，我没看到任何关于用非搜索方式求魔方最少步的算法或程序

作者: 铯_猪哥恐鸣 时间: 2010-3-20 22:07:27

说搜索笨也好，没有理论研究价值也好，但至少通过它我们或许可以解决求三阶魔方最少步这一问题，就好比四色定理的证明，完全是计算机枚举，一点数学味道都没有，但它仍然是有意义的

作者: superflip 时间: 2010-3-20 22:07:46

回版主：不要轻易说你有更好的想法，都没看过别人的~ 我都不知道怎么回了~

作者: 铯_猪哥恐鸣 时间: 2010-3-20 22:09:50

另外我还是提醒一句，搜索有的时候并没有你想的那么简单，同样是有限的时间可以解出答案，十年和十秒完全是两回事

作者: superflip 时间: 2010-3-20 22:18:24

原帖由 pengw 于 2010-3-20 21:30 发表
与其说是状态同态，不如说是公式转层镜像，如是公式转层镜像，何止48种镜像！上下，左右，前后都可以镜像，每一个镜像公式又对应24个作用方位，为什么单单只选左右公式镜像？道理何在？

建议楼主就不要提什么48同 ...

看到这"何止48种镜像" , “为什么单单只选左右公式镜像”，我无话可说~ （48=24 x 2）

我以为版主前面已经明白CE同态的定义了，以及这么定义有什么好处~

[ 本帖最后由 superflip 于 2010-3-20 22:20 编辑 ]

作者: pengw 时间: 2010-3-20 22:18:44

看“你们”弄得这么神秘，不过我倒是一点也感觉不到，20年前解三阶的软件也不过只写了二天，幸好我也算得上是一位IT人士。

虽然你们一唱一合说得那么甜美可口，说白了，也只不过是在玩公式的左右镜向而已，不过我要再次缠正你们，公式镜像并不总是等价于状态镜像，二者不要混不一谈。

作者: aubell 时间: 2010-3-20 22:19:25

状态无论怎么表示都可以，重要的不一定只有效率。

用户体验最重要。
用户需要的是相对效率，而不是绝对的效率。
即使一个程序运行的很慢，但运行过程中给出许多有趣的图像、音乐等，用户也就不会觉得它慢了。

CubeExplorer已经很优秀了，很难超越。

作者: pengw 时间: 2010-3-20 22:20:51

如果你们不将算法说清楚，至少我不会相信什么CE的结果，哈哈哈

作者: superflip 时间: 2010-3-20 22:23:45 标题: 回复 63# 的帖子

哈哈，说实话，楼主只是在写作业，我只是最近在拿楼主的2阶论文学编程~

其实算出最小步是没什么意义的，即使明天证明最小步为20步了，我也觉得~

作者: pengw 时间: 2010-3-20 22:24:29

重来没有听说过的什么CE能比CubeExplorer更强？CubeExplorer至少还附有算法，还没有强调是什么最小步工具，今天冒出一个什么连算法都没有的CE，号称是什么最小步工具，凭什么让人相信？

作者: superflip 时间: 2010-3-20 22:26:30 标题: 回复 65# 的帖子

我倒！CE能比CubeExplorer更强，今天开眼了~

作者: pengw 时间: 2010-3-20 22:29:43

怪不得让你澄清算法比要你的命还难受，原来是在无理取闹，哗众取宠，你急什么嘛，又没人跟你争输赢

作者: superflip 时间: 2010-3-20 22:30:54 标题: 回复 67# 的帖子

CE就是CubeExplorer

作者: pengw 时间: 2010-3-20 22:36:59

我还以为是你发明的什么东西，哈哈哈。

作者: 宇枫幽蓝 时间: 2010-3-20 22:40:06

高理论境界结合IT运算，看了六十多楼，实在一句话也插不上嘴，路过留名！希望讨论后能得出个总结，让我们这些外行的能看明白！谢谢各位！

作者: pengw 时间: 2010-3-20 22:41:43

如果你有什么创新，请先贴出你的原理吧或算法，否则没人会去在意

作者: pengw 时间: 2010-3-20 22:44:58

回70楼：
完全是拿着似是而非的东西在这里瞎忽悠，连贴子的名称都是文不对题，算了，还是让smok来陪你们玩吧

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