我有一个如下的迷宫：
||||||||||||||||||||||||||||||||||||
| P|
| ||||||||||||||||||||||| |||||||| |
| || | | ||||||| || |
| || | | | | |||| ||||||||| || |||||
| || | | | | || || |
| || | | | | | |||| ||| |||||| |
| | | | | | || |||||||| |
| || | | |||||||| || || |||||
| || | || ||||||||| || |
| |||||| ||||||| || |||||| |
|||||| | |||| || | |
| |||||| ||||| | || || |||||
| |||||| | ||||| || |
| |||||| ||||||||||| || || |
|||||||||| |||||| |
|+ |||||||||||||||| |
||||||||||||||||||||||||||||||||||||
目标是让P找到+，其子目标是
+的路径成本最低（1跳=成本+ 1）我试图理解为什么我的A *启发式表现比我对Greedy 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
A *搜索尝试找到问题的最佳解决方案，而贪婪的最佳 - 首先只是尝试找到任何解决方案。 A *有一个非常艰巨的任务，它必须投入大量的工作来探索可能是最好的每一条路径，而贪婪的最佳优先算法直接用于看起来最接近目标的选项。
由于这还没有得到解决，即使OP问的错误可以通过Fezvez's answer解决，我觉得我需要问这个问题，也许可以回答错误以及为什么Fezvez的答案可以解决它：你检查了吗？使用A *算法的所有节点的启发式值并注意到奇怪的东西？他们都不平等吗？因为尽管您的启发式算法对于最佳优先算法是正确的，但它并不直接适合您的A *算法。我在java中创建了一个类似的项目，我遇到了这个问题，这就是我在这里问的原因。例如，假设您有以下兴趣点：
而且，如果我没有弄错的话，对于迷宫中的所有要点都是如此。现在，考虑到A *算法通常像具有启发式（和路径成本）的广度优先算法一样实现，因为你的启发式总是给你相同的总数（F = h + g），它实际上变成了广度优先算法也为您提供了最佳解决方案，但实际上总是比A *通常要慢。现在正如Fezvez所建议的那样，给你的启发式赋予权重可能只是混合了两个世界中的最佳（最好的第一和广度优先），并且看起来像上面给出的点：