魔方吧·中文魔方俱乐部

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

只有一个箱子的关卡的最佳答案的步数 [复制链接]

Rank: 2

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

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






[ 本帖最后由 skyivben 于 2012-4-19 21:23 编辑 ]
已有 3 人评分经验 收起 理由
anian + 10 很好的想法!
Cielo + 10 厉害!
sokoban + 20 原创的研究

总评分: 经验 + 40   查看全部评分

Rank: 7Rank: 7Rank: 7

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

论坛建设奖 八年元老

发表于 2012-4-15 18:44:09 |显示全部楼层

回复 1# 的帖子

非常感谢银河兄提出的思路和猜想。

若银河兄的猜想是对的,25 x 25 时,最佳答案的最大值已超过 41,943,040,即B(23, 23),这已经远远大于100, 000.
那么50 x 50 就不是大一点点了。如果理论值真的这么大,按道理找到一个具体的步数大于100,000的关卡并给出 xsb 格式应该是很有可能的。

另外,银河兄让我发现我的悬赏贴有一处表述不严谨,就是关卡还必须可解(否则步数就是无穷大了),我在原帖没有强调这一点。

使用道具 举报

Rank: 2

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

S(3, 6) 的最小值从 23 改进为 25


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

使用道具 举报

Rank: 2

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

回复 2# 的帖子

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

使用道具 举报

Rank: 7Rank: 7Rank: 7

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

论坛建设奖 八年元老

发表于 2012-4-15 19:24:08 |显示全部楼层
补充一个信息,已知 S(48,48) >=  99893  (即加上墙后50 x 50) 的关卡。

使用道具 举报

Rank: 2

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

回复 2# 的帖子

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

使用道具 举报

Rank: 2

积分
215
帖子
64
精华
1
UID
1303898
性别
发表于 2012-4-15 19:37:33 |显示全部楼层
非常感谢 Cielo 兄和 sokoban 兄的评分和鼓励。

使用道具 举报

Rank: 2

积分
215
帖子
64
精华
1
UID
1303898
性别
发表于 2012-4-15 20:00:58 |显示全部楼层
如果我们定义一个函数 T(n) = S(n, n),那么,如果有一个富翁给出一个悬赏:
在 2099-12-31 之前求出 T(123456789) 的值并证明该值的正确性的个人和单位,奖励十亿元人民币。
那么,这笔奖金非常可能发不出去。

使用道具 举报

Rank: 7Rank: 7Rank: 7

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

论坛建设奖 八年元老

发表于 2012-4-15 21:29:21 |显示全部楼层

回复 8# 的帖子

的确,我觉得这个 T(48) 都已经很困难了。

使用道具 举报

Rank: 2

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

S(3, 5) 的最小值目前还是 15。


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

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

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

使用道具 举报

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

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

GMT+8, 2024-3-29 14:36

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部