A* (A-ster)
Algoritme dat het kortste pad in een graaf vindt: Dijkstra plus een heuristiek die de zoektocht richting het doel stuurt.
Hart, Nilsson & Raphael (Stanford, 1968). Beoordeelt knopen met f(n) = g(n) + h(n), waarbij g de kosten vanaf de start zijn en h de geschatte kosten tot het doel. Is h toelaatbaar (overschat nooit), dan garandeert A* een optimale oplossing.
Standaardalgoritme voor navigatie in game-AI, robotica en gps-routering. Manhattan- en Euclidische afstand zijn gangbare heuristieken voor 2D-roosters. Alternatieven: Dijkstra (zonder heuristiek), Jump Point Search (optimalisatie voor roosters), HPA* (hiërarchisch).