knightofluna/sokoban-solver

推箱子解决方案 sokoban AI solver

sokoban-solver's Issues

算法优化

你好 请问可以改进死锁和剪枝的优化吗，稍微复杂的情况，5min都出不来结果，其他solve可以1min内出结果

该solver实现的heuristic function不是admissible heuristic function

即，如README描述，设定为“到目当前状态为止，所有箱子按顺序排列的位置和所有目的地按顺序排列的位置，两两间的manhatten distance总和”是可能大于真实需要步数的（从README中，A*算法在level1中不能得到最优解RurrddddlDRuuuuLLLrdRDrddlLdllUUdR也可以说明此问题）。
提供两个简单的admissible heuristic function的想法：

1. 对每个箱子，寻找距离其与最近的目标的曼哈顿距离，求和；
2. 对每个箱子和每个目标，使用曼哈顿距离构造代价矩阵，并使用Kuhn–Munkres算法求解得到最优匹配总开销；
3. 1或2中的方法，但增加人物和任一/最远（的未到位）箱子的曼哈顿距离 - 1。

怎么处理player在goal上面

主程序sokoban.py里面都没有定义player在goal上面的情况