关于推箱子的算法

leevis

前天笔试的时候，有一道题目就是推箱子的AI，如果是一个箱子就很好解决，DSP，BSP，A*都可以，但是几个箱子互相影响的情况就比较复杂了，后来我给的答案就是使用for嵌套，基本思路就是先移动第一个箱子到合适的地方，为移动第二个箱子做准备（第1层for），接下来将第二个移动到合适的地方，为移动第三个箱子做准备（第2层for）……直到最后一个箱子，使用DSP，或者BSP，A*移动到目的地，接下来就是依次完称各层for接下来的DSP，或者BSP，A*，不知道这样的想法会不会有缺陷？
再总结一下，也就是依次移动1，2，3，4到合适位置，再4，3，2，1移动到目的地，会不会有1，2，3移动，4到目的地，还需要2，3，1调整，才可以移动3，然后1，2调整才可以移动2，最后是1，虽然直觉觉得可以通过前面的移动到合适的地点来避免，但是没有数学证明总觉得不放心，还请算法大人点播啊

lights

什么公司啊！果然bt!推箱子的复杂度主要取决于地图，
最佳顺序的复杂程度在某些地图条件下可是箱子数的n倍！
你的算法只能适合于复杂程度=箱子数的最简单地图！
你玩一个推箱子游戏就知道了！我绞尽脑汁也没想到个高效的方式！
想想遍历所有的情况，筛去推入死角和同质化情况，在面对一个小地图时也是很低效的运算。
那位仁兄有好的算法就讲讲啊，我也很想学习学习！

游戏战士

先想一下

tarkey

设计好思路，回朔可以实现，速度方面没什么好办法可以保证。

zetorchen

用动态规划

necro

地图为平面，箱子规则的话，成为棋盘移子，不需要那些复杂技术吧。

超级飞鱼

我去育碧考试的时候也有这个题目，结果。。。。郁闷了！
不过好像看到本站ftp里面有一个相关的程序，去看看吧：）
如果有高手有好一点的算法，也请不吝赐教！

fujingqiu

招个程序员还得考这种题目！这些公司一定是有病！