Un pas en avant de l’algorithme de Dijkstra est A * (lire: « une étoile”). En termes de recherche de chemin, l’algorithme de Dijkstra voudra essayer chaque chemin et chaque sommet pour trouver le chemin le plus court entre son point de départ et sa destination, alors que A * a un attribut supplémentaire, une heuristique, qui devrait lui permettre de trouver le chemin le plus court sans avoir besoin de vérifier chaque chemin et sommet. Chaque algorithme a ses cas d’utilisation, mais en général, Dijkstra et A * peuvent trouver le chemin le plus court, mais A * le fera plus rapidement.

Je recommande d’en savoir un peu plus sur l’algorithme de Dijkstra avant d’entrer dans cet article, car il y a beaucoup de points de comparaison. Ou mieux encore, lisez mon dernier article sur le sujet ! https://medium.com/swlh/pathfinding-dijkstras-algorithm-65e71c346629

Je vais devoir configurer quelques éléments pour mes exemples, en plus de donner une définition de ce qu’est une heuristique. Pour commencer, permettez-moi de vous montrer le type de graphique que je souhaite utiliser pour mes exemples.

C’est un peu abstrait, mais je veux utiliser un tableau à carreaux comme graphique, et je veux permettre le mouvement entre ses carrés. Si je superpose le graphique équivalent avec des sommets et des arêtes, cela devrait ressembler à ceci.

Prenons le carré central / sommet, E, par exemple. Il a huit sommets voisins, nous pouvons donc nous déplacer vers le haut, le bas, la gauche, la droite et dans toutes les combinaisons diagonales de chacun. Et c’est vraiment tout ce que j’essayais de mettre en place ici: je vais utiliser un damier, et je vais permettre le mouvement dans huit directions. Un peu long, mais commençons maintenant à regarder le mouvement et le coût du mouvement.

En commençant par simple, je dirai que les déplacements vers le haut, le bas, la gauche et la droite ont un coût de déplacement de 1. Le tableau est occupé, je vais donc extraire le graphique et ajouter ce coût de mouvement sous forme de poids de bord.

Si ces poids sont des distances, et si les relations et les voisins sont disposés comme ceci, alors la géométrie peut nous parler du coût des mouvements diagonaux. En utilisant le Théorème de Pythagore, nous devrions obtenir √(12 + 12) = √2, ce qui est à peu près 1.41421356237… Ce qui n’est pas un très bon nombre avec lequel travailler. Alors, je vais voler une idée (et citer mes sources!), et multiplier et arrondir les coûts. Pour les deux types de mouvement, je vais les multiplier par dix, puis tronquer leurs décimales. Cela nous donnera des coûts finaux de 10 pour les mouvements haut, bas, gauche et droit, et de 14 pour les mouvements diagonaux.

Heuristiques

J’ai l’impression que ceux-ci sont difficiles à définir pour moi, alors je vais commencer par la ligne d’ouverture de Wikipedia sur le sujet:

En informatique, intelligence artificielle et optimisation mathématique, une heuristique (du grec ερρίσκω « Je trouve, découvre”) est une technique conçue pour résoudre un problème plus rapidement lorsque les méthodes classiques sont trop lentes, ou pour trouver une solution approximative lorsque les méthodes classiques ne parviennent pas à trouver une solution exacte. Ceci est réalisé en échangeant l’optimalité, l’exhaustivité, la précision ou la précision pour la vitesse. D’une certaine manière, cela peut être considéré comme un raccourci.

Est-ce utile? Tu comprends ? Parce que je ne comprends pas. Je veux dire, je comprends un peu, et c’est une description précise, mais si c’était la première fois que vous aviez entendu parler d’une heuristique, je ne suis pas sûr que vous auriez une image complète de ce que sont les heuristiques. Peut-être que si je vous parle juste de l’heuristique d’A *, vous comprendrez mieux.

Avec l’algorithme de Dijkstra, l’accent était mis sur une valeur : la distance la plus courte de l’indice de départ. Ce qui, quand on y pense, est un peu étrange. Vous avez cet algorithme qui essaie de trouver de nouveaux chemins plus courts vers une destination, mais il se concentre toujours sur l’endroit où il a commencé. Imaginez quelqu’un qui sort faire ses courses, mais qui marche en arrière tout le long du chemin, essayant de garder un œil sur sa maison jusqu’à ce qu’il arrive au magasin. Dans la vraie vie, cela ne fonctionnerait probablement pas, mais peut-être que si vous leur donniez le temps d’aller dans toute la ville, cela pourrait éventuellement fonctionner.

