5. A*

5. A*

A* ajoute au meilleur d’abord le coût réellement parcouru. Il classe les états selon :

f(n) = g(n) + h(n)

• g(n) : coût réel du meilleur chemin connu de l’état initial à n;
• h(n) : estimation du coût restant de n vers le but;
• f(n) : estimation du coût total d’une solution passant par n.

5.1 Procédure

1. Placer l’état initial dans OUVERTS avec sa valeur f et son parent.
2. Choisir dans OUVERTS l’état de plus petite valeur f.
3. Le retirer de OUVERTS et le placer dans FERMÉS.
4. S’il s’agit du but, reconstruire la solution à partir des parents.
5. Sinon, générer ses enfants :
   • ignorer un enfant déjà fermé selon la procédure du cours;
   • s’il n’est pas ouvert, l’ajouter avec g, h, f et son parent;
   • s’il est déjà ouvert avec une valeur moins bonne, remplacer cette entrée par le meilleur chemin.
6. Répéter; si OUVERTS devient vide, aucun but accessible n’existe.

5.2 Admissibilité et optimalité

Une heuristique est admissible si elle ne surestime jamais le vrai coût restant. La distance à vol d’oiseau constitue un exemple classique lorsqu’un trajet réel doit au moins couvrir cette distance. Avec une telle heuristique et les conditions usuelles de l’algorithme, A* fournit une solution optimale; plusieurs solutions de même coût peuvent exister.

5.4 Variante pondérée

Le cours présente :

f(n) = (1-w)g(n) + wh(n), avec 0 ≤ w ≤ 1.

• w=0 : Dijkstra, priorité au coût déjà parcouru;
• w=1 : meilleur d’abord, priorité à l’estimation restante;
• w=0,5 : pondération équilibrée correspondant au même ordre de priorité que g+h, puisque le facteur 0,5 multiplie uniformément la somme.