##  [Recherche A\*](/fr/node/58873) 

 Définition

Un algorithme de recherche best-first sur graphe qui ordonne l'expansion des nœuds par une fonction de coût f(n)=g(n)+h(n), où g(n) est le coût depuis le départ jusqu'au nœud n et h(n) est une estimation heuristique du coût de n à un but ; avec une heuristique admissible (et de préférence consistante), A* trouve des chemins de coût minimal de manière efficace.

 

 

 

 

 

 





## Principe

Principe

Prioriser les nœuds ayant le coût total estimé le plus bas (g + h) ; l'admissibilité de h (ne surestime jamais le coût réel) garantit que la première fois qu'un nœud but est retiré de la frontière il est optimal, et la consistance (monotonicité) simplifie la gestion et garantit des valeurs f non décroissantes le long des chemins.

 

 

 

 

 





## Démonstration

Démonstration

Recherche de chemin sur une grille : utiliser g(n) comme longueur du chemin parcouru et h(n) comme distance de Manhattan jusqu'à la cible. A* étend les nœuds qui semblent prometteurs selon f ; si h est la distance de Manhattan pour des déplacements orthogonaux 4-voisin, A* trouvera le plus court chemin sur la grille sans explorer toutes les cases. En robotique, A* planifie des trajets discrets sur des grilles d'occupation.

 

 

 

 

## Mauvaise application

Mauvaise application

Employer une heuristique non admissible (qui surestime) peut produire des chemins sous-optimaux ; des heuristiques trop faibles (proches de zéro) dégradent A* en algorithme de Dijkstra, entraînant trop d'expansions et un usage mémoire élevé ; ignorer les limites mémoire peut rendre A* impraticable sur grands graphes.

 

 

 

 

 





## Conséquence

Conséquence

Lorsqu'une bonne heuristique admissible existe, A* réduit fortement les expansions de nœuds par rapport à la recherche non informée et produit des chemins optimaux ; il offre aussi un cadre flexible pour des variantes (A* pondéré, IDA*) qui échangent optimalité contre vitesse ou mémoire.

 

 

 

 

## Inversion

Inversion

L'algorithme de Dijkstra correspond à A* avec h=0 (non informé) et est optimal mais peut explorer davantage ; la recherche avide best-first utilise f=h et peut être plus rapide mais n'est pas garantie optimale.

 

 

 

 

 





## Limite

Limite

Conçu pour la recherche dans des espaces d'états discrets et les problèmes de plus court chemin avec coûts d'arête non négatifs et tests d'objectif bien définis ; les problèmes continus exigent discretisation ou variantes continues spécialisées ; l'optimalité dépend des propriétés heuristiques et des hypothèses sur les coûts.

 

 

 

 

 





## Tension sémantique

Tension sémantique

Tension entre admissibilité/optimalité et vitesse pratique : les heuristiques admissibles garantissent l'optimalité mais peuvent être conservatrices ; les heuristiques pondérées ou non admissibles accélèrent la recherche mais risquent des solutions sous-optimales. Il existe aussi une tension entre consommation de mémoire (taille de la frontière) et taux d'expansion.

 

 

 

 

 





## Synthèse

Synthèse

A* combine le coût réel depuis le départ et le coût heuristique restant en un ordre unique qui, avec une heuristique admissible, produit une recherche optimale et souvent efficace ; son déploiement pratique exige d'équilibrer conception heuristique, contraintes mémoire et compromis acceptables entre rapidité et optimalité.