J'essayais de comprendre pourquoi l'heuristique utilisée dans la recherche d'arbre A * doit être admissible si A * doit être optimal. Par recherche d'arbre, je veux dire qu'il n'y a pas d'ensemble exploré maintenu par l'algorithme. En même temps, j'ai rencontré la question suivante: Est-ce que A * fonctionne pour les poids de bord négatifs?L'algorithme A * fonctionne-t-il avec des poids de bord négatifs?
L'algorithme A * est essentiellement Dijkstra’s algorithm avec heuristiques. Et l'algorithme de Dijkstra ne fonctionne pas avec les poids de bord négatifs. Donc A * ne fonctionnera pas avec des poids de bords négatifs non plus.
Si vous cherchez un algorithme qui fonctionne avec des poids de bord négatifs, jetez un oeil à the Bellman-Ford algorithm (mais il n'utilise pas d'heuristique).
Cet excellent article sur ce Dijkstra peut se révéler utile et fournit un bel exemple sur les bords négatifs ...
doea A * travailler avec des arêtes négatives s'il n'y a pas de cycles négatifs? – TimeToCodeTheRoad
@TimeToCodeTheRoad: Non. – Gumbo