L'algorithme de Dijkstra peut-il surpasser une étoile, en termes de sommets vérifiés?

Question

Je sais que l'algorithme de Dijkstra peut être considéré comme un cas spécifique d'une étoile, lorsque l'estimation heuristique utilisée retourne simplement 0, donc je sais qu'une étoile avec cette heuristique spécifique ne peut pas vérifier plus de sommets que l'algorithme de Dijkstra. Ce que je demande, c'est ce qui suit. Compte tenu d'un algorithme d'étoile avec une heuristique qui n'est pas l'heuristique retour 0, pourrait-il vérifier plus de sommets que l'algorithme de Dijkstra?

Mon intuition est oui, et je vais montrer pourquoi. Considérez la figure en dessous, dans laquelle nous considérons une grande quantité de points discrets dans ce plan, représentant les sommets du graphique et connectant les arcs avec le coût 1 entre tous les points adjacents, créant un graphique de grille. Supposons que l'heuristique utilisée par une étoile soit la distance euclidienne, et supposons que de nombreux murs incurvés comme ceux que j'ai dessinés existent au milieu existent de cette manière, pas seulement les trois que j'ai dessinés. Une étoile dans cette situation serait "trompée" pour aller entre les murs, car l'heuristique le guiderait près du point, seulement pour découvrir que c'est une impasse (ou un optimum local quelconque si vous voulez), et Cela se produirait autant de fois qu'il y a des murs. Dijkstra ne serait pas trompé de cette façon. Le seul problème avec mon exemple ici, c'est que Dijkstra ne pas surpasser une étoile ici. Alors, mon intuition est-elle erronée, ou fait-elle des instances plus intelligentes que celle-ci dans laquelle Dijkstra peut en fait surpasser une étoile en termes de sommets vérifiés?