只有一个箱子的关卡的最佳答案的步数

skyivben

请参阅：推箱子关卡最佳答案的步数

[ 本帖最后由 skyivben 于 2012-4-19 21:23 编辑 ]

skyivben

左边是原来的关卡地图，最佳答案的步数是 23。
右边是改进后的关卡地图，最佳答案的步数是 25。
实际上 S(n, m) 是确定的，但实际上只有少数的 S(n, m) 的值是已知的，比如说 S(1, 6) = 4。
当 n, m 较大时，我们只知道 S(n, m) 的最小值，比如说：S(3, 6) ≥ 25。
希望各位朋友帮助改进 S(n, m) 的最小值。

skyivben

谢谢 sokoban 兄的指正。已经修正了我在博客园中的随笔，在 S(n, m) 的定义中加入了“可解的”这一限制。

skyivben

B(n, m) 函数不必太当真，可能其值增长太快了一点，所以叫SB猜想。
这只是提供一种思路，可能需要寻找一个更靠谱的C(n, m)，增长不要那么快。
我想这个C(n, m)函数虽然增长不那么快，但是C(23, 23)仍然可能超过十万。
这个SC猜想应该更容易证明一点。

skyivben

非常感谢 Cielo 兄和 sokoban 兄的评分和鼓励。

skyivben

如果我们定义一个函数 T(n) = S(n, n)，那么，如果有一个富翁给出一个悬赏：
在 2099-12-31 之前求出 T(123456789) 的值并证明该值的正确性的个人和单位，奖励十亿元人民币。
那么，这笔奖金非常可能发不出去。

skyivben

左边是原来的关卡地图，最佳答案的步数是 15。
右边是改进后的关卡地图，最佳答案的步数是 19。

更正：搞错了，右边的关卡地图，最佳答案的步数也是 15。

[ 本帖最后由 skyivben 于 2012-4-16 21:19 编辑 ]

skyivben

当 (n, m) 值较小时，编程计算 S(n, m) 是个很好的想法。
目前我还没有研究如何编程自动解答一个推箱子的关卡，所以暂时还无法编程计算 S(n, m) 的值。

skyivben

左边是原来的关卡地图，最佳答案的步数是 21。
右边是改进后的关卡地图，最佳答案的步数是 24。

skyivben

其实，对于 S(3, 5)，就算不考虑对称性造成的重复，也不用计算 2¹⁵ 种不同的迷宫布局。

首先，箱子、目标、人这三者至少需要占用两个位置。实际上，箱子需要单独占用一个位置，目标和人可以共同占用一个位置，也可以占用两个不同的位置。

其次，对对 n 和 m 均不小于 3 的关卡而言，如果关卡内部没有墙的话，决不可能是最复杂的。

所以，就算不考虑对称性造成的重复，对于 S(3, 5) 也只需计算 2^{15 - 2 - 1} = 4096 种不同的迷宫布局就行了。

[ 本帖最后由 skyivben 于 2012-4-16 21:56 编辑 ]