关于24同构

pengw

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

铯_猪哥恐鸣

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

pengw

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

pengw

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

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

铯_猪哥恐鸣

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

铯_猪哥恐鸣

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

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

pengw

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

pengw

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

铯_猪哥恐鸣

等长显然，都是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

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