Trouver le plus court chemin, sans force brute
Entre une case départ et une case arrivée séparées par des murs, il existe une infinité de trajets, mais un seul mérite d'être calculé : le plus court. Explorer toute la grille au hasard serait ruineux. A* (« A star ») résout ce problème en guidant la recherche : à chaque étape, il n'ouvre que la case la plus prometteuse. Je m'en sers ici comme démonstration, mais c'est le même algorithme qui route un déplacement dans un jeu, une tournée de livraison ou un flux logistique.
Le cœur d'A* : le coût f = g + h
Chaque case candidate reçoit un score f = g + h. Le g
est le coût réel déjà parcouru depuis le départ — ce que l'on sait avec certitude.
Le h est une heuristique : une estimation du coût restant
jusqu'à l'arrivée, ici la distance de Manhattan (la somme des écarts horizontal et
vertical), naturelle sur une grille où l'on se déplace en quatre directions. A*
développe toujours la case au plus petit f : celle qui promet le
meilleur compromis entre le chemin déjà tracé et ce qu'il reste, en théorie, à faire.
Pourquoi une heuristique admissible garantit l'optimum
Une heuristique est dite admissible lorsqu'elle ne surestime
jamais le coût réel restant. La distance de Manhattan l'est : à vol d'oiseau sur la
grille, elle ignore les murs et ne peut donc que sous-estimer un vrai trajet. Cette
propriété est ce qui rend A* fiable : tant que h reste optimiste, il
est mathématiquement impossible qu'A* ferme l'arrivée par un chemin plus long qu'un
autre encore ouvert. Le premier chemin trouvé est le plus court —
pas seulement un chemin court. Une heuristique trop gourmande irait plus
vite mais pourrait rater l'optimum ; l'admissibilité est le prix de la garantie.
La file de priorité et la parenté avec Dijkstra
Les cases à examiner vivent dans l'open set, une file de priorité ordonnée
par f : à chaque tour, on en extrait le minimum. Coupez l'heuristique
(h = 0) et A* redevient exactement l'algorithme de Dijkstra :
sans direction privilégiée, la recherche s'étale en anneaux concentriques autour du
départ et visite bien plus de cases pour le même résultat. La touche « D » de la démo
bascule entre les deux : on voit A* filer droit vers l'arrivée là où Dijkstra explore
à l'aveugle. A* n'est rien d'autre que Dijkstra à qui l'on a donné un sens de l'orientation.
Ce que cela change pour un projet
Derrière cette grille se cache une compétence concrète : choisir le bon algorithme plutôt que d'empiler de la puissance de calcul. Là où une approche naïve parcourt tout, un algorithme guidé fait le même travail en une fraction des opérations — et la différence explose à l'échelle de vos volumes réels. C'est exactement ce que j'apporte sur vos projets : identifier le point où une bonne structure de données ou une heuristique bien posée transforme une fonctionnalité lente et coûteuse en une fonctionnalité rapide, prévisible et tenable dans le temps.
