回复 21# 的帖子
不是很理解你的意思,比如你给出UFLF,那么我根据你给定的公式给出了上面48个状态,再加上它们的逆状态,总共96个状态。 寻找对称的根本目的是缩小搜索集合,前提是所有同态或同构有相同的最短路径,除此以外还有什么意义?问题是,不是所有状态都有相同数量的同构或同态,要利用这个所谓的同态概念,首先就得以同态为序构造一个状态数据库,如何实现构造? 你不妨将UFLF的另外95个公式写出来,让大家明白96 同态的意义,看看是否都是等长的最短公式,不过有一点可以肯定,公式F及其逆公式F‘是不可能在24个作用方位构造96个互不相同的状态[ 本帖最后由 pengw 于 2011-5-3 23:17 编辑 ]
回复 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 编辑 ]
回复 24# 的帖子
我已经写出了48个,另外48个是这48个的逆,并且这96个里面没有重复,很容易验证把。公式F确实不可能构造出96个不同的状态,这个我完全同意,即便是公式RUF也只能构造出48个状态,这一点我前面就给出了解释,因为某些个构造重复了。
[ 本帖最后由 铯_猪哥恐鸣 于 2011-5-3 23:18 编辑 ] 回20楼:
你确认这所给出的这组公式及其逆公式都是等长的最短公式?你描述一下,从一公式生成另外48同态公式的一般性构造方法 时间不早,明天还要成都飞昆明,建议明天继续讨论
回复 27# 的帖子
等长显然,都是4步,是否最短这个因为只有4步,所以很容易验证,事实上由于原公式可以通过某个Si变换过去,那变换后的公式当然也能同样的变换回来,所以只要原公式是最短,则变换后的公式一定最短且和原公式一样长。好的,对于给定的长度为n的公式A = A1A2A3...An,生成的第i个公式Bi = Si-1 A Si = Si-1 A1 Si Si-1 A2 Si ... Si-1 An Si
由于A1, A2, ..., An都是基本旋转(RUFBLD等),所以S_i^-1 Ak S_i事先算好即可,不需要给出A再另外计算。
大师辛苦~
[ 本帖最后由 铯_猪哥恐鸣 于 2011-5-4 00:00 编辑 ] Si-1与Si是二个互逆的公式?