推箱子关卡最佳答案的步数
我在“只有一个箱子的关卡的最佳答案的步数”的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)，也更值得研究。
http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=3-4-SSWqSS http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=4-4-SSVCWqSS
http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=3-5-SSS0KSSQ http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=4-5-SSSE6QASSS http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=5-5-SSSuKQgSACSSQ
http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=3-6-SSSWgKSSS http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=4-6-SSSQg6QAqSSS http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=5-6-SSSRg6QgiQAKSSS http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=6-6-SSSRgKQB6QkiQACSSS
[*]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上述结论还有很大的改进余地。
请参阅：再谈推箱子关卡最佳答案的步数 推箱子这玩意太复杂了。。。我这智商也就我小游戏上推箱子前几关了
回复 2# 的帖子
目前步数最多的关卡（箱子个数没有限制）可能暂时还是利用 Fibo 系列关卡来构造。参看此帖：(34楼 金优先生的回帖)http://bbs.mf8-china.com/viewthread.php?tid=30733&page=4#pid621511 好厉害，虽然看不懂。。
更正: R(3, 4) 的最小值
http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=5-6-SSSRg6QgiQAKSSS1楼的 R(3, 4) 不对，应该是：
R(3, 4) ≥ 13 : uURdrdLuuurDD
新的 R(3, 4) 关卡
http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=5-6-SSSXgKQgiQAKSSSR(3, 4) ≥ 21 : rrddlldRuruullDDrUruL
不知是否有更好的解答。
[ 本帖最后由 skyivben 于 2012-4-20 21:50 编辑 ] 我在“推箱子关卡最佳答案的步数”中定义了 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猜想是非常有可能成立的。
回复 7# 的帖子
除了n很小的情况，一般地，我猜测 R(n,n) < 2^n即50x50的关卡，步数不会超过 R(48,48) < 2^48 = 281474976710656 步
[ 本帖最后由 sokoban 于 2012-4-21 17:17 编辑 ]
回复 8# 的帖子
根据“解法步数随关卡大小成指数增长的关卡”贴子第34楼和36楼jinyou(金优)先生的说法，我们有：http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=7-7-bSSaSASQgAS5tCQgCSQATaSSY http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=7-9-bbSSaSSASQgAAS5ttCQgACSSQATbaSSY http://aspspider.ws/skyivben/aspx/xsbbitmap.aspx?x=7-11-bbbSSaSSSASQgAAAS5tttCQgAACSSSQATbbaSSY[*]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 编辑 ] 根据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 编辑 ]
页:
[1]
2