魔方吧·中文魔方俱乐部

标题: 对公式进行局部窗口优化 [打印本页]

作者: noski 时间: 2010-4-17 23:07:49 标题: 对公式进行局部窗口优化

对于一个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 时间: 2010-4-17 23:26:55

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

作者: 铯_猪哥恐鸣 时间: 2010-4-17 23:31:06

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

作者: yq_118 时间: 2010-4-18 00:04:03

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

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

作者: noski 时间: 2010-4-18 00:14:06

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

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

作者: yq_118 时间: 2010-4-18 00:56:03

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

作者: pengw 时间: 2010-4-18 00:58:49

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

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

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

作者: aubell 时间: 2010-4-18 12:36:43

准备实践一下。

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

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

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

作者: 真的是个游客 时间: 2010-4-18 13:43:36

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

作者: pengw 时间: 2010-4-18 15:34:54

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

作者: 铯_猪哥恐鸣 时间: 2010-4-18 19:35:43

回楼上，那个不叫生长树，叫搜索树。还有就是搜索大规模数据的时候是要剪枝的，不是搜索所有状态的。

作者: pengw 时间: 2010-4-18 20:45:32

楼上理解有误,这颗最短路径树在生长过程中就完成剪枝,生长完成后,也就是说,每个状态都占据树上一个合适的位置后,再去搜索,因此,搜索这样一颗树是最无技术含量的编程,从任何一个结点一直下到根(没有上),就是根到这个结点的最短路径,最高的叶就是最远状态,结点之间90度/步,每个结点有属于它的唯一一步,从任意一点下树过程,顺序收集每一个结的步,这个步的集合就是点到根的最短公式,只要这颗树生长完成,所谓最小步就是一个简单的查表问题.

这颗树可以慢慢生长,你只须要在你的电脑中装一个ORACLE数据库,数据库拥有几个T的空间,写一个树的生长程序,随时将长出来的状态加入数据库即可,生长过程可以随时停止或开始,至到完成,最终的树就是一个含所有状态的ORACLE数据库，外观上看，可能是五六个1T的硬盘（估计，没有细算）

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

作者: 铯_猪哥恐鸣 时间: 2010-4-18 23:05:00

回楼上，其实本质还是一个图，只不过遍历的方式不同罢了。至于这个算法，现在国外也确实有人在做，不过对于三阶魔方他们也只做到了第13层，毕竟4^19次太大了，即使除去同态也在当前能接受的范围之外。
另外对于求单个状态的最少步，其实并不用遍历整个图。

作者: pengw 时间: 2010-4-18 23:51:48

对,现在的问题就是存贮量过大,求单个状态的最小步就从这个点一直下树下到根就行了,根本无须遍历全图,使用起来很方便,生长树算法极其简单,至于求任意二个状态最小步,也是一直下树,为什么?考你一下

归根结底,这些都是最蠢的方法,恐怕能对付的最多就是三阶,然而,四阶,五阶又奈何?必然发展一种直接状态分析法

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

作者: noski 时间: 2010-4-19 00:11:11 标题: 回复 14# 的帖子

这一点赞同的，无论再怎样剪枝、消同态，暴力搜索都不是终极办法，否则随着阶数的提高，这个暴力搜索将永无止境了。除非，它真是一个NP完全问题。。

在魔方简单的变换规则下，却到现在都没有一个合适的理论能计算一个状态的最少步数，神奇啊。

作者: 铯_猪哥恐鸣 时间: 2010-4-19 00:26:43

是这样的，魔方状态集合构成的是图，所谓的树的概念是只有我们以某节点作为根，在搜索过程以后才自然生成了一棵搜索树，所以我不是很明白你说得从一个节点沿着树往下的意思。
至于你考考我的对于A,B两状态，求T,使得AT=B这个问题，等价于求T使得B'AT=1，即搜索B'A这个状态的还原步骤即可，不知这是否是你要得答案？

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

作者: pengw 时间: 2010-4-19 07:32:38

回14楼:
如果不发展一种从状态解析最短路径的方法,的确将没有出路,我想穷举法到三阶就止步了.即是穷举三阶,希望不要买一车硬盘回家,我正在发展,有相当大的进展，但遭遇强大的共扼阻力。例如：

U层：角块自然顺向四轮换
D层：棱块自然逆向四轮换

抛弃共扼，就一步还原，但是共扼的存在，仅选层就有24*24种组合，每一个组合还要独立确定fFf',你说该几步，即便如此，也比穷举好很多。

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

不过偿试发展一种直接分析方法，让我完成发展变换理论的工作后，再次有机会享受魔方带来的思维乐趣，极有可能没有结果，但无所谓，享受的是过程

[ 本帖最后由 pengw 于 2010-4-19 07:37 编辑 ]

作者: pengw 时间: 2010-4-19 07:40:39

回16楼：
距根最短路径相同的点，都在树的同一层，所以，任意结点一直下树到根就是短路径求解，树的深度就是最远状态，有时间我把算法整理出来，或许对各位有用,在长出每一层的同时,同态都会被消灭至只留一下

[ 本帖最后由 pengw 于 2010-4-19 08:35 编辑 ]

作者: ggglgq 时间: 2010-4-19 11:06:47

　　
　　

嗯，明眼人一看就知道，按楼主的构造方法，最好的结果是：循环变换的

子变换。  其中：窗口宽度小于魔方最远状态变换长度， N 小于  魔方最远

状态变换长度的 2 倍。
　　
　　

循环变换的子变换中所有的（循环变换的）半子变换，均是最少步变换，

但长度大于其（循环变换的）半子变换的变换，也满足楼主的条件，却不是

最少步变换。看到 aubell 结合楼主的思路利用“人工智能”解决最少步问题

的探索精神，着实令人敬佩。希望由此得到一个求魔方循环变换的简便软件。

　　
　　
　　
　　

[ 本帖最后由 ggglgq 于 2010-4-19 12:33 编辑 ]

作者: ggglgq 时间: 2010-4-19 11:08:09

　　
　　

提供一个图，以便大家更直观地理解楼主的问题与循环变换的关系。

　　
　　
　　
　　
　　

[ 本帖最后由 ggglgq 于 2010-5-25 09:18 编辑 ]

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