对公式进行局部窗口优化

noski

对于一个N步的魔方公式而言，且记为：Mov[1]，Mov[2]，Mov[3]，……，Mov[N]，每个Mov是魔方的标准操作之一。

如果初步设定窗口宽度为10，即认为10步公式以内的魔方状态是可以找到最少步，并且时间可接受的，

那么逐次对Mov[1]~Mov[10]，Mov[2]~Mov[11]，Mov[3]~Mov[12]，……这些公式中的窗口进行优化，保证每个窗口中都是最少步数。

通过选取适当窗口宽度，或许可以达到一个不错的优化效果。。仅是一个想法，没有编程验证过。。

superacid

好高深啊，不懂，帮忙顶了

铯_猪哥恐鸣

个人认为，窗口小于14的话优化效果不会很明显，另外就是无法保证最后得到的是最少步。

yq_118

的确可以对原有公式化简。

对于三阶魔方，谁知道窗口设为多少就一定是最少步了？

noski

回复 3# 的帖子
的确不能保证最后结果是最少步，但是还是有一定优化意义的

回复 4# 的帖子
对于三阶魔方，窗口设定为公式长度

yq_118

窗口设为上帝之数就可以保证最少步，不知道还可以更少不。

pengw

每截取公式一段X,找到X对应的状态Y,再由Y找到对应的最小步公式，然后替换，事前建好X长度的最短步数公式表，然而再长一点，就没法建表了，让窗口反复滑动，至到无可替换，问题是一段最小步加另一段最小步，不一定就是最小步。

穷举的实用性可能最多到三阶，目前连三阶也没有解决。

[ 本帖最后由 pengw 于 2010-4-18 01:01 编辑 ]

aubell

准备实践一下。

现在的可能存在的一个矛盾是：
窗口太窄，可能没效果；窗口太宽，要检验的公式的数量巨大。
不一定是最少步还没有关系。无限接近就可以了。

验证的时候，也许不使用公式，而使用“规则”，那样可以减少工作量。
从可化简的公式中总结出化简的规则，
让程序自己总结这些规则，自己扩展规则库。
做一个“生长着的程序”，让它自己变强。

[ 本帖最后由 aubell 于 2010-4-22 10:00 编辑 ]

真的是个游客

让我想到了快速排序，呵呵。

pengw

生长树的概念我早就提过,其容量就是将所有状态以跟根远近(最短路径)的原则组织进树,容量比全体状态稍大一点,一次性构造完成,以后全是对树进行搜索操作,以状态名进行向下的深度优先搜索,到根点为止,路径长度就是最短路径,最高的叶就是最远状态.已有成熟的的生长法则,除了受容量限制外,没有任何限制,