Visualiseur d'algorithmes de recherche de chemin
observe différents algorithmes de recherche s'affronter sur la même grille, front par front
pourquoi les heuristiques comptent 🖖
La formule f(n)=g(n)+h(n) fait préférer à A* les nœuds peu coûteux jusqu'ici et qui semblent encore proches de l'arrivée. Si h ne surestime jamais le coût restant, A* conserve sa garantie de plus court chemin ; une heuristique admissible plus forte explore moins de cellules inutiles. Change le menu déroulant d'algorithme pour voir ce qui se passe si l'on retire l'heuristique (Dijkstra), le coût déjà payé (Greedy), ou tout système de score (BFS).
Une boucle, quatre personnalités 🖖
Les quatre algorithmes exécutent exactement la même boucle : ils retirent la case la plus prometteuse d'une liste d'attente (le front ambre), la marquent comme visitée (indigo), puis rajoutent ses voisines libres à la liste. Ils ne diffèrent que par la façon dont ils décident quelle case semble la plus prometteuse. À retenir : le nombre de nœuds développés est le vrai tableau de bord — moins de cases indigo, c'est le même but atteint avec moins de travail gaspillé.
Les diagonales peuvent briser la garantie 🖖
Activez 'Autoriser les diagonales' avec l'heuristique de Manhattan et A* peut discrètement renvoyer un chemin qui n'est pas le plus court. Ici un pas diagonal ne coûte que √2 ≈ 1.41, mais la distance de Manhattan le facture 2 — l'heuristique surestime donc, devient non admissible, et la garantie d'optimalité est perdue. Passez à Euclidienne, qui ne dépasse jamais la distance à vol d'oiseau, et le plus court chemin revient.
Exemples de problèmes
- grille ouverte - Des obstacles clairsemés produisent un chemin A* quasi direct, avec très peu d'expansions.
- façon labyrinthe - Des obstacles denses forcent A* à emprunter des détours plus longs et à effectuer davantage d'expansions.
- heuristique faible - Une heuristique plus faible explore beaucoup plus de cellules avant de trouver le même chemin.
- Dijkstra explore - Dijkstra ignore l'objectif et se propage dans toutes les directions.
- piège greedy - Le glouton Best-First fonce vers l'objectif et peut se laisser piéger dans des impasses.
- bfs + diagonales - BFS traite les déplacements diagonaux et orthogonaux comme ayant le même coût, donc son chemin peut différer de celui d'A*.