Python Pacman启发式算法不一致

Question

作为人工智能作业的一部分，我必须解决加州大学伯克利分校的Pacman项目。您可以在这里的search/searchAgents.py:source code下找到（已经解决的）源代码

我的问题是，在foodheuristic中，需要一种一致的启发式方法来寻找所有食物。我已经发现，如果我在迷宫中从吃豆人的位置到最远处的食物的真实距离，我有足够的启发。但我的想法是，如果我得到两个食物点之间的最远距离，并将pacman位置和两个找到的食物点之一的最近点之间的距离加在一起，我会有一个更好的解决方案

比如：(x1,y1)和(x2,y2)在迷宫中它们之间的距离最大。这意味着，无论发生什么，吃豆人至少要走这么远。但如果吃豆人没有直接在两点中的一点上产卵，他还必须至少在当前位置和两点中最近点之间移动一段距离。但是当我这样做的时候，我得到了一个警告，我的启发式是不可接受的，甚至是不一致的。这对我来说毫无意义

我的代码还通过使用列表记录了两个食物点对同时具有最大距离的可能性。因此，代码可以稍后确定所有对中到pacman位置的最小距离

守则：

mazeDistance(x,y,default)在点x和y之间的迷宫中找到最低的实际路径

position, foodGrid = state

foodList = foodGrid.asList()#is a list that contains all food positions
if not foodList:
    return 0
elif len(foodList) == 1:
    return mazeDistance(position, foodList[0], problem.startingGameState)
distancesBetweenFood = []
for foodNode in foodList:
    foodList2 = foodList
    foodList2.remove(foodNode)
    for foodNode2 in foodList2:
        distancesBetweenFood.append([mazeDistance(foodNode, foodNode2, problem.startingGameState), [foodNode, foodNode2]])
highestDistanceBetweenFood = max(distancesBetweenFood)[0]
highestDistanceNodes = []
for dist,nodes in distancesBetweenFood:
    if dist == highestDistanceBetweenFood:
        highestDistanceNodes.append(nodes)
lowestDistanceBetweenFoodAndPacman = 9999999#should be infinite
for nodes in highestDistanceNodes:
    manhattanDists = []
    manhattanDist = 0
    for n in nodes:
        manhattanDists.append(mazeDistance(position, n, problem.startingGameState))
    manhattanDist = min(manhattanDists)
    if manhattanDist < lowestDistanceBetweenFoodAndPacman:
        lowestDistanceBetweenFoodAndPacman = manhattanDist
sumDist = lowestDistanceBetweenFoodAndPacman + highestDistanceBetweenFood
return sumDist