魔方吧·中文魔方俱乐部

标题: 关于24同构 [打印本页]

作者: pengw 时间: 2011-4-29 22:23:18 标题: 关于24同构

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

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

作者: 乌木 时间: 2011-4-30 11:10:16

上述定义中“已复原魔方”的条件能否扩展为“任一态”？即，同一个打乱的初态，在24个方位上分别执行同一公式，得到的24个状态，如果互不相同，是否可以叫（关于那个初态的）“同构”？当然，这样，更加不直观了。

作者: 乌木 时间: 2011-4-30 11:29:26

试试下面这样的24个态是否互不相同：
[java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CU U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CU2 U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CU' U R B L F U' F' L' B' R'[/param]
[/java3]

[java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CR U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CR CU U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CR CU2 U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CR CU' U R B L F U' F' L' B' R'[/param]
[/java3]

[java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF CU U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF CU2 U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF CU' U R B L F U' F' L' B' R'[/param]
[/java3]

[java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF2 U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF2 CU U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF2 CU2 U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF2 CU' U R B L F U' F' L' B' R'[/param]
[/java3]

[java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF' U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF' CU U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF' CU2 U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF' CU' U R B L F U' F' L' B' R'[/param]
[/java3]

[java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CR' U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CR' CU U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CR' CU2 U R B L F U' F' L' B' R'[/param]
[/java3][java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CR' CU' U R B L F U' F' L' B' R'[/param]
[/java3]

初步查看下来，24个态没有同态，正是24同构态。

[ 本帖最后由乌木于 2011-4-30 12:37 编辑 ]

作者: 乌木 时间: 2011-4-30 17:02:36

3楼的24个同构态中，四号角周围的三棱轮换态有三个，见下图：
24个同构态中的三个.JPG

其中第一态也可以这样做：
[java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]U2 (F U)2 (F' U' )3 [/param]
[/java3]

其中第二个也可以这样获得：
[java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt](R' F' )3 (R F)2 R2 [/param]
[/java3]

第三个也可以这样获得：
[java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt](U' R' )3 (U R)2 U2 [/param]
[/java3]

不过，还有一种位置变化一样但色向变化不同的三棱轮换的情况，就不属于3楼的24个同构系列了：
[java3=150,180]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]R B R2 U' MF' U2 MF U' R2 B' R' [/param]
[/java3]

三个棱块要么都不反向，要么只能反向两个，所以只能有上述四种色向变化。

问题是，假如四种状态直接放在面前，不知道获得的步骤，好像不容易区分其中哪几个是同构态吧？如果仅仅根据位置的变化来看的话，判断同构态容易出错的吧？

[ 本帖最后由乌木于 2011-4-30 18:34 编辑 ]

附件: 24个同构态中的三个.JPG (2011-4-30 17:02:36, 22.67 KB) / 下载次数 59
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQxMzgyfGQwYjhkMTg1fDE3MzIyOTc0MTJ8MHww

作者: 乌木 时间: 2011-4-30 22:28:30

看来按照定义得到24个态之后，检查它们是否互不相同这一工作很要紧，比如，4楼最后一个公式 RBR2U'MF'U2MFU'R2B'R'，当魔方初态改变取向后，其中四号角周围三棱轮换的另两个态CR CU RBR2U'MF'U2MFU'R2B'R' 和CF' CU' RBR2U'MF'U2MFU'R2B'R' ，居然三者是同态！所以公式RBR2U'MF'U2MFU'R2B'R' 就没有24个同构，对吧？能否看作每三个同态简并之后，24个态就简并为8个同构了？
[java3=150,270]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]R B R2 U' MF' U2 MF U' R2 B' R'[/param]
[/java3]
[java3=150,270]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CR CU R B R2 U' MF' U2 MF U' R2 B' R' CU' CR'[/param]
[/java3]
[java3=150,270]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]CF' CU' R B R2 U' MF' U2 MF U' R2 B' R' CU CF[/param]
[/java3]

[ 本帖最后由乌木于 2011-4-30 22:43 编辑 ]

作者: Cielo 时间: 2011-5-1 01:52:37

对于任一个公式，确实不一定能得到24个不同的状态。

最极端的例子：十二棱翻色。

作者: pengw 时间: 2011-5-1 21:11:46

发贴后，一直在忙，今天才上网，十分抱歉。事实上，我至少找到二组真正意义上的24同构，在此之前，也不十分确定就一定能够找到。不但找到24同构，同时也找到与他们对称的24同构，即逆公式对应的另一组24同构，之前被称着什么48同态。寻找同构与对称（不用再说成是什么同态，谨慎或逻辑没有问题的人不会这样定义）的本质意义在于缩小搜索集合。

确如CIELO所言，不是所有状态都有24同构，例如，复原状态没有同构也没有对称，仅有一个中心块转180度的状态有6个同构，但是没有对称。

相似变换（某人所说的循环变换）可视为拓扑相同的一组状态，这种说法并不完全正确，须要付加一个条件才正确，有时间我会证明这一点。

所有同构的状态一定拓朴相同，但拓朴相同的状态，不一定是同构。

作者: pengw 时间: 2011-5-2 07:41:02

就上面的讨论而言,如果一个公式是最短公式,最多可以找到48个状态与之对应,目前找到的最小对应是1,有谁能分别找出2,3,4这样的对应?镜子里的魔方就不要讨论了,还是放在明年的愚人节上表演.

即然不是每一个状态都有24同构或与之对称的24同构(cielo的举列只有一个),则48这个数字并不具有普适价值,至于48同态,则完全是一个非正常状态的匪夷所思的发明.希望我的"猜想"能够被优雅地证伪,而不是仅仅听到无可奈何的悲吟或扰人又绝望的惨叫,诊治这样的症状需要去专门的地方,而不是论坛,

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

作者: woshicsxyk 时间: 2011-5-2 08:20:50

那么一个三换棱的PLL似乎也行的通。

作者: pengw 时间: 2011-5-2 08:38:22

对于一个表层棱三元置换公式,有二种可能,顺置换与逆置换,可能的三置换块有4个组合,这样算来,也就有24同构及其对称的24同构

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

作者: pengw 时间: 2011-5-2 08:48:43

可以肯定,如果一个公式是最短公式,则其逆公式也是最短公式.从前有人谈到镜像公式,我还真不知道,任意公式的镜像公式是如何定义,这个定义的本质意义是什么?根据某些描述,由此产生了96同态,请问这96同态的最短步数都相同吗?如果不同,这样的定义又有什么意义?

况且,任意公式都有镜像公吗?任意公式及其逆公式,以及他们对应的镜像公式都是等长的最短公式?即然有人捣鼓这类概念,就一定能回答这类问题,况且也必须回答这类问题,否则,发明这些概念又为何?

我无意糟蹋高人神来之笔,但是,我有权力要求高人举证回答这类显然易见问题,高人也不能说什么就是什么,自已还不屑于证明.即使是咱们的数学太差,但至少也看得明白证明你自已的魔方状态.

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

作者: 铯_猪哥恐鸣 时间: 2011-5-3 21:10:00

不想浪费精力在翻译和翻译产生的歧义上，请看下面网页吧
http://kociemba.org/math/symmetries.htm

大致的解释就是，我们可以定义4种“基”对称变换（"basic" symmetries）：
S_URF3, a 120 degree       turn of the cube around an axis through the URF-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 the RL-slice plane.
则所有的对称变换可以表示成
(S_URF3)x1 * (S_F2)x2 * (S_U4)x3 * (S_LR2)x4with x1 from 0..2, x2 from 0..1, x3 from 0..3 and x4 from 0..1.
这样就一共定义了48个变换，此处不妨记为S_0, S_1...S_47
那么某个变换A的对称变换们为
B_i = S_i^-1 A S_i
这样对于某个状态A，就定义了48个不同的状态B_i，它们就是我们说的A的48同构，或者同态（我不知道这两个名词是怎么来的，也不想争论到底用哪个名词，总之我们找到了48个变换）
最后，存在某些变换A，使得B_i = B_j。也就是说并不是每个变换都可以找到48个同构变换，但事实上确实只有少数状态存在少于48个变换，具体这些状态他那个网站里都有。

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

作者: pengw 时间: 2011-5-3 21:45:10

看了半天,原来说的还是24同构及其对称24同构,显然那个洋文把问题说得太复杂,关键是,我没有看到96同态是如何诞生的

作者: pengw 时间: 2011-5-3 21:49:39

12楼不妨用二阶枚举一个48同态,另外,这48个同态相对于基态,都有同样的最短路径?如何证明?

作者: 铯_猪哥恐鸣 时间: 2011-5-3 22:00:02

好的，很高兴您在线。
第一个问题：
96同构是怎么产生的：
不知道你有没有注意到，上面所说的四个基对称变换中没有逆变换，事实上，如果加上逆变换，那么就有96个所谓同构了，当然是否应该叫“同构”我自己也没有把握，暂且就这么叫了。
第二个问题：
如何证明相对于基态都有最短路径：
对于上述给出的S_0, S_1, ... S_47，容易证明，如果A为某一种转动（RUBLDF），则S_i ^-1 A S_i也是一种转动。这样就很容易证明同态对于基态都有同样的最短路径。

作者: pengw 时间: 2011-5-3 22:05:25

相对三阶复原状态，UFL显然是一个最短公式，那么其对应的另外47个同构公式是什么模样？你可以枚举出来否？

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

作者: 铯_猪哥恐鸣 时间: 2011-5-3 22:19:45 标题: 回复 16# 的帖子

手动写起来比较耗时间，久等了，包括UFL总共48个，请核对。
UFL
URF
UBR
ULB
RFU
RDF
RBD
RUB
BUL
BRU
BDR
BLD
DFR
DLF
DBL
DRB
FUR
FLU
FDL
FRD
LUF
LBU
LDB
LFD
U'F'R'
U'L'F'
U'B'L'
U'R'B'
L'F'U'
L'D'F'
L'B'D'
L'U'B'
B'U'R'
B'L'U'
B'D'L'
B'R'D'
D'F'L'
D'R'F'
D'B'R'
D'L'B'
F'U'L'
F'R'U'
F'D'R'
F'L'D'
R'U'F'
R'B'U'
R'D'B'
R'F'D'

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

作者: pengw 时间: 2011-5-3 22:56:29

楼上的结果与1楼命题没有任何区别，如果将你的公式组求逆，结果还是原来的公式组，这就是所谓的96态？

[ 本帖最后由 pengw 于 2011-5-3 23:01 编辑 ]

作者: 铯_猪哥恐鸣 时间: 2011-5-3 22:58:03 标题: 回复 18# 的帖子

17楼不就是48个等长公式吗？

作者: 铯_猪哥恐鸣 时间: 2011-5-3 23:00:50 标题: 回复 18# 的帖子

求逆的话，由于你给的公式的特殊性，所以确实找不到96个，这一点我前面应该提到了。比如如果你给的公式是UFLF，那么48个等长公式为：
UFLF
URFR
UBRB
ULBL
RFUF
RDFD
RBDB
RUBU
BULU
BRUR
BDRD
BLDL
DFRF
DLFL
DBLB
DRBR
FURU
FLUL
FDLD
FRDR
LUFU
LBUB
LDBD
LFDF
U'F'R'F‘
U'L'F'L’
U'B'L'B‘
U'R'B'R’
L'F'U'F‘
L'D'F'D’
L'B'D'B‘
L'U'B'U’
B'U'R'U‘
B'L'U'L’
B'D'L'D‘
B'R'D'R’
D'F'L'F‘
D'R'F'R’
D'B'R'B‘
D'L'B'L’
F'U'L'U‘
F'R'U'R’
F'D'R'D‘
F'L'D'L’
R'U'F'U‘
R'B'U'B’
R'D'B'D‘
R'F'D'F’

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

作者: pengw 时间: 2011-5-3 23:05:55

再说一次，你定义的48同态，与我在本贴所说的“24同构加上与其对称的24同构”没有本质区别。我想让你找出一个最短公式（是大家容易确认的）对应的所有96个状态。

作者: 铯_猪哥恐鸣 时间: 2011-5-3 23:09:16 标题: 回复 21# 的帖子

不是很理解你的意思，比如你给出UFLF，那么我根据你给定的公式给出了上面48个状态，再加上它们的逆状态，总共96个状态。

作者: pengw 时间: 2011-5-3 23:12:02

寻找对称的根本目的是缩小搜索集合，前提是所有同态或同构有相同的最短路径，除此以外还有什么意义？问题是，不是所有状态都有相同数量的同构或同态，要利用这个所谓的同态概念，首先就得以同态为序构造一个状态数据库，如何实现构造？

作者: pengw 时间: 2011-5-3 23:15:18

你不妨将UFLF的另外95个公式写出来，让大家明白96 同态的意义，看看是否都是等长的最短公式，不过有一点可以肯定，公式F及其逆公式F‘是不可能在24个作用方位构造96个互不相同的状态

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

作者: 铯_猪哥恐鸣 时间: 2011-5-3 23:15:36 标题: 回复 23# 的帖子

是的，你说的没错，这就是我给出的那个网页中提到的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 编辑 ]

作者: 铯_猪哥恐鸣 时间: 2011-5-3 23:17:27 标题: 回复 24# 的帖子

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

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

作者: pengw 时间: 2011-5-3 23:41:07

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

作者: pengw 时间: 2011-5-3 23:43:28

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

作者: 铯_猪哥恐鸣 时间: 2011-5-3 23:55:29 标题: 回复 27# 的帖子

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

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

作者: pengw 时间: 2011-5-4 15:58:51

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

作者: pengw 时间: 2011-5-4 16:13:42

定义:任意公式及其逆公式在复原魔方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 编辑 ]

作者: 小明的马甲 时间: 2011-5-4 16:34:36 标题: 回复 31# 的帖子

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

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

作者: 42752277 时间: 2011-5-4 20:58:28

很多JAVA

.

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