了解单个目标迷宫的A*启发式算法

Question

我有一个如下的迷宫:

||||||||||||||||||||||||||||||||||||
|                                 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).

我真的想知道我在哪里出错了.我知道,贪婪的最佳头等算法可这样的表现自然,但在节点扩展的差距就是这么大,我觉得喜欢的事已经是错在这里..任何帮助,将不胜感激.如果我上面粘贴的内容在某些方面不清楚,我很乐意添加细节.

Answer 1

A* 搜索尝试找到问题的最佳可能解决方案，而贪婪最佳优先只是尝试找到任何解决方案。A* 的任务要困难得多，它必须投入大量工作来探索可能是最好的每一条路径，而贪婪的最佳优先算法只是直接选择看起来最接近目标的选项。