|
L'algorithme A* (A-star) est un algorithme de recherche heuristique utilisé en informatique pour trouver le chemin le plus court entre deux nœuds dans un graphe. Il s'agit d'une extension de l'algorithme de Dijkstra, qui trouve le chemin le plus court mais n'utilise pas d'heuristiques.
Intuition
A* utilise des heuristiques, des informations sur le domaine problématique qui aident à guider sa recherche. Ces heuristiques sont souvent appelées heuristiques d’admissibilité ou de distance, car elles ne surestiment jamais le coût réel pour atteindre l’objectif. Dans de nombreux cas, A* trouve des solutions optimales, même si cela n’est pas toujours garanti.
Comment fonctionne A* ?
A* conserve deux ensembles de nœuds lors de sa recherche :OUVERT (Fringe) et FERMÉ
OUVERT contient tous les nœuds qui ont été générés, mais pas encore entièrement évalués. Il est classé en fonction du score F (discuté ci-dessous) de ses membres, le score F le plus bas étant placé en tête.
FERMÉ contient tous les nœuds qui ont été entièrement évalués.
L'algorithme commence par placer le nœud de départ en OUVERT, tandis que le nœud d'objectif réside initialement en FERMÉ. À chaque étape de l'algorithme, A* supprime le nœud dans OPEN avec le score F le plus bas, le développe et ajoute tous ses voisins à OPEN. Si un voisin n'est pas déjà en OUVERT ou FERMÉ, A* calcule un score G (le coût réel pour atteindre le voisin depuis le nœud de départ) et un score H (une estimation du coût pour atteindre l'objectif depuis le voisin) pour lui. , et l'ajoute à OPEN. Si un voisin est déjà en OPEN, le nouveau score G est comparé au score G actuel, et si le nouveau score G est inférieur, le voisin est mis à jour. Si un voisin est déjà en FERMÉ, le nouveau score G est comparé au score G actuel, et si le nouveau score G est inférieur, le voisin est déplacé de FERMÉ à OUVERT et mis à jour.
Résiliation
L'algorithme se termine de deux manières. Premièrement, si un voisin du nœud en cours d’expansion est l’objectif, l’algorithme renvoie le chemin vers l’objectif. Deuxièmement, si OPEN devient vide, l'algorithme se termine sans succès, indiquant qu'il n'y a pas de chemin valide entre le nœud de départ et l'objectif.
Complexité
La complexité temporelle dans le pire des cas de l’algorithme A* est exponentielle dans la taille du graphique. Cependant, en pratique, A* fonctionne bien sur de nombreux problèmes et trouve souvent des solutions optimales dans un laps de temps raisonnable.
|
