A* (A-star)
Algoritmo di ricerca del percorso che trova il cammino minimo in un grafo — Dijkstra più un'euristica che orienta la ricerca verso l'obiettivo.
Hart, Nilsson e Raphael (Stanford, 1968). Valuta i nodi con f(n) = g(n) + h(n), dove g è il costo dalla partenza e h la stima del costo fino all'obiettivo. Se h è ammissibile (non sovrastima mai), A* garantisce una soluzione ottimale.
Algoritmo standard per la navigazione nell'IA dei giochi, nella robotica e nel calcolo dei percorsi GPS. Le distanze di Manhattan ed euclidea sono euristiche comuni sulle griglie 2D. Alternative: Dijkstra (senza euristica), Jump Point Search (ottimizzazione per griglie), HPA* (gerarchico).