关于24同构

pengw

定义：同一公式，在已复原魔方的24个方位上各执行一次，得到24个状态，将这些状态中互不相同的状态的集合称为同构。依据这个定义，有人愿意偿试找出一组24同构状态否？曾要求过高人举证，但没有任何结果。以前曾有24同态一说，本质上是指这样一些状态，即魔方相对坐标系做整体转动得到的状态的集合，请注意区分这个概念。

[ 本帖最后由 pengw 于 2011-5-2 09:19 编辑 ]

42752277

很多JAVA


.

小明的马甲

是的，这是公式无关的，变换方法前面已经给出，48个s是已知的，具体它们的描述得看国外那个网站关于变换的详细表述方式，我也不便直接贴过来。另外，在ce的实际实现上因为某些原因只使用了16种对称

[ 本帖最后由 小明的马甲 于 2011-5-4 16:36 编辑 ]

pengw

定义:任意公式及其逆公式在复原魔方24个方位分别执行一次,得48个状态,将48个状态中互不相同的状态的集合称为同构对称集.
-----------------------
显然同构对称集最大是48,最小是1.任意同构对称集都有二个固有特性

1.即根据其中任意一个状态,即可公式无关地导出同构对称集中的其它状态
2.同构对称集中每一个状态相对同一始态都有等长的最短公式,且这些公式都是二二互逆

基于以上二点,同构对称集在状态搜索中的意义是显而易见的.
----------------------

1.有公式F及f',如果F不改魔方状态,则可以有条件(F=F1+F2,F2+F1=F2+F1+F2+F2'=F2+F+F2',某高人就是利用这一点,声称发现了循环变换理论,明眼人一看就知是相似变换)地做到F与fFf'等长,否则将很难等长
2.fFf'对应的状态可能远不止96,有可能要多很多,为什么偏用96同态这个说法?
3.谁能证明:F是最短公式,fFf'一定就是最短公式?

---------------------

基于F与F‘的同构对称集大小的上限一定是48,决不会高于此,而基于F与fFf'的状态数上限一定远远大于96

同构对称集一定是fFf'与fF‘f'构造的状态的子集，且，这个子集是自足，即根据一个状态，即可公式无关地推得子集中的其它状态

[ 本帖最后由 pengw 于 2011-5-4 17:08 编辑 ]

pengw

Si-1与Si是二个互逆的公式?

铯_猪哥恐鸣

等长显然，都是4步，是否最短这个因为只有4步，所以很容易验证，事实上由于原公式可以通过某个S_i变换过去，那变换后的公式当然也能同样的变换回来，所以只要原公式是最短，则变换后的公式一定最短且和原公式一样长。
好的，对于给定的长度为n的公式A = A1A2A3...An，生成的第i个公式B_i = S_i^-1 A S_i = S_i^-1 A1 S_i    S_i^-1 A2 S_i   ...   S_i^-1 An S_i
由于A1, A2, ..., An都是基本旋转（RUFBLD等），所以S_i^-1 Ak S_i事先算好即可，不需要给出A再另外计算。
大师辛苦~

[ 本帖最后由 铯_猪哥恐鸣 于 2011-5-4 00:00 编辑 ]

pengw

时间不早，明天还要成都飞昆明，建议明天继续讨论

pengw

回20楼：
你确认这所给出的这组公式及其逆公式都是等长的最短公式？你描述一下，从一公式生成另外48同态公式的一般性构造方法

铯_猪哥恐鸣

我已经写出了48个，另外48个是这48个的逆，并且这96个里面没有重复，很容易验证把。
公式F确实不可能构造出96个不同的状态，这个我完全同意，即便是公式RUF也只能构造出48个状态，这一点我前面就给出了解释，因为某些个构造重复了。

[ 本帖最后由 铯_猪哥恐鸣 于 2011-5-3 23:18 编辑 ]

铯_猪哥恐鸣

是的，你说的没错，这就是我给出的那个网页中提到的sym-coordinate。它的做法是：For each equivalence class we store the smallest coordinate as the representant of this class in an integer array
另外通过那个网站我大致知道，事实上利用对称并不能直接减小搜索量，但可以直接减小剪枝表(pruning table)的大小，换句话说，用同样的内存可以做更大的剪枝表，提高搜索效率。

[ 本帖最后由 铯_猪哥恐鸣 于 2011-5-3 23:31 编辑 ]