L'algorithme de recherche A* (qui se prononce A étoile, ou A star à l'anglaise) est un algorithme de recherche de chemin dans un graphe entre un nœud
initial et un nœud final tous deux donnés. De par sa
simplicité il est souvent exhibé comme un exemple typique
d'algorithme de planification, un domaine de l'intelligence artificielle.
L'algorithme A* a été créé pour que la première solution trouvée soit
l'une des meilleures, c'est pourquoi il est célèbre dans des
applications comme les jeux vidéo privilégiant le temps de calcul à
l'exactitude des résultats.
Détails
Vous trouverez plus d'informations sur Wikipedia http://fr.wikipedia.org/wiki/Algorithme_A%2A
Le programme
Le programme présenté ici met en oeuvre l'algorithme de
recherche du plus court chemin dans le cas le plus simple envisageable.
Il est possible de définir le point de départ et
d'arrivée, et de dessiner des murs (obstacles) entre ces 2
points.
La zone explorée par l'algorithme se colorie, montrant l'optimisation réalisée dans la recherche du chemin.
