A*
Comment trouver le chemin le moins cher sans tout explorer ?
Ordonne la frontière par le coût déjà payé plus une estimation de ce qui reste, donc il fonce vers le but comme la recherche gloutonne tout en trouvant le chemin le moins cher.
A* combine les deux idées précédentes. Chaque case reçoit f = g + h. Ici g est le coût exact depuis le départ, ce qu’utilise Dijkstra, et h une estimation du coût jusqu’au but, ce qu’utilise la recherche gloutonne. Il développe toujours la case de f le plus bas.
Si h ne surestime jamais le coût restant réel (une heuristique admissible), A* est optimal, et il développe bien moins de cases que Dijkstra, car les cases qui éloignent du but reçoivent un f élevé et attendent. Plus h est proche de la vérité, moins il lui faut de cases.
Multiplier h par un poids supérieur à 1 le rend plus glouton : plus rapide, avec un chemin qui peut être plus long que l’optimal jusqu’à ce facteur. La démo a un curseur pour exactement cela.
Chargement de la démo…
La grille avec A* sélectionné. Changez l’heuristique et son poids, puis utilisez « Tout comparer » pour voir combien de cases chaque recherche a développées.
- 01Poser g(départ) = 0 et mettre le départ en file avec f = h(départ).
- 02Prendre la case de f le plus bas.
- 03Si c’est le but, remonter les parents mémorisés jusqu’au départ.
- 04Pour chaque voisine, calculer g(case) plus le coût du pas. Si cela bat le g enregistré de la voisine, l’enregistrer, mémoriser le parent et mettre la voisine en file avec f = g + w · h.
- 05Répéter jusqu’à ce que la file soit vide.
function a_star(start, goal, h, w = 1):
g = {start: 0}
parent = {}
heap = [(w * h(start), start)]
while heap is not empty:
_, cell = heap.pop_min()
if cell == goal: return path_from(parent, goal)
for n, step in neighbours(cell):
new = g[cell] + step
if new < g.get(n, infinity):
g[n] = new
parent[n] = cell
heap.push((new + w * h(n), n))
return no_pathLe temps dépend de l’heuristique : avec une heuristique parfaite il va droit au but, avec h = 0 il devient l’algorithme de Dijkstra. La mémoire est celle de Dijkstra.
- Optimal quand l’heuristique est admissible.
- Développe en général bien moins de cases que Dijkstra.
- Un seul poids échange qualité du chemin contre vitesse.
- Demande une bonne heuristique pour le problème.
- La mémoire croît avec la frontière, comme Dijkstra.
- Perd sa garantie dès que le poids dépasse 1.
- 01Recherche de cheminQuatre heuristiques (octile, Manhattan, euclidienne, Tchebychev) et un curseur de poids, avec le nombre de cases développées.