Recherche A*

La recherche non informée traite toutes les directions inexplorées de la même façon et gaspille donc de l’effort à développer des nœuds qui s’éloignent du but. La recherche gloutonne utilise une estimation heuristique de la distance restante mais ignore le coût déjà payé : elle peut donc s’engager sur un itinéraire d’apparence bon marché qui se révèle coûteux. A* combine les deux signaux.

Chaque nœud est noté par f(n) = g(n) + h(n), où g est le coût connu du meilleur chemin trouvé jusqu’à n et h estime le coût restant de n jusqu’à un but. Comme f est une estimation du coût total d’une solution passant par n, développer toujours le plus petit f revient à poursuivre l’itinéraire qui paraît actuellement le moins coûteux dans l’ensemble.

L’optimalité repose sur une condition que Russell et Norvig énoncent précisément : h doit être admissible, c’est-à-dire ne jamais surestimer le coût pour atteindre le but. Comme g est le coût réel engagé, une h admissible fait que f ne surestime jamais le coût réel d’une solution passant par ce nœud. Les heuristiques admissibles sont optimistes par nature, et c’est cet optimisme qui empêche A* d’écarter un itinéraire véritablement meilleur. Pour la recherche en graphe, une condition légèrement plus forte, la cohérence, est normalement requise également.

L’heuristique détermine l’efficacité plutôt que la correction. Avec h identiquement nulle, A* se réduit à la recherche à coût uniforme : elle est optimale mais explore largement. Avec une heuristique proche du coût restant réel, elle file presque directement vers le but. Des heuristiques admissibles plus fortes sont donc le principal levier de performance, et une grande part de la recherche classique porte sur leur construction.

Pour un calcul d’itinéraire sur une carte routière, g est la distance effectivement parcourue pour atteindre une ville et h la distance à vol d’oiseau de cette ville à la destination. La distance à vol d’oiseau est admissible parce qu’aucune route ne peut être plus courte que la ligne directe.

La recherche développe la ville minimisant la distance parcourue plus la distance directe restante. Une ville légèrement à l’écart de la ligne directe mais atteinte à bas coût peut être développée avant une ville plus proche de la destination mais qui a demandé un long détour.

Remplacer la distance à vol d’oiseau par quelque chose qui pourrait surestimer, disons une estimation gonflée par prudence, brise la garantie d’optimalité. A* peut alors renvoyer un itinéraire sous-optimal parce qu’elle a élagué le véritable meilleur sur la foi d’une surestimation.