En partant de cette analogie loufoque, A * est différent de celui de Dijkstra parce qu’il suggère de se retourner et d’avancer. A *, comme celui de Dijkstra, garde également une trace de sa distance de la maison, mais sa caractéristique unique est qu’il garde également une trace de sa distance de sa destination. Lors de sa prochaine étape, Dijkstra examinera quel chemin est actuellement le plus court, mais A * va plus loin et considère également si cette étape le rapproche de son objectif. Plus simplement, A * a une estimation approximative de sa distance restante à son objectif, et lorsque cette estimation se rapproche de zéro, il sait qu’il se déplace dans la bonne direction. C’est l’heuristique que nous utiliserons dans nos exemples.

Parcourir l’algorithme

Cela va être un exemple assez simple, mais cela devrait vous montrer le flux de base et la répétition de l’algorithme. Je m’assurerai de fournir des liens dans mes références à d’autres exemples plus compliqués, mais cela devrait être une bonne amorce pour ceux-ci. Je vais utiliser une configuration similaire à celle de Dijkstra.

Une autre différence entre Dijkstra et A * est que Dijkstra peut commencer à boucler immédiatement, mais A * doit faire un peu de configuration pour son sommet de départ. Alors faisons-le maintenant, et ayons une idée un peu de la façon dont la table va fonctionner.

Tout d’abord, nous ajouterons A à l’ensemble ouvert. Deuxièmement, nous déterminerons la distance de A depuis le départ. Naturellement, la distance de A à A est nulle, donc cela sera ajouté à la table, et j’aurai ce chiffre dans le coin supérieur gauche du carré de A. Troisièmement, nous déterminerons la distance heuristique. Nous pouvons le faire de plusieurs façons, tout ce qui est important est que nous mesurons cette distance de la même manière pour chaque carré. Je vais utiliser une distance « à vol d’oiseau” pour toutes les distances heuristiques, ce qui signifie que je peux à nouveau utiliser le théorème de Pythagore. Dans ce cas, nous calculerons √ (202 + 302), et constaterons que A est une distance de 36,0555127546 from de L (j’arrondis les décimales au dixième le plus proche pour économiser de l’espace). Je vais ajouter ceci à la table et le placer dans le coin supérieur droit du carré de A. Enfin, la somme. Je vais ajouter la distance la plus courte du début à la distance heuristique, l’ajouter à la table et la placer au centre du carré de A.

C’est notre point de départ, et nous pouvons maintenant regarder les voisins de A et ajouter leurs valeurs à la table.

Tout d’abord, nous ajouterons B, E et F à l’ensemble ouvert. Ensuite, nous pouvons trouver leurs distances les plus courtes depuis le début, et comme tout est à un pas du début, ce sera juste 10 pour B et E, et 14 pour le déplacement diagonal vers F. Pour la distance heuristique, nous utiliserons le Théorème de Pythagore de chaque carré au sommet final. Enfin, nous obtiendrons leurs sommes et ajouterons « A” à chacune de leurs colonnes de sommets précédentes.

À ce stade, nous avons fait tout ce dont nous avions besoin avec A, il sera donc déplacé vers l’ensemble fermé, et nous aurons besoin d’un nouveau sommet actuel. Pour déterminer quel sommet doit être examiné ensuite, nous examinerons l’ensemble ouvert et trouverons le sommet qui a la somme la plus faible. En ce moment, c’est F avec une somme de 36,1. Nous allons donc en faire le sommet actuel et commencer à calculer les valeurs de ses voisins.

F a huit voisins, mais seulement cinq vont être modifiés ici. Premièrement, A est maintenant dans l’ensemble fermé, il ne peut donc pas être modifié maintenant. Pour les sept autres, nous les ajouterons à l’ensemble ouvert (sauf s’ils en font déjà partie), puis travaillons sur leurs distances depuis le début. Cela va fonctionner un peu comme l’algorithme de Dijikstra, et nous ajouterons la distance de F depuis le début à la distance de chacun de ses voisins par rapport à F. Sur notre table, la distance de F depuis le début est de 14, nous remplirons donc 14 + 10 = 24 ou 14 + 14 = 28 pour ceux-ci. Cependant, B et E ont déjà des distances plus courtes au début, de sorte que leurs enregistrements de table ne sont pas mis à jour. Cela laisse cinq sommets qui seront mis à jour, avec C, I et K obtenant 28, et G et J obtenant 24 pour leur distance depuis le début. Ensuite, utilisez le théorème de Pythagore pour les distances heuristiques de chacun de ces sommets, puis calculez leurs sommes, et enfin ajoutez « F” à la colonne de sommets précédente pour les sommets qui ont été mis à jour.

F est terminé et sera déplacé vers l’ensemble fermé, et un nouveau sommet courant sera choisi en fonction du sommet de l’ensemble ouvert ayant la somme la plus faible. C’est très proche, mais K est un dixième plus petit (et oui, c’est à cause d’une différence d’arrondi, mais dans ce cas, cela s’avère être un bon bris d’égalité). K sera le nouveau sommet à examiner, commençons donc par regarder ses voisins.

K a six voisins, dont trois sont déjà dans l’ensemble Ouvert, donc les deux derniers H et L seront également ajoutés à l’ensemble ouvert. Maintenant, nous allons calculer leurs distances depuis le début. La distance de K depuis le début est de 28, nous allons donc travailler avec 28 + 10 = 38 pour G, J et L, et 28 + 14 = 42 pour H. Cependant, G et J ont déjà des distances plus petites pour démarrer, elles ne seront donc pas mises à jour. Nous allons trouver les distances heuristiques pour chacun, calculer leurs sommes et ajouter « K” à chaque sommet précédent qui a été mis à jour.

K est complet et déplacé vers l’ensemble fermé, et le sommet suivant dans l’Ouvert avec la plus petite somme est L, notre destination!

Maintenant, que L est le sommet actuel, l’algorithme se termine et nous pouvons utiliser notre table pour tracer le chemin vers le début:

• Le sommet précédent de L est K
• Le sommet précédent de K est F
• Le sommet précédent de F ’ est A, le sommet de départ.

Donc, cela signifie que le chemin le plus court est Un >F >K >L.

En analysant les résultats

Par rapport à l’algorithme de Dijkstra, A * a laissé tout un gâchis derrière lui. Regardons quelques points étranges. En commençant, regardez le sommet C et sa distance au début: 28. Cela semble bizarre car A et C ne sont que deux mouvements horizontaux l’un de l’autre, donc la distance la plus courte devrait être de 20. À l’heure actuelle, C semble penser que son chemin le plus court vers A est deux mouvements diagonaux à travers F.

Lorsque l’algorithme de Dijkstra se termine, il devrait fournir un tableau très complet des distances depuis le point de départ. Inversement, la table de A * a de mauvaises valeurs et manque complètement le sommet D. Mais elle a la même réponse que celle de Dijkstra, et elle a fait beaucoup plus vite. Dijkstra aurait voulu examiner les 12 sommets avant de déclarer qu’il avait trouvé le chemin le plus court; A * n’avait besoin que d’en regarder 4 avant de trouver le bon chemin. Ce changement de vitesse est dû à l’heuristique que nous utilisions: aussi souvent que possible, nous voulions fermer la distance avec notre destination. Si nous revenons à la définition heuristique de Wikipedia, A * a troqué la complétude contre la vitesse.

Essayons un autre petit exemple, mais avec une obstruction sur le chemin de la destination.

Le point de départ est le sommet en haut à gauche, et A * essaie de trouver le chemin le plus court vers le sommet en bas à droite. Les carrés noirs représentent un espace dans le graphique et ne peuvent pas être parcourus. Si A * suit son heuristique de « toujours se rapprocher de la destination », ces carrés noirs vont le conduire dans une impasse.

À ce stade, A * recherchera les plus petites sommes, qui seront les carrés juste en dessous et à droite du sommet de départ. A * explorera les deux chemins, mais le chemin descendant se heurtera à une autre impasse, et le chemin vers la droite trouvera un moyen de contourner les carrés noirs. Cela pourrait se dérouler un peu différemment de cela, mais supposons que c’est ainsi que A * a géré ce scénario. Même quand il a été tiré dans des impasses, il a pu revenir en arrière et trouver un autre chemin, et il n’a pas eu besoin de regarder chaque sommet (le sommet tout en haut à droite a été sauté à nouveau). Cela signifie que lorsqu’une étoile * fonctionne à son pire niveau absolu, elle est fondamentalement aussi rapide que les performances normales de Dijkstra. Chaque algorithme a des cas d’utilisation parfaitement valides, mais en termes de recherche de chemin et de recherche des chemins les plus courts, A * est le meilleur choix.