（所有棋盘开始时每个角落都有豆子）

如果我有一个这样的吃豆人棋盘

*--------------------*------------------------------------------------------------------------------------------------------------------------------------P--------------------*----------------------

要让他吃掉所有的豆子（*），最好的启发式是什么？我在使用A*搜索。我尝试过使用曼哈顿距离，但是一旦加入了墙壁，它的效果就不如广度优先搜索（BFS），因此不是最优的。我希望它在扩展的节点数少于BFS的情况下达到最优效果。

回答：

好的，我找到了一个解决方案：

（到最远角落的最大(x,y)距离）

childXY = state[0] cornersLeft = state[1]

maxDistance = 10000minDistance = 0farthestCorner = 0nearestCorner = 0for corner in cornersLeft:    if util.manhattanDistance(childXY, corner) > minDistance:        minDistance = util.manhattanDistance(childXY, corner)          farthestCorner = minDistance - min((childXY[0]-corner[0]),(childXY[1]-corner[1]))heuristic = farthestCornerprint "heuristic is: ", heuristicreturn heuristic

我的A*搜索存在一个问题，最终导致我的启发式无法正常工作的主要问题。