Разбиране на A* евристика за лабиринт с една цел

Имам лабиринт като следния:

||||||||||||||||||||||||||||||||||||
|                                 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, което имам, намира неоптимален път (цена: 74) само в 160 разширения.

Наистина се опитвам да разбера къде греша тук. Осъзнавам, че алгоритмите на Greedy Best First могат да се държат по този начин естествено, но разликата в разширенията на възлите е толкова голяма, че чувствам, че нещо трябва да е грешно тук.. Всяка помощ ще бъде оценена. Ще се радвам да добавя подробности, ако това, което съм поставил по-горе, е неясно по някакъв начин.