关于魔方的状态表示方式？

pengw

原来你的48同态来自二阶段搜索算法,那么,我提一个问题,你如何从状态空间(N阶定律制约)中分辩出那些是48同态状态?

如果你将N阶定律简单地理解成只是计算状态数和指导如何组装魔方,那未免太过偏执,事实上N阶定律还能告诉你更多,哪些变换可行,哪些不可行,公循环周期如何计算,复原算法如何构造,不同状态之间转换公式步数的奇偶性等等.公式不可能告诉你状态空间大小,对吧,如果你不知道状态空间大小,你又如何评估你的搜索难度?

二阶段搜索算法只是一个基于经验的较短路径算法,而非最短路径算法,

[ 本帖最后由 pengw 于 2010-3-20 17:51 编辑 ]

pengw

从公式到状态,这很好办,但从状态到公式就难办了,事实上你面临的就是这个问题.正如前面smok所言,就算将三阶状态T分成96 个/组,即你的搜索空间大小是F=T/96,你还要为这F个组中的每一个确定的最小步公式模板，我认为这几乎等于是没有效果.

[ 本帖最后由 pengw 于 2010-3-20 17:59 编辑 ]

superflip

哈哈，终于回到正常的讨论了，CE既能2阶段搜索，也能求最小步，点一下optimal即可~

你上楼的担忧恰恰就是为什么现在CE能算最小步，就是能从一个已知的状态知道他的48个同态，而不需要记住已知的那个状态是用什么公式打乱得来的~

很简单，不是吗？（但是楼主认为CE这块的处理还是不够高效，所以才来问你们是否理论上有更好的状态表示方法有利于求解3阶最小步！你们是否也应该去看看ce的算法呢~ 和楼主讨论就更充分了）

ps：我前面只是举例你的理论主要能干什么，不可能面面俱到，但是你也曾说过，会计算N阶的状态数不就相当于理解核心理念了吗？

[ 本帖最后由 superflip 于 2010-3-20 18:34 编辑 ]

pengw

问题是你真的认为你理解了N阶状态数计算的全部意义了？

据我所知，二阶段法的思想是，有一个环形岛链，外围的鱼船总能得到一个靠得最近的小岛，这些小岛之间比此又有较短的路径，因此二个鱼船的较近距离通过借岛链来间接取得。

问题是，如果二个鱼船比此靠得很近，还须要借助岛链吗？

澄清一点，二阶段算法并不是最短路径算法，只不过通过将状态分为外围与岛链二组，间接缩小搜索空间之权宜之计

[ 本帖最后由 pengw 于 2010-3-20 18:43 编辑 ]

pengw

N定律可以立即断定任意二个状态之间的最短路径是奇数步还是偶数步，奇怪吗？

superflip

CE既能2阶段搜索，也能求最小步，点一下optimal即可~

晕倒~ 版主用过CE吗？箭头旁边有个optimal的单选框，可以求解真正的最小步，不是2阶段，但是楼主觉得他的算法还有很大改进余地，所以才来理论区问你们的。

superflip

回35#： 这有啥奇怪的，你的一步是以90度为一步的吧~

pengw

如何证明你的结果是最小步？

superflip

额的神啊，我是来普及CE软件的~

他就是剪枝穷举~你说会不是吗？所以少48倍空间才使得计算有效多了~

[ 本帖最后由 superflip 于 2010-3-20 18:55 编辑 ]