魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 491197|回复: 47
打印 上一主题 下一主题

解法步数随关卡大小成指数增长的关卡 [复制链接]

Rank: 7Rank: 7Rank: 7

积分
5289
帖子
3234
精华
19
UID
13140
性别

论坛建设奖 八年元老

跳转到指定楼层
1#
发表于 2009-6-8 20:11:49 |只看该作者 |正序浏览
在最坏的情况下,推箱子的解法步数和关卡大小(或者箱子数)的可以是指数关系。

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

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

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

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



1.jpg


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

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

b.jpg

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

Rank: 7Rank: 7Rank: 7

积分
5289
帖子
3234
精华
19
UID
13140
性别

论坛建设奖 八年元老

48#
发表于 2015-3-13 09:17:20 |只看该作者
shamy 发表于 2015-3-10 11:02
2个箱子可以吗?

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

使用道具 举报

Rank: 3Rank: 3

积分
816
帖子
181
精华
0
UID
1319509
性别
保密
兴趣爱好
推箱
47#
发表于 2015-3-10 11:02:48 |只看该作者
sokoban 发表于 2015-2-17 12:50
一个箱子不可能是指数关系。

2个箱子可以吗?

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
5289
帖子
3234
精华
19
UID
13140
性别

论坛建设奖 八年元老

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

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

使用道具 举报

积分
1
帖子
1
精华
0
UID
1335185
性别
保密
兴趣爱好
破解
45#
发表于 2015-2-12 23:16:47 |只看该作者
我是慕名而来的~
借帖求问高手是否可能设计单个箱子情况下
推箱子的解法步数和关卡大小可以是指数关系?

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

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
5289
帖子
3234
精华
19
UID
13140
性别

论坛建设奖 八年元老

44#
发表于 2012-7-31 14:52:37 |只看该作者
把34楼 Fibo 系列关卡和它的变形的分析写成了一篇博客文章:

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

使用道具 举报

Rank: 2

积分
215
帖子
64
精华
1
UID
1303898
性别
43#
发表于 2012-4-21 16:31:17 |只看该作者
非常有趣的关卡。学习了。

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
5289
帖子
3234
精华
19
UID
13140
性别

论坛建设奖 八年元老

42#
发表于 2009-7-23 15:22:05 |只看该作者
说的有理,这类关卡很少有人能真的动手解一遍。解个简化版就足够了

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

使用道具 举报

Rank: 4

积分
1167
帖子
232
精华
2
UID
103807
性别
保密
41#
发表于 2009-7-23 15:15:48 |只看该作者
我个人不喜欢这个类型的关卡,将推箱子变成了体力活!
其实适当简化一下,表达出关卡的难点和原理就可以了。

使用道具 举报

Rank: 8Rank: 8

积分
1918
帖子
588
精华
5
UID
145
性别

魔方破解达人 八年元老

40#
发表于 2009-7-22 08:46:47 |只看该作者
37楼朋友说的对,是这个数。50355四舍五入就是10万。

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-11-26 03:14

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部