也来请教算法：推箱子

zxl0714

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

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

zxl0714

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

zxl0714

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

zxl0714

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