Het A* (uitgesproken als: “A ster”) algoritme is een zoekalgoritme waar bij Kunstmatige Intelligentie veel aandacht aan gespendeerd is. Met deze oplossing kun je in een graaf, een verzameling punten verbonden met lijnen, de kortste route vinden.
Het werkt volgens de formule :
F (n)= G (n)+ H(n)
Waarbij F staat voor de geschatte kosten van het totale pad.
G zijn de kosten van het beginpunt tot het huidige punt volgens het gegenereerde pad.
H zijn de geschatte kosten van het huidige gegenereerde punt tot het eindpunt.
Het belangrijke bij H is dat deze admissable (toelaatbaar) is, dit wil zeggen dat het nooit de kosten tot het goal overschat. In formules wordt dit uitgedrukt als h(n) <= h*(n). h is hier de geschatte kosten tot het goal en h* de werkelijke kosten tot het goal. Dus de heuristiek moet optimistisch zijn en wanneer het pad 30 meter in werkelijk is, kan h hier 27 meter schatten. Dit voorkomt vastlopen in de zoekboom.
Depth First Search
Het A* algoritme maakt gebruik van depth first search. Dit is een zoekmethode die een beslissingsboom kan doorlopen door van bijvoorbeeld van links naar rechts paden zo diep mogelijk uit te zoeken en als het geen oplossing vindt, dan doet het een stapje terug (backtracking).
Algoritme in plaatjes
Vaak is het bij complexere problemen makkelijker om een plaatje te zien, plaatjes zeggen meer dan 1000 woorden. Daarom volgt nu een beschrijving aan de hand van het volgende plaatje.
Stel we willen van Saarbrucken naar Wurzburg. Het A* algoritme gaat dan als volgt:
[imageflow id="1"]
