查看: 745946|回复: 16

也来请教算法：推箱子 [复制链接]

tonylmd

金魔

花样爱好者

Rank: 8 Rank: 8

积分: 8970
帖子: 4217
精华: 13
UID: 22473

电梯直达

1^#

发表于 2009-4-7 15:42:48 |只看该作者 |倒序浏览

这个有挑战性啊……论坛里编程好手多哈~pSpace问题？反正我是不懂……
~
什么是推箱子？
http://bbs.mf8-china.com/viewthr ... &extra=page%3D1
简单说就是：墙、箱子、目标位置、仓管员（用户）的有机组合
~
问1 暴力破解的算法如何实现？是枚举步数吗？
问2 题目应如何设置才能使暴力破解运算时长在15天以上？（常规条件下了曙光3000A不考虑哈

）
问3 能否设计一个直接生成符合上面要求的题目的软件？
~
PS.设计题目要考虑人工简化的情况暴力破解无法规定不准对原图做任何修改
也就是期望能出一个人全方位防人脑电脑暴力破解的推箱子题目生成软件了……（晕…这样的要求没有自相矛盾吧…？…）

收藏0

玩魔方玩的是心情~

小陆的个人文集

使用道具举报

tonylmd

金魔

花样爱好者

Rank: 8 Rank: 8

积分: 8970
帖子: 4217
精华: 13
UID: 22473

2^#

发表于 2009-4-7 16:16:30 |只看该作者

无厘头的想起了不可逆加密算法…
恍惚记得是跟大质数分解有关…

玩魔方玩的是心情~

小陆的个人文集

使用道具举报

kaylmu

红魔

kay

Rank: 4

积分: 2430
帖子: 2133
精华: 1
UID: 67968

3^#

发表于 2009-4-7 17:27:08 |只看该作者

完全部懂...楼主读什么呀?

使用道具举报

aben306

透魔

Rank: 6 Rank: 6

积分: 6174
帖子: 5963
精华: 0
UID: 17509
性别: 女

4^#

发表于 2009-4-7 18:27:25 |只看该作者

呵呵,这对我可是难题.不懂哦.

小魔女 QQ:835711797
我的主页

使用道具举报

kexin_xiao

银魔

小欣然的爸爸

Rank: 7 Rank: 7 Rank: 7

积分: 37843
帖子: 34374
精华: 15
UID: 16477
性别: 保密

5^#

发表于 2009-4-7 19:11:56 |只看该作者

有这样的软件吧？

天津1群11471969，2群5834223
3群62462688，4群62462702
5群70735234，6群33712046
7群12240584，8群29198783
9群62974165，欢迎加入！

使用道具举报

骰迷

红魔

All Blue

Rank: 4

积分: 1196
帖子: 999
精华: 2
UID: 38845
性别: 男

6^#

发表于 2009-4-7 21:50:17 |只看该作者

其實推箱子的活動範圍那麼小，怎麼可能把運算時間推到15天，就是最難的關卡，人試幾十次都能解出來

使用道具举报

tonylmd

金魔

花样爱好者

Rank: 8 Rank: 8

积分: 8970
帖子: 4217
精华: 13
UID: 22473

7^#

发表于 2009-4-7 21:56:52 |只看该作者

喔…补充条件：箱子数量在15~20个

玩魔方玩的是心情~

小陆的个人文集

使用道具举报

zxl0714

白魔

Rank: 1

积分: 171
帖子: 132
精华: 0
UID: 30495
性别: 保密

8^#

发表于 2009-4-9 08:50:28 |只看该作者

推箱子问题很难解的，因为这是一个np问题。只要地图大一点，箱子多一点，基本上电脑就肯定跑不出来了。。。
我说一下算法，我的想法是用IDA*算法，就是限定深度并且按估价扩展结点，其实可以只关心箱子四周的能到达的地方，可以忽略走的过程，这样就能快一些。
用IDA*算法的好处就是可以快速找到一个近似解，但并不一定是最优解。

我认为生成一个最难的推箱子地图并不现实，因为这本身就是一个np问题。

使用道具举报