Visualiseur d'algorithmes de recherche de chemin

Trois des quatre algorithmes du menu déroulant sont un seul et même algorithme. Ils classent tous les cellules en attente d'exploration à l'aide d'une seule expression, f(n) = g(n) + h(n) — le coût accumulé plus l'estimation du coût restant — et ne diffèrent que par celui des deux termes qu'ils conservent. Retirez h et vous obtenez l'algorithme de Dijkstra. Ignorez g et vous obtenez Greedy Best-First. Le quatrième, le parcours en largeur (BFS), est ce à quoi se réduit l'algorithme de Dijkstra lorsque chaque déplacement coûte la même chose.

Ce que signifie chaque symbole

g(n)

le coût du trajet le moins cher trouvé jusqu'ici du départ à la cellule n. Un déplacement latéral ou vertical coûte 1 ; une diagonale coûte √2, car le déplacement est mesuré sous forme de longueur plutôt que compté comme un seul mouvement.

h(n)

l'estimation du coût restant à parcourir. Pour l'algorithme de Dijkstra et le parcours en largeur (BFS), elle n'est pas seulement inutilisée — elle est zéro, et c'est précisément ce qui en fait la même expression avec un terme en moins.

f(n)

la clé de classement : la cellule avec le plus petit f est celle explorée ensuite. Elle est affichée au-dessus de la grille avec les valeurs numériques de la cellule actuelle substituées, de sorte que le choix que l'algorithme vient de faire soit visible plutôt qu'affirmé.

frontier

les cellules ambres — découvertes, mais pas encore explorées. Nœuds développés compte ce qui a quitté cet ensemble, ce qui en fait une mesure du travail effectué, non de la qualité de la réponse.

D’où vient la formule

1. Définissez ce que signifie « le plus court » avant de choisir un algorithme. Le coût d'un chemin est la somme des longueurs de ses étapes : 1 pour un déplacement latéral ou vertical, √2 pour une diagonale. On ne compte pas les cellules ; on additionne les distances.
2. Voici maintenant la boucle, identique pour les quatre : retirez une cellule du front, marquez-la comme explorée, et proposez à nouveau chaque voisin franchissable au front avec un g mis à jour. Remarquez ce que cette boucle ne mentionne jamais — une heuristique, la direction de l'arrivée, ou l'algorithme que vous avez choisi.
3. La seule décision restante est donc quelle cellule retirer, et cela tient en une seule expression. Classez par g + h et vous avez la Recherche A*. Fixez h = 0 et le classement se fait uniquement selon le coût accumulé — c'est l'algorithme de Dijkstra, qui s'étend vers l'extérieur en cercles concentriques parce qu'il n'a aucune idée d'où se trouve l'arrivée. Ignorez plutôt g et le classement se fait uniquement selon l'estimation — c'est Greedy Best-First, qui fonce vers l'arrivée et accepte n'importe quel itinéraire auquel il est parvenu.
4. Le parcours en largeur (BFS) ne classe pas du tout : premier entré, premier sorti. Lorsque l'option Autoriser les diagonales est désactivée, chaque étape coûte exactement 1, donc l'ordre d'arrivée des cellules est l'ordre des g croissants — et le parcours en largeur explore donc exactement ce qu'explore l'algorithme de Dijkstra. Vous pouvez le vérifier sans régénérer la grille : basculez entre les deux et Nœuds développés ne bouge pas. Activez les diagonales et l'argument s'effondre, car une diagonale coûte √2 plutôt que 1 et l'ordre d'arrivée ne suit plus le coût.

Comment lire ce que vous voyez

Le score de priorité se trouve au-dessus de la grille avec les valeurs g et h propres à la cellule actuelle remplies, afin que vous puissiez lire le classement qui a produit le dernier choix. En dessous se trouvent deux compteurs : Nœuds développés et Longueur du chemin. L'ambre représente le front, l'indigo est déjà exploré. Changer d'algorithme ne génère pas de nouvelle grille, et c'est ce qui donne toute sa valeur à la comparaison — sur la même disposition, le nombre de Nœuds développés de l'algorithme de Dijkstra n'est jamais inférieur à celui de la Recherche A*, et celui de Greedy Best-First n'en représente qu'une petite fraction.

Suppose

Des coûts d'étape qui ne sont jamais négatifs, et une grille qui ne change pas pendant l'exécution de la recherche. Le départ est toujours la cellule en haut à gauche et l'arrivée celle en bas à droite. La fermeture d'une cellule est définitive — la boucle ne revient jamais sur une cellule — et cela n'est sûr que parce qu'aucun itinéraire ultérieur ne peut arriver à moindre coût lorsque chaque étape ajoute une quantité non négative.

Ne tient plus quand

Nœuds développés est le nombre qui varie le plus spectaculairement, et ce n'est pas une mesure de qualité. Choisissez Greedy Best-First : sur la même grille, il explore une petite fraction de ce que fait la Recherche A*, et sur la plupart des dispositions, il renvoie une Longueur du chemin plus grande. Générez quelques nouvelles grilles et observez les deux compteurs évoluer dans des directions opposées. Examiner moins de cellules indique à quel point l'algorithme a travaillé dur, et jamais la qualité de sa réponse.