解法步数随关卡大小成指数增长的关卡

sokoban

在最坏的情况下，推箱子的解法步数和关卡大小（或者箱子数）的可以是指数关系。

下面举一个例子，不知道还有没有别更简单的例子。这个例子是我从别处看来的，原始地址一时找不着了。

我们构造一系列推箱子关卡L(n)，每个关卡的大小(指的是长乘于宽)是S(n)=(10+13n) x 17，然而解答所需要的推数是P(n)=2+12*(2^n-1)，这相对于关卡的大小是成指数增长的。

L(1)如下图所示。我们注意到只有左上角的一个箱子没有归位。而且这个箱子一定只能作为最后一个被归位的箱子，因为归位后，仓库管理员就被困在左上角出不来了。要把左上角的箱子归位，仓库管理员必须经过图中用红箭头指示的三个“门”所围成的“房间”。这个房间里面的箱子都是已经归位了的，所以只能把某些箱子推离再推回原位。

对于仓库管理员来说，只能通过右上角的门进入房间。容易看出，仓库管理员必需两次从右上角进入这个房间。第一次进入后，绕一个大弯把房间里左上角的箱子向左推一格，把中间的箱子归位后，再从下面的门出来。第二次则不用绕弯直接从上面通过房间，然后从左上角的门出去。第一次进入房间要推9下，第二次要推3下。






L(n)就是在L(1)的基础上，把中间的房间复制n份连起来。这样从左到右每个房间分别要进入2次、4次，8次... 2^n次。下图是L(3)。

exp.rar (247 Bytes, 下载次数: 72)

2009-6-8 20:11:49 上传

下载次数: 72

[ 本帖最后由 sokoban 于 2009-6-10 23:34 编辑 ]

sokoban

shamy 发表于 2015-3-10 11:02
2个箱子可以吗？

不能限制箱子数目。因为箱子数目限定了的话，比如只有不超过k个箱子（k是一个常数，比如2），关卡大小是n个格子。那么总状态数是 n^k 数量级，也就是说顶多是n的一个多项式步长，不可能达到指数步长。

shamy

sokoban 发表于 2015-2-17 12:50
一个箱子不可能是指数关系。

2个箱子可以吗？

sokoban

yyhandsome 发表于 2015-2-12 23:16
我是慕名而来的~
借帖求问高手是否可能设计单个箱子情况下
推箱子的解法步数和关卡大小可以是指数关系？
...

一个箱子不可能是指数关系。

yyhandsome

我是慕名而来的~
借帖求问高手是否可能设计单个箱子情况下
推箱子的解法步数和关卡大小可以是指数关系？

只看到jinyou提供的步数大约是平方关系

sokoban

把34楼 Fibo 系列关卡和它的变形的分析写成了一篇博客文章：

http://sokoban.ws/blog/?p=430

skyivben

非常有趣的关卡。学习了。

sokoban

说的有理，这类关卡很少有人能真的动手解一遍。解个简化版就足够了

不过这类关卡拿来分析，计算一下步数和箱子数之间的关系，倒有点意思。

xxx821006

我个人不喜欢这个类型的关卡，将推箱子变成了体力活！
其实适当简化一下，表达出关卡的难点和原理就可以了。

jinyou

37楼朋友说的对，是这个数。50355四舍五入就是10万。