🗺️ Recherche de Chemin A*

Greedy Best-First fixe g = 0 et n'utilise que h pour classer les nœuds, se précipitant toujours vers le nœud qui semble le plus proche du but. C'est très rapide dans des environnements ouverts, mais elle ignore le coût réel du chemin, donc elle peut être attirée à travers un terrain coûteux ou autour d'obstacles vers un itinéraire plus long. Dans le pire cas, elle trouve un chemin arbitrairement pire que l'optimal.

Utilisez la distance de Manhattan quand le mouvement est restreint à 4 directions (haut, bas, gauche, droite), car elle compte exactement le nombre minimum de pas. La distance euclidienne convient quand les déplacements diagonaux sont autorisés et que le coût diagonal vaut √2. La distance de Chebyshev (max de |Δx|, |Δy|) est le bon choix quand les 8 directions coûtent le même prix, comme c'est courant dans de nombreux jeux de stratégie.

Les cellules pondérées représentent un terrain plus difficile à traverser — boue, eau peu profonde ou route accidentée. Dans cette simulation, une cellule pondérée coûte 5 au lieu de 1 pour y entrer, donc A* contournera souvent plusieurs cellules pondérées plutôt que de les traverser. Dijkstra et A* gèrent tous deux correctement les poids ; Greedy Best-First ignore les coûts et peut traverser directement un terrain coûteux.

Dans le pire cas, A* a une complexité temporelle et spatiale de O(b^d), où b est le facteur de branchement et d la profondeur de la solution optimale. Avec une heuristique cohérente (satisfaisant l'inégalité triangulaire), chaque nœud est étendu au plus une fois, donnant O(V log V) sur un graphe fini à V sommets — la même borne asymptotique que Dijkstra avec un tas binaire.

Le générateur de labyrinthe crée un labyrinthe parfait grâce à un algorithme aléatoire qui creuse des passages dans une grille, garantissant exactement un chemin entre deux cellules quelconques. Les labyrinthes sont particulièrement exigeants pour les algorithmes de recherche car les couloirs étroits éliminent l'avantage heuristique de A* — avec un seul chemin valide, tous les algorithmes doivent explorer à peu près les mêmes nœuds.

Le vert marque le nœud de départ, le rouge le but. Les cellules bleues forment la frontière actuelle (ensemble ouvert), le bleu foncé marque les nœuds visités (fermés), et le jaune met en évidence le nœud en cours d'extension. Les cellules pondérées apparaissent en brun. Une fois un chemin trouvé, il est tracé en vert citron du départ au but, et vous pouvez lire le coût exact dans le panneau de statistiques.

Oui — A* fonctionne sur tout graphe dont les coûts d'arêtes sont non négatifs et pour lequel vous pouvez fournir une heuristique admissible. Les applications réelles incluent la planification de mouvement de bras robotiques 3D (graphes d'espace de configuration), le routage réseau (latence comme coût), et l'analyse du langage naturel (treillis de type Viterbi). La grille ici n'est que la représentation la plus visuellement intuitive de l'algorithme général.

Les nœuds étendus comptent combien de fois l'algorithme a retiré un nœud de la frontière et traité ses voisins — c'est la mesure principale de l'efficacité de A*. Un compte plus bas signifie que l'heuristique guide bien la recherche. Sur une grille 30×30 (900 cellules), une bonne heuristique peut souvent trouver le chemin optimal en étendant moins de 100 nœuds, alors que Dijkstra peut étendre chaque cellule accessible.