魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 3232|回复: 10

推箱子关卡最佳答案的步数 [复制链接]

Rank: 2

积分
215
帖子
64
精华
1
UID
1303898
性别
发表于 2012-4-19 22:51:40 |显示全部楼层

我在“只有一个箱子的关卡的最佳答案的步数”的15楼中提到:



进一步,我们定义以下函数:

  • P(n, m, k) 表示大小为 (n + 2) x (m + 2) 的可解的最复杂的最多 k 个箱子的关卡的最佳答案的步数。
  • Q(n, m, k) 表示大小为 (n + 2) x (m + 2) 的可解的最复杂的刚好 k 个箱子的关卡的最佳答案的步数。
  • R(n, m) = P(n, m, n * m),表示大小为 (n + 2) x (m + 2) 的可解的最复杂的关卡的最佳答案的步数。
  • S(n, m) = Q(n, m, 1),表示大小为 (n + 2) x (m + 2) 的可解的最复杂的只有一个箱子的关卡的最佳答案的步数。
显然,R(n, m) ≥ S(n, m),也更值得研究。










  • R(1, 2) = 0
  • R(2, 2) = 0
  • R(1, 3) = 1 : D
  • R(2, 3) = 5 : ruulD
  • R(3, 3) = 10 : drruulDrdL
  • R(1, 4) = 2 : DD
  • R(2, 4) = 7 : uruulDD
  • R(3, 4) ≥ 17 : RluUdrruulDrdLulD
  • R(4, 4) ≥ 25 : luUrurrdddLLrruLruulDDrdL
上述结论还有很大的改进余地。



请参阅:再谈推箱子关卡最佳答案的步数

Rank: 4

积分
1872
帖子
1569
精华
0
UID
1307004
性别
兴趣爱好
其它
发表于 2012-4-19 22:58:31 |显示全部楼层
推箱子这玩意太复杂了。。。我这智商也就我小游戏上推箱子前几关了

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
5262
帖子
3216
精华
19
UID
13140
性别

论坛建设奖 八年元老

发表于 2012-4-19 23:21:03 |显示全部楼层

回复 2# 的帖子

目前步数最多的关卡(箱子个数没有限制)可能暂时还是利用 Fibo 系列关卡来构造。参看此帖:(34楼 金优先生的回帖)

http://bbs.mf8-china.com/viewthr ... mp;page=4#pid621511

使用道具 举报

Rank: 2

积分
587
帖子
305
精华
4
UID
1263453
性别
居住地
成都市
WCA ID
2010SHIX01
兴趣爱好
理论

四年元老 十年元老 十二年元老

发表于 2012-4-20 01:12:08 |显示全部楼层
好厉害,虽然看不懂。。

使用道具 举报

Rank: 2

积分
215
帖子
64
精华
1
UID
1303898
性别
发表于 2012-4-20 21:43:44 |显示全部楼层

更正: R(3, 4) 的最小值


1楼的 R(3, 4) 不对,应该是:
R(3, 4) ≥ 13 : uURdrdLuuurDD

使用道具 举报

Rank: 2

积分
215
帖子
64
精华
1
UID
1303898
性别
发表于 2012-4-20 21:48:13 |显示全部楼层

新的 R(3, 4) 关卡



R(3, 4) ≥ 21 : rrddlldRuruullDDrUruL
不知是否有更好的解答。

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

使用道具 举报

Rank: 2

积分
215
帖子
64
精华
1
UID
1303898
性别
发表于 2012-4-21 16:52:16 |显示全部楼层
我在“推箱子关卡最佳答案的步数”中定义了 B(n, m) 函数:
  • B(1, m) = m - 2,      when m > 0
  • B(n, m) = B(m, n),   when m > 0, n > m
  • B(n, m) = B(n - 1, m - 1) + B(n - 1, m),  when m > 1, n > 1, n ≤ m
并提出SB猜想:S(n, m) ≥ B(n, m)。
现在我们提出RB猜想:R(n, m) ≥ B(n, m)。
由于R(n, m) ≥ S(n, m),所以如果SB猜想成立的话,RB猜想也就一定成立。
由于B(n, m)增长得非常快,所以SB猜想未必成立。虽然目前还没有找到SB猜想的反例。
但是RB猜想是非常有可能成立的。

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
5262
帖子
3216
精华
19
UID
13140
性别

论坛建设奖 八年元老

发表于 2012-4-21 17:07:38 |显示全部楼层

回复 7# 的帖子

除了n很小的情况,一般地,我猜测 R(n,n) < 2^n
即50x50的关卡,步数不会超过 R(48,48) < 2^48 = 281474976710656 步

[ 本帖最后由 sokoban 于 2012-4-21 17:17 编辑 ]

使用道具 举报

Rank: 2

积分
215
帖子
64
精华
1
UID
1303898
性别
发表于 2012-4-21 17:56:39 |显示全部楼层

回复 8# 的帖子

根据“[url=http://bbs.mf8-china.com/viewthread.php?tid=30733&page=4]解法步数随关卡大小成指数增长的关卡[/url]”贴子第34楼和36楼jinyou(金优)先生的说法,我们有:


  • R(5, 5) ≥ 48 : rDrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL
  • R(5, 7) ≥ 170 : rDDDLUdrrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL
  • R(5, 9) ≥ 494 : rDDDLUdrDDLUdrrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuuuullDDRUldDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuuuurrDDLUdrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL

此外,我们还有 R(5, 2 * m + 1) ≥ R(5, 2 * m - 1) * 2.618。

由于 R(5, 2 * 2 + 1) ≥ 48 ≥ 2.6182 + 2

所以我们有以下R5定理:R(5, 2 * m + 1) ≥ 2.618m + 2




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

使用道具 举报

Rank: 2

积分
215
帖子
64
精华
1
UID
1303898
性别
发表于 2012-4-21 18:09:21 |显示全部楼层

根据R5定理,我们有:R(5, 47) = R(5, 2 * 23 + 1) ≥ 2.61823 + 2 > 2.813 x 1010

而 sokoban 兄在8楼猜测 R(48, 48) < 248 < 2.815 x 1014

看来这个猜测有点危险。

如果 R(48, 48) > R(5, 47) x 10008 的话,这个猜测就不成立了。



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

使用道具 举报

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

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

GMT+8, 2024-3-29 13:29

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部