Algorithme de A*

L’algorithme de A* a était élaboré par le chercheur en intelligence artificielle Nils Nilsson en 1968 alors que ce dernier travailler sur un robot qui devait se déplacer dans une pièce avec des obstacles. Pour ce faire il avait créé un algorithme appelé A1 qui était une version plus rapide de l’algorithme de Dijkstra. L’algorithme a ensuite était amélioré par Bertram Raphael donnant lieu à A2 qui lui-même a était amélioré par Peter E. Hart afin de donner A*.

L’algorithme de A* est donc un algorithme qui essaye de trouver le chemin le plus court dans un graphe et qui a pour avantage d’être très peu gourmand en ressources. L’algorithme va ajouter tous les sommets voisins du point où il se trouve dans un tableau open(). L’algorithme va ainsi visiter les sommets d’open dont le chemin est le plus court (Le coût le plus faible) vers la destination. Les sommets visitées ou comportant un obstacle seront alors ajouté dans un tableau closed() jusqu’à que l’algorithme arrive au sommet de destination. A* est donc un algorithme parfaitement adapté dans le cadre d’une intelligence artificielle, il permet de rapidement prendre des décisions en utilisant peux de ressources et est également facile à implémenter en informatique.

Exemple

En violet les sommets visités closed(), en vert les sommets a explorer open() et en rouge la destination à atteindre.

Etape 1