寻找最佳启发式算法、A* 搜索、pacman

Question

（所有图板的每个角都以点开头）

如果我有这样的吃豆人板

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

让他吃掉所有点 (*) 的最佳试探法是什么？我正在使用 A* 搜索。我试过使用曼哈顿距离，但是一旦将墙壁扔进混合物中，它就不会达到与 BFS 相同的结果，因此不是最优的。我正在寻找它是最佳的，同时比 BFS 扩展更少的节点。

Answer 1

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

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

childXY = 州[0] cornersLeft = 状态[1]

maxDistance = 10000
minDistance = 0
farthestCorner = 0
nearestCorner = 0


for 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 = farthestCorner

print "heuristic is: ", heuristic
return heuristic

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

寻找最佳启发式算法、A* 搜索、pacman

Looking for optimal heuristic, A* search, pacman

search

artificial-intelligence