查看: 746718|回复: 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

玩魔方玩的是心情~

小陆的个人文集

使用道具举报

zhenying

蓝魔

Rank: 2

积分: 579
帖子: 187
精华: 0
UID: 86525
性别: 保密

17^#

发表于 2009-4-15 13:56:32 |只看该作者

Re:6#帖
不敢苟同

使用道具举报

tonylmd

金魔

花样爱好者

Rank: 8 Rank: 8

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

16^#

发表于 2009-4-9 22:46:43 |只看该作者

哈哈……假如果真如你说的估价算法不可实现那么就确实如此 1#最后的括号里也说了

玩魔方玩的是心情~

小陆的个人文集

使用道具举报

zxl0714

白魔

Rank: 1

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

15^#

发表于 2009-4-9 21:52:35 |只看该作者

要创造一个防人又防电脑的地图，确又要保证他有解。。。。。这不是很矛盾么。

使用道具举报

zxl0714

白魔

Rank: 1

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

14^#

发表于 2009-4-9 21:49:02 |只看该作者

我又想了想，这个真的是太难了。推箱子本身就是一个np问题，防“解法优化”也一定是一个np问题，如过我们能快速的找到防“解法优化”的方法，那么我么就可以逆向利用这个，快速找到解法。这样的“解法优化”算法可以扩展到任何一个np问题里，很难想象啊。
还有一点就是要确保这个有解，这又是个np问题。。。。。。。

使用道具举报