对公式进行局部窗口优化

铯_猪哥恐鸣

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

pengw

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

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

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

铯_猪哥恐鸣

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

pengw

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

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

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

noski

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

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

铯_猪哥恐鸣

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

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

pengw

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

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

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

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

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

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

pengw

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

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

ggglgq

　　
　　
  
    嗯，明眼人一看就知道，按楼主的构造方法，最好的结果是： 循环变换 的
  
子变换 。  其中： 窗口宽度 小于 魔方最远状态变换长度， N 小于  魔方最远

状态变换长度 的 2 倍。
　　
　　
  
    循环变换 的子变换中所有的 （循环变换 的）半子变换，均是 最少步变换，
  
但长度大于其 （循环变换 的）半子变换 的变换，也满足楼主的条件，却不是
  
最少步变换。看到 aubell 结合楼主的思路 利用“人工智能”解决最少步问题
  
的探索精神，着实 令人敬佩。希望由此得到一个求魔方 循环变换 的简便软件。
  
　　
　　
　　
　　

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

ggglgq

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

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