Recherche de chemin : BFS, DFS, Dijkstra, A*

Quatre façons d'explorer

Les quatre algorithmes suivent le même schéma : garder une frontière de cases à explorer, en sortir une, y ajouter ses voisines. Ils ne diffèrent que par l'ordre dans lequel la frontière est vidée.

Ce qu'il faut observer

• BFS s'étend en cercles concentriques : il trouve le chemin le plus court en nombre de cases, mais ignore les coûts. Sur la carte « Terrain coûteux », il traverse le terrain difficile.
• DFS file tout droit puis revient sur ses pas. Il trouve un chemin, souvent très long : il sert à explorer (labyrinthes, composantes connexes, tri topologique), pas à optimiser.
• Dijkstra étend la frontière par coût croissant : il contourne le terrain difficile quand le détour coûte moins cher. Sans terrain, il se comporte comme BFS.
• A* ajoute au coût déjà payé une heuristique $h(n)$, estimation du coût restant — ici la distance de Manhattan $\lvert \Delta x \rvert + \lvert \Delta y \rvert$. Il explore d'abord vers l'arrivée et visite beaucoup moins de cases, pour le même chemin optimal.

Pourquoi A* reste optimal

Une heuristique est admissible si elle ne surestime jamais le coût réel restant. La distance de Manhattan l'est : aucun déplacement ne coûte moins de 1, et il en faut au moins $\lvert \Delta x \rvert + \lvert \Delta y \rvert$. Avec $h = 0$, A* redevient Dijkstra ; avec une heuristique qui surestime, il va plus vite mais peut rater le meilleur chemin.

Le tableau sous la figure compare les quatre algorithmes sur la carte courante : même coût pour Dijkstra et A*, nombre de cases explorées très différent.