On a déjà au préalable évoqué dans un blog précédant un algorithme de recherche très connu qu’est celui de Dijkstra. On avait évoqué l’importance des algorithmes de recherche, ça permet principalement pour les logiciels de navigation comme titre d’exemple, de trouver d’une façon méthodique le plus court chemin à partir de votre position actuelle dans une carte vers une destination donnée. L’algorithme évoqué dans la vidéo en bas de la chaîne YouTube Computerphile est tout aussi important, C’est l’algorithme A* et représente une réelle amélioration de l’algorithme de Dijkstra.
Lorsque nous avons décrit précédemment l’algorithme de Dijkstra, ça nous a sauté aux yeux combien l’algorithme était si intuitif. En prenant un papier et un crayon, et avec un peu de chance il est possible redécouvrir l’algorithme par soi-même. L’hypothèse de départ est que vous avez une carte de plusieurs villes interconnectées par des routes avec des distances différentes, le but est de trouver le plus court chemin d’une ville de départ vers une ville d’arrivée. Intuitivement, on va commencer par la ville de départ avec une distance de 0, et explorer les voisins directs de cette ville tout en avantageant la ville la plus proche. Algorithmiquement, ça va être une file qui contient la liste ordonnée des villes intermédiaires avec leurs distances à la ville de départ. Ce même processus l’exploration va se répéter pour la tête de file, donc la ville la plus proche. Et continuez au fur et à mesure avec les autres villes jusqu’à y arriver à la ville de destination. Bien sûr dès qu’on termine l’exploration d’une ville en doit la supprimer de la liste, puisque c’était au préalable la ville la plus proche et c’est impossible de trouver dans la liste des villes suivantes un chemin plus cours. Il faut aussi entre-temps mettre à jour les distances des villes anciennement explorées si un nouveau chemin plus court est découvert.
L’algorithme A* représente une extension de l’algorithme de Dijkstra. Il va utiliser ce qu’on appelle en mathématiques une heuristique pour améliorer l’algorithme de Dijkstra. L’heuristique est une amélioration intelligente de l’algorithme de Dijkstra en le poussant plus rapidement vers la destination, et en lui évitant de faire l’exploration de la totalité des courts chemins. Cette amélioration est aussi si intuitive que l’algorithme de Dijkstra lui-même. Il a suffi de modifier l’algorithme non plus d’ordonner la liste des villes par le plus court chemin, mais par l’addition du plus court chemin avec la distance directe (ou à vol d’oiseau) de la ville vers la destination. Ainsi les villes les plus loin de la destination vont être pénalisées et les villes les plus proches vont être avantagées. On peut voir sur la vidéo en haut de la comparaison entre l’algorithme Dijkstra et l’algorithme A*, et comment l’algorithme de Dijkstra fait l’exploration en largeur et le A* étend son exploration vers la destination. Contrairement à l’algorithme de Dijkstra, l’algorithme A* ne garantit pas le plus court chemin.
L’algorithme A* étoile n’est pas aussi précis que l’algorithme de Dijkstra, mais il a l’avantage d’être beaucoup plus rapide. Ce qui le rend un candidat idéal pour les applications temps réel, où le temps de réponse doit être rapide ou borné. C’est particulièrement vrai pour les jeux vidéo avec une vue de haut, où il faut cliquer sur la souris et laisser le caractère trouver son propre chemin sur le terrain. Ça concerne principalement les jeux de stratégie RTS et les jeux de rôle RPG isométrique. L’algorithme assurant le chemin du caractère vers sa destination est généralement appelé Path-Finder. Vous pouvez voir par exemple sur l’image en haut, l’algorithme A* utilisé comme Path-Finder dans le très célèbre jeu de stratégie StarCraft. D’autres algorithmes plus modernes et plus efficaces sont utilisés comme Path-Finder dans les jeux modernes. L’algorithme A* est aussi utilisé en intelligence artificielle pour la résolution des labyrinthes, du rubik’s cube, ou le puzzle du Taquin, et beaucoup bien d’autres.