python - 了解单目标迷宫的A *启发式

我有一个类似以下的迷宫:

||||||||||||||||||||||||||||||||||||
|                                 P|
| ||||||||||||||||||||||| |||||||| |
| ||   |   |      |||||||   ||     |
| || | | | | |||| ||||||||| || |||||
| || | | | |             || ||     |
| || | | | | | ||||  |||    |||||| |
| |  | | |   |    || ||||||||      |
| || | | |||||||| ||        || |||||
| || |   ||       ||||||||| ||     |
|    |||||| |||||||      || |||||| |
||||||      |       |||| || |      |
|      |||||| ||||| |    || || |||||
| ||||||      |       ||||| ||     |
|        |||||| ||||||||||| ||  || |
||||||||||                  |||||| |
|+         ||||||||||||||||        |
||||||||||||||||||||||||||||||||||||

目标是让P查找+，其子目标为

到+的路径是成本最低的(1跳= cost + 1)

搜索到的单元格数量(扩展的节点)最小化

我试图理解为什么我的A *启发式方法的性能要比贪婪Best First的实现方案差很多。这是每个代码的两位:

#Greedy Best First -- Manhattan Distance
self.heuristic = abs(goalNodeXY[1] - self.xy[1]) + abs(goalNodeXY[0] - self.xy[0])

#A* -- Manhattan Distance + Path Cost from 'startNode' to 'currentNode'
return abs(goalNodeXY[1] - self.xy[1]) + abs(goalNodeXY[0] - self.xy[0]) + self.costFromStart

在这两种算法中，我都使用heapq，它基于启发式值进行优先级排序。两者的主要搜索循环是相同的:

theFrontier = []
heapq.heappush(theFrontier, (stateNode.heuristic, stateNode)) #populate frontier with 'start copy' as only available Node

#while !goal and frontier !empty
while not GOAL_STATE and theFrontier:
    stateNode = heapq.heappop(theFrontier)[1] #heappop returns tuple of (weighted-idx, data)
    CHECKED_NODES.append(stateNode.xy)
    while stateNode.moves and not GOAL_STATE:
        EXPANDED_NODES += 1
        moveDirection = heapq.heappop(stateNode.moves)[1]

        nextNode = Node()
        nextNode.setParent(stateNode)
        #this makes a call to setHeuristic
        nextNode.setLocation((stateNode.xy[0] + moveDirection[0], stateNode.xy[1] + moveDirection[1]))
        if nextNode.xy not in CHECKED_NODES and not isInFrontier(nextNode):
            if nextNode.checkGoal(): break
            nextNode.populateMoves()
            heapq.heappush(theFrontier, (nextNode.heuristic,nextNode))

现在我们来解决这个问题。尽管A *找到了最佳路径，但这样做非常昂贵。为了找到cost:68的最佳路径，它会扩展(导航和搜索)452个节点来这样做。

虽然使用贪婪最佳(Greedy Best)的实现方式，但在160个扩展中却发现了次优路径(成本:74)。

我真的是想了解我在哪里出问题了。我意识到Greedy Best First算法可以自然地表现出来，但是节点扩展的间隙是如此之大，以至于我觉得这里一定有问题。任何帮助将不胜感激。如果我上面粘贴的内容在某种程度上不清楚，我很乐意添加详细信息。

最佳答案

A *提供问题的最佳答案，贪婪的最佳优先搜索提供任何解决方案。

预计A *必须做更多的工作。

如果您希望A *的变化不再是最优的，但是可以更快地返回解决方案，则可以查看加权的A *。它仅包含对试探法赋予权重(权重> 1)。在实践中，它为您带来了巨大的性能提升

例如，您可以尝试这样:

return 2*(abs(goalNodeXY[1] - self.xy[1]) + abs(goalNodeXY[0] - self.xy[0])) + self.costFromStart