Algorithme A*
A* est un ensemble d'étapes (un algorithme) que les ordinateurs peuvent utiliser pour trouver comment se rendre rapidement entre deux endroits. Si vous avez une liste d'endroits et que vous avez du mal à vous rendre d'un endroit à l'autre, l'utilisation de A* peut vous indiquer rapidement le chemin le plus rapide. Il est lié à l'algorithme de Dijkstra, mais il fait des suppositions intelligentes pour ne pas passer autant de temps à essayer des chemins lents. C'est une bonne série d'étapes si vous voulez seulement le chemin entre deux endroits. Si vous demandez plusieurs chemins à partir de la même carte, il existe des chemins plus rapides, qui trouvent toutes les réponses en même temps, comme l'algorithme de Floyd-Warshall. A* ne fonctionnera pas si vous voulez visiter plusieurs endroits au cours d'un même voyage (le problème du voyageur de commerce).
Les étapes
A* a d'abord besoin d'une liste de tous les endroits où vous pouvez vous rendre, puis il a besoin d'une liste de la distance entre chacun d'eux. Il vous indiquera ensuite le chemin le plus rapide pour vous rendre du lieu A au lieu Z.
Par exemple, nous dirons que A est relié aux lieux B et C, et que B et C sont tous deux reliés à D et E. D et E sont tous deux reliés à Z. Il y a 4 façons possibles de passer de A à Z. Vous pouvez aller A-B-D-Z, A-C-D-Z, A-B-E-Z ou A-C-E-Z. Un ordinateur qui utilise A* examine d'abord la difficulté de se rendre de A à B et de A à C. C'est le "coût" de ces endroits. Le coût d'un lieu signifie combien il est difficile de se rendre de A à ce lieu. Après avoir noté les deux coûts, l'ordinateur examine la difficulté à se rendre de B à D et l'ajoute au coût de B. Il l'inscrit comme le coût de D. Ensuite, l'ordinateur examine la difficulté à se rendre de C à D et ajoute ce coût au coût de C. Ce coût est différent pour D, et s'il est inférieur à celui qu'il a déjà, il remplacera l'ancien. L'ordinateur ne veut connaître que le meilleur chemin, il ignore donc celui qui coûte le plus cher. Il ne se souviendra que de l'un des chemins A-B-D et A-C-D, celui qui est le plus rapide.
L'ordinateur s'allume et trouve le moyen le plus rapide de se rendre à E. Enfin, il va de D à Z, et trouve un coût, et de E à Z et trouve un coût. Il obtient un coût final pour Z, et c'est le plus petit coût qu'il peut obtenir. Maintenant, l'ordinateur sait quel est le chemin le plus rapide et il a la réponse. L'ordinateur peut faire une série d'étapes similaires, mais avec beaucoup plus d'endroits. À chaque fois, il examinera l'endroit le plus proche de A et additionnera les coûts des voisins de cet endroit.
Les gens appellent la série d'étapes ci-dessus l'algorithme de Dijkstra. L'algorithme de Dijkstra peut être lent, parce qu'il examine de nombreux endroits qui pourraient être dans la mauvaise direction à partir de Z. Si vous demandez à l'ordinateur comment se rendre d'une ville à une autre proche, l'algorithme de Dijkstra pourrait finir par chercher dans un autre état.
A* résout ce problème. A* vous permet d'indiquer à l'ordinateur une estimation de la distance qui le sépare de chaque endroit jusqu'à la fin. L'ordinateur peut utiliser cette estimation pour déterminer approximativement la distance à parcourir entre un certain endroit et Z. Au lieu de se contenter de choisir l'endroit le plus proche de A, il examinera celui qui aura probablement le total le plus faible. Il trouve ce total en ajoutant le coût à la distance restante prévue. De cette façon, il ne peut regarder que dans la direction où les choses s'amélioreront probablement. Ce n'est pas grave si la supposition n'est pas parfaite, mais même une simple mauvaise supposition peut faire avancer le programme beaucoup plus vite. Si vous essayez de trouver un chemin entre deux endroits dans le monde réel, une bonne supposition est juste la distance entre eux en ligne droite. Le chemin réel sur les routes sera plus long, mais cela permet au programme de le deviner, et il n'ira pas dans la mauvaise direction.
En littérature mathématique ou informatique, cette supposition est souvent une fonction du lieu, et on l'appelle heuristique. Chaque lieu est un sommet, et chaque chemin entre deux lieux est une arête. Ce sont des mots de la théorie des graphes.
