Algorithme A* (A-star)
L'algorithme A* ne se contente pas de regarder le chemin parcouru ; il projette également l'effort restant. C'est un algorithme best-first search (recherche du meilleur d'abord).
- \(g(v)\) (Le coût réel) : C'est la distance exacte parcourue depuis la source jusqu'à \(v\). C'est la mémoire de l'algorithme.
- \(h(v)\) (L'heuristique) : C'est une estimation du coût restant pour atteindre la cible depuis \(v\). C'est l'intuition de l'algorithme.
- \(f(v)\) (L'espérance totale) : C'est l'estimation du coût total du chemin passant par \(v\).
- Dijkstra choisit le prochain sommet tel que \(g(v)\) soit minimal.
- A* choisit le prochain sommet tel que \(f(v)\) soit minimal.
Le rôle de l'Heuristique \(h\)
L'efficacité de A* dépend entièrement du choix de la fonction \(h\). Elle doit être rapide à calculer, car elle est appelée à chaque expansion de sommet.
Le choix de l'heuristique dépend de la liberté de mouvement dans l'espace :
- Distance Euclidienne : Utilisée dans un espace libre (vol d'oiseau).
- Distance de Manhattan : Idéale pour les grilles où l'on ne se déplace qu'horizontalement et verticalement.
- Distance de Tchebychev : Utilisée si les déplacements en diagonale sont autorisés au même coût que les déplacements cardinaux.
La condition d'optimalité : L'admissibilité
C'est le point crucial pour les examens et la mise en pratique. Pour que A* garantisse le chemin le plus court, l'heuristique \(h\) doit être admissible.
Pourquoi est-ce vital ?
- Si \(h(v)\) est trop optimiste (admissible), A* explorera prudemment.
- Si \(h(v)\) est trop pessimiste (non-admissible), l'algorithme risque de trouver un chemin "suffisamment bon" mais de passer à côté du chemin optimal car il a cru qu'un raccourci potentiel était trop coûteux.
Types d'heuristiques admissibles
Heuristique basée sur le nombre minimal d'arcs
- \(k(s)\) est le nombre minimal d'arcs séparant \(s\) de la destination,
- \(w_{min}\) est le plus petit poids d'arête du graphe.
Chaque arc coûte au moins \(w_{min}\), donc le coût réel est forcément : \(\ge k(s) \times w_{min}\). Donc, l'heuristique est admissible.
Heuristique géométrique (distance euclidienne)
Lorsque les sommets sont placés dans le plan, on peut utiliser la distance géométrique vers la destination.
La distance géométrique fournit une borne inférieure naturelle du coût restant.
Heuristique fondée sur un chemin connu
On estime le coût restant en considérant un chemin valide connu, mais pas forcément optimal, vers la destination.
Le plus court chemin réel ne peut être plus long que ce chemin connu. Donc, l'heuristique est admissible.
Déroulement de l'algorithme
L'algorithme utilise trois tableaux principaux :
- \(g[v]\) : le coût réel du chemin le plus court trouvé de la source \(s\) à \(v\).
- \(f[v]\) : l'estimation du coût total passant par \(v\) (\(g[v] + h(v)\)).
- \(\pi[v]\) : le prédécesseur de \(v\) (pour reconstruire le chemin).
Algorithme A*
Pour tout sommet v:
g[v] ← +∞
f[v] ← +∞
π[v] ← None
FinPour
g[s] ← 0
f[s] ← 0
h[s] ← heuristique(s, destination)
F ← ∅ // Liste des sommets visités/fermés
Q ← {s} // Liste des sommets à explorer/ouverts
TantQue Q ≠ ∅ Faire
u ← sommet de Q avec f[u] minimal
Si u = destination :
Arrêter (Cible atteinte, reconstruire le chemin via π)
Retirer u de Q et l'ajouter à F
Pour chaque voisin v ∉ F de u Faire
cout_provisoire ← g[u] + w(u,v)
Si v ∉ Q ou cout_provisoire < g[v] Alors
g[v] ← cout_provisoire
h[v] ← heuristique(v, destination)
f[v] ← g[v] + h[v]
π[v] ← u
Si v ∉ Q Alors
ajouter v à Q
FinSi
FinSi
FinPour
TantQueExemple : A* de A vers F
On considère le graphe suivant et on effectue l'algorithme de A* à partir du sommet \(A\) vers le sommet \(F\).
graphe = [
[(1, 10), (3, 5), (2, 12)], # A (0)
[(0, 10), (4, 11)], # B (1)
[(0, 12), (3, 6), (4, 11), (5, 8)], # C (2)
[(0, 5), (2, 6), (5, 14)], # D (3)
[(1, 11), (2, 11)], # E (4)
[(2, 8), (3, 14)] # F (5)
]Heuristique \(h(s)\) (admissible)
On choisit l'heuristique basée sur le nombre minimal d'arcs :
\[ h(s) = \text{nombre minimal d'arcs de } s \text{ à la destination} \times 1 \]
(car le plus petit poids d'arc du graphe vaut 1, donc ça ne surestime jamais).
Distances en "nombre d'arcs" vers F :
- \(h(F) = 0\)
- \(h(C) = h(D) = 1\)
- \(h(A) = h(E) = 2\)
- \(h(B) = 3\)
Étape 0 : Initialisation
| Sommets à explorer (Q) | Sommets visités (F) | ||||||
|---|---|---|---|---|---|---|---|
| Sommet | g | f | π | Sommet | g | f | π |
| A | 0 | 2 | None | ||||
| B | ∞ | ∞ | None | ||||
| C | ∞ | ∞ | None | ||||
| D | ∞ | ∞ | None | ||||
| E | ∞ | ∞ | None | ||||
| F | ∞ | ∞ | None | ||||
Étape 1 : Depuis A
On regarde les voisins directs de \(A\) : \(B\), \(C\) et \(D\). On calcule \(g\) (coût réel) et \(f = g + h\).
- B : \(g(B) = 10\). Priorité \(f(B) = 10 + h(B) = 10 + 3 = 13\).
- C : \(g(C) = 12\). Priorité \(f(C) = 12 + h(C) = 12 + 1 = 13\).
- D : \(g(D) = 5\). Priorité \(f(D) = 5 + h(D) = 5 + 1 = 6\).
| Sommets à explorer (Q) | Sommets visités (F) | ||||||
|---|---|---|---|---|---|---|---|
| Sommet | g | f | π | Sommet | g | f | π |
| B | 10 | 13 | A | A | 0 | 2 | None |
| C | 12 | 13 | A | ||||
| D | 5 | 6 | A | ||||
| E | ∞ | ∞ | None | ||||
| F | ∞ | ∞ | None | ||||
Le minimum de \(f\) entre \(B:13\), \(C:13\) et \(D:6\) est \(D\). On verrouille \(D\).
Étape 2 : Depuis D
On regarde les voisins de \(D\) : \(F\) et \(C\).
- C : \(g(C) = g(D) + 6 = 11\). \(f(C) = 11 + 1 = 12\). (On met à jour car \(12 < 13\)).
- F : \(g(F) = g(D) + 14 = 19\). \(f(F) = 19 + 0 = 19\).
| Sommets à explorer (Q) | Sommets visités (F) | ||||||
|---|---|---|---|---|---|---|---|
| Sommet | g | f | π | Sommet | g | f | π |
| B | 10 | 13 | A | A | 0 | 2 | None |
| C | 11 | 12 | D | D | 5 | 6 | A |
| E | ∞ | ∞ | None | ||||
| F | 19 | 19 | D | ||||
Le minimum dans \(Q\) est \(f(C) = 12\). On verrouille \(C\).
Étape 3 : Depuis C
On regarde les voisins de \(C\) : \(E\) et \(F\).
- E : \(g(E) = g(C) + 11 = 11 + 11 = 22\). \(f(E) = 22 + 2 = 24\).
- F : \(g(F) = g(C) + 8 = 11 + 8 = 19\). \(f(F) = 19 + 0 = 19\).
| Sommets à explorer (Q) | Sommets visités (F) | ||||||
|---|---|---|---|---|---|---|---|
| Sommet | g | f | π | Sommet | g | f | π |
| B | 10 | 13 | A | A | 0 | 2 | None |
| E | 22 | 24 | C | D | 5 | 6 | A |
| F | 19 | 19 | D | C | 11 | 12 | D |
Le minimum dans \(Q\) entre \(B : 13\) et \(F : 19\) est \(B\). On verrouille \(B\).
Étape 4 : Depuis B
Le seul voisin sortant de \(B\) est \(E\).
- E : \(g(E) = g(B) + 11 = 10 + 11 = 21\). \(f(E) = 21 + 2 = 23\).
| Sommets à explorer (Q) | Sommets visités (F) | ||||||
|---|---|---|---|---|---|---|---|
| Sommet | g | f | π | Sommet | g | f | π |
| E | 21 | 23 | B | A | 0 | 2 | None |
| F | 19 | 19 | D | D | 5 | 6 | A |
| C | 11 | 12 | D | ||||
| B | 10 | 13 | A | ||||
Le minimum est désormais \(F\) avec \(f = 19\). \(F\) est le nœud cible, la recherche est donc terminée.
Résultat final
| Sommet | g | f | π |
|---|---|---|---|
| A | 0 | 2 | None |
| D | 5 | 6 | A |
| C | 11 | 12 | D |
| B | 10 | 13 | A |
| F | 19 | 19 | D |
Résultats
- Chemin optimal : \(A \rightarrow D \rightarrow F\)
- Coût réel \(g(F)\) : \(5 + 14 = 19\)
Implémentation Python
import heapq
def a_star(g_adj, h, s, cible):
n = len(g_adj)
# Q : File de priorité (f_score, u)
Q = [(h[s], s)]
# Initialisation des coûts réels g à l'infini
g_score = [float('inf')] * n
g_score[s] = 0
# Dictionnaire des parents pour la reconstruction (initialisé à None)
parents = [None] * n
# F : Liste fermée (sommets verrouillés)
F = set()
while Q:
# Extraire le sommet u ayant le f_score minimal
f_u, u = heapq.heappop(Q)
# SI CIBLE ATTEINTE : Déclencher la reconstruction
if u == cible:
return reconstruire_chemin(parents, cible), g_score[cible]
if u in F:
continue
F.add(u)
# Exploration des voisins
for v, poids in g_adj[u]:
if v in F:
continue
# g_score provisoire pour le voisin v via le sommet u
g_provisoire = g_score[u] + poids
if g_provisoire < g_score[v]:
# On a trouvé un meilleur chemin vers v !
parents[v] = u
g_score[v] = g_provisoire
f_score = g_provisoire + h[v]
heapq.heappush(Q, (f_score, v))
return None, float('inf')
def reconstruire_chemin(parents, actuel):
"""Reconstruit le chemin depuis la source jusqu'à la cible"""
chemin = []
while actuel is not None:
chemin.append(actuel)
actuel = parents[actuel]
return chemin[::-1] # On inverse la liste pour avoir l'ordre Départ -> Cible
# Exemple d'utilisation
graphe = [
[(1, 10), (3, 5), (2, 12)], # A (0)
[(0, 10), (4, 11)], # B (1)
[(0, 12), (3, 6), (4, 11), (5, 8)], # C (2)
[(0, 5), (2, 6), (5, 14)], # D (3)
[(1, 11), (2, 11)], # E (4)
[(2, 8), (3, 14)] # F (5)
]
# Heuristique : nombre minimal d'arcs vers F
h = [2, 3, 1, 1, 2, 0]
chemin_indices, cout_total = a_star(graphe, h, 0, 5)
print(f'Chemin de A(0) à F(5) : {chemin_indices}')
print(f"Le coût total : {cout_total}")Chemin de A(0) à F(5) : [0, 3, 5] Le coût total : 19
Comparaison A* vs Dijkstra
| Critère | Dijkstra | A* |
|---|---|---|
| Fonction de priorité | \(g(v)\) (coût réel depuis la source) | \(f(v) = g(v) + h(v)\) |
| Connaissance de la cible | Aucune (exploration aveugle) | Utilise une heuristique vers la cible |
| Optimalité | Toujours optimal (poids positifs) | Optimal si \(h\) est admissible |
| Cas particulier | Cas particulier de A* avec \(h=0\) | Généralisation de Dijkstra |
- Complexité temporelle : \(O((|S| + |A|) \log |S|)\) dans le pire cas (avec une file de priorité)
- Complexité spatiale : \(O(|S|)\) pour stocker \(g\), \(f\) et les parents
- Efficacité pratique : Bien meilleure que Dijkstra si l'heuristique est bien choisie
- \(h = 0\) : A* devient Dijkstra
- \(h\) non admissible : A* peut trouver une solution sous-optimale mais plus rapidement
- \(h\) parfaite : \(h(v) = d^*(v)\), A* explore uniquement le chemin optimal
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.