KnightofLuna/sokoban-solver

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

ComradeSpark opened this issue · 0 comments

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

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