Algorithme A* ("A-étoile" ou "A-star" en anglais)

Description de l’algorithme

Entrée :

• Un graphe pondéré (les arrêtes ont des poids)
• Un sommet initial
• Un sommet objectif
• Une fonction heuristique $h(n)$

Sortie :
Le plus court chemin entre le sommet initial et le sommet objectif

Idée principale

L’algorithme A* est une amélioration de Dijkstra.

Au lieu de choisir simplement le sommet avec la plus petite distance connue, on choisit le sommet qui minimise :

où :

• $g(n)$ = distance connue du départ jusqu’au sommet $n$ (ça, c'est comme dans Dijkstra)
• $h(n)$ = estimation du coût restant jusqu’à l’objectif (ça, c'est l'heuristique)
• $f(n)$ = estimation du coût total du chemin passant par $n$ (ça, c'est la somme)

Dijkstra est un cas particulier de A* avec $h(n) = 0$.

Condition importante

Pour que A* garantisse un plus court chemin, l’heuristique doit être :

• Admissible :

Un exemple classique est la distance à vol d’oiseau pour un GPS :

• $h(x)$ c'est la distance à vol d'oiseau
• On a bien $h(x) \leq \text{plus petite distance en voiture}$

L'algorithme

Initialisation

• $g(\text{départ}) = 0$
• $f(\text{départ}) = h(\text{départ})$
• Comme dans Dijkstra, tous les autres sommets ont :

On crée :

• Une liste des sommets à explorer (souvent appelée futurs_sommets)
• Une liste des sommets visités (souvent appelée deja_visite)

À chaque étape

1. On choisit dans la liste ouverte le sommet avec le plus petit $f(n) = g(n) + h(n)$
2. S’il s’agit du but → on s’arrête
3. Sinon :
   • On l’enlève de futurs_sommets
   • On l’ajoute à deja_visite
   • Pour chacun de ses voisins :
     • On calcule : $g_{\text{nouveau}} = g(\text{courant}) + \text{coût}(\text{courant}, \text{voisin})$
     • Si cette nouvelle distance est meilleure :
       • On met à jour $g(\text{voisin})$
       • On mémorise le parent (pour reconstruire le chemin)
       • On ajoute le voisin à futurs_sommets

Remarques

Comparaison avec Dijkstra

Complexité

Dans le pire cas :

où $b$ est le nombre maximal d'arrêtes sortantes d'un point et $d$ est le nombre d'arrêtes reliant le sommet initial du sommet final.

Mais en pratique, A* est beaucoup plus rapide si l’heuristique est bonne.

Code en Python

def a_etoile(matrice, depart, arrivee, heuristique):
    n = len(matrice)
    
    g = [float("inf")] * n
    f = [float("inf")] * n
    parent = [None] * n
    
    g[depart] = 0
    f[depart] = heuristique[depart]
    
    futurs_sommets = [(f[depart], depart)]
    
    deja_visite = set() # C'est une liste sans répétitions
    
    while futurs_sommets:
        courant = futurs_sommets.pop()
        
        if courant == arrivee:
            break
        
        if courant in deja_visite:
            continue
            
        deja_visite.add(courant)
        
        for voisin in range(n):
            if matrice[courant][voisin] != float("inf"):
                
                nouveau_g = g[courant] + matrice[courant][voisin]
                
                if nouveau_g < g[voisin]:
                    g[voisin] = nouveau_g
                    f[voisin] = g[voisin] + heuristique[voisin]
                    parent[voisin] = courant
                    
                    futurs_sommets.append((f[voisin], voisin))
    
    # Reconstruction du chemin
    chemin = []
    sommet = arrivee
    while sommet is not None:
        chemin.append(sommet)
        sommet = parent[sommet]
    
    chemin.reverse()
    
    return chemin, g[arrivee]