魔方吧·中文魔方俱乐部

标题: 也来请教算法：推箱子 [打印本页]

作者: tonylmd 时间: 2009-4-7 15:42:48 标题: 也来请教算法：推箱子

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

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

作者: tonylmd 时间: 2009-4-7 16:16:30

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

作者: kaylmu 时间: 2009-4-7 17:27:08

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

作者: aben306 时间: 2009-4-7 18:27:25

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

作者: kexin_xiao 时间: 2009-4-7 19:11:56

有这样的软件吧？

作者: 骰迷 时间: 2009-4-7 21:50:17

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

作者: tonylmd 时间: 2009-4-7 21:56:52

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

作者: zxl0714 时间: 2009-4-9 08:50:28

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

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

作者: tonylmd 时间: 2009-4-9 08:56:14

不必最难只要可以根据一定算法对难度（破解时间）进行评估并筛选就行了

作者: zxl0714 时间: 2009-4-9 09:04:42

楼上的这样不现实啊，要是能很快就能对难度进行评估，那搜索就很快了。这样强悍的估价函数不存在的，估计复杂度也是np的。要不然就可以根据这个估价函数来展开结点，瞬间解出。

作者: tonylmd 时间: 2009-4-9 09:19:17

呃…
等sokoban来讲一下“优化解法”的原理吧
貌似是根据已有解进行最简优化不和暴力破解完全相同

作者: migl 时间: 2009-4-9 10:59:13

为了解这个，让俺的计算机“高烧”15天~~~

也太疯狂了吧~~~

“烧”一天，我都不愿意。

作者: sokoban 时间: 2009-4-9 12:33:07 标题: 回复 11# 的帖子

优化解法我是从葛永先生那里了解的。

优化解法相对来说计算机比较容易实现。而且从设计关卡上来防“解法优化”也是比较困难。

作者: zxl0714 时间: 2009-4-9 21:49:02

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

作者: zxl0714 时间: 2009-4-9 21:52:35

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

作者: tonylmd 时间: 2009-4-9 22:46:43

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

作者: zhenying 时间: 2009-4-15 13:56:32

Re:6#帖
不敢苟同

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)