华容道二横布局状态集的最大直径是230步，一横布局最大直径是145步

hubo5563

华容道二横布局状态集的最大直径是230步，是如下两个布局的距离：


也就是说从第一个布局到第二个布局最少需要走230步。

第一个布局的最优解是138步。

[ 本帖最后由 hubo5563 于 2011-4-17 18:05 编辑 ]

aubell

请问大师：华容道和15滑块是不是差不多啊？是否好比捆绑魔方和普通魔方？

乌木

我好奇问问：
这一布局走得出的状态集是否不止230个态？“230”只是所述两个态之间的最少步数，即不必“历遍”所有的态，对吗？至于这230步是该状态集的最大直径，是否唯一的？即左边状态到别的态的步数，有的当然小于230，有的也是230，但没有大于230的，对吗？正像三阶魔方的最远态（目前认为是20步态）不止一个。如果这种布局的华容道最远态是唯一的，则说明它和魔方还是不同的。
如果四小块无区别，两个横块无区别，三个竖块也无区别，那么两态之间还是230步吗？
还有，除了“走得出”态之外，是否还有组装得出但走不出的状态？好像魔方有“转得出态”和“装得出转不出态”一样。

[ 本帖最后由 乌木 于 2011-4-17 16:12 编辑 ]

hubo5563

这一布局走的出的状态很多，共有81340个状态，230只是所述两个态之间的最少步数。230步是该状态集的最大直径，不是唯一的。从状态1开始到最小230步共3个状态，状态2是其中之一。没有大于230步的。这里的小块和竖块没有区别。除了“走得出”态之外，还有组装得出但走不出的状态。
另外的两最远状态为：


从第二布局开始找最远状态也有3个，除第一布局外还有如下两个：


二横布局也有不连通的状态，比如：

这个布局最多走出7个状态，和上面的大集是不连通的。



一横布局下面是两个不连通的布局：



也就是说从左面状态走不到右面状态，从右面状态也走不到左面状态。而且凡是左边状态能到达的状态，和凡是右边状态能到达的状态是不连通的。

也就是说这两个布局代表两个不连通状态集，并且状态数是相同的，都是25955个状态。

[ 本帖最后由 hubo5563 于 2011-4-17 18:01 编辑 ]

zxy6350479

买了个木板的 好像长方型? 楼主的好像正方形? 看来自己做更好看 直接楼上放大打印(彩色) 就行

hubo5563

原帖由 aubell 于 2011-4-16 20:50 发表
请问大师：华容道和15滑块是不是差不多啊？是否好比捆绑魔方和普通魔方？

我觉得还不同。

hubo5563

一横布局最大直径是145步
是如下两个状态的距离：



从左面状态找最远点可以找到4个，另外三个如下：



并且从四个最远态找最远态都只有一个就是第一个。

第一个状态作为布局，最优解是93步。

这也是华容道一横布局最优解步数最多的一个布局，另一个就是它的对称状态。

[ 本帖最后由 hubo5563 于 2011-4-17 18:31 编辑 ]