| Het A*-algoritme (A-ster) is een heuristisch zoekalgoritme dat in de computerwetenschap wordt gebruikt om het kortste pad tussen twee knooppunten in een grafiek te vinden. Het is een uitbreiding van het Dijkstra-algoritme, dat het kortste pad vindt maar geen heuristiek gebruikt.
Intuïtie
A* maakt gebruik van heuristieken, informatie over het probleemdomein die de zoektocht helpt begeleiden. Deze heuristieken worden vaak toelaatbare heuristieken of afstandsheuristieken genoemd, omdat ze nooit de werkelijke kosten om het doel te bereiken overschatten. In veel gevallen vindt A* optimale oplossingen, al is dit niet altijd gegarandeerd.
Hoe werkt A*?
A* onderhoudt twee sets knooppunten tijdens het zoeken:OPEN (Fringe) en GESLOTEN
OPENEN bevat alle knooppunten die zijn gegenereerd, maar nog niet volledig zijn geëvalueerd. Het wordt geordend op basis van de F-score (hieronder besproken) van de leden, met de laagste F-score vooraan.
GESLOTEN bevat alle knooppunten die volledig zijn geëvalueerd.
Het algoritme begint met het plaatsen van het startknooppunt in OPEN, terwijl het doelknooppunt aanvankelijk in GESLOTEN staat. Bij elke stap van het algoritme verwijdert A* het knooppunt in OPEN met de laagste F-score, breidt het uit en voegt al zijn buren toe aan OPEN. Als een buurman nog niet OPEN of GESLOTEN is, berekent A* hiervoor een G-score (de werkelijke kosten om de buurman vanaf het startknooppunt te bereiken) en een H-score (een schatting van de kosten om het doel van de buurman te bereiken). en voegt het toe aan OPEN. Als een buurman al in OPEN staat, wordt de nieuwe G-score vergeleken met de huidige G-score, en als de nieuwe G-score lager is, wordt de buurman bijgewerkt. Als een buur al in GESLOTEN is, wordt de nieuwe G-score vergeleken met de huidige G-score, en als de nieuwe G-score lager is, wordt de buur verplaatst van GESLOTEN naar OPEN en bijgewerkt.
Beëindiging
Het algoritme eindigt op twee manieren. Ten eerste, als een buur van het knooppunt dat wordt uitgebreid het doel is, retourneert het algoritme het pad naar het doel. Ten tweede, als OPEN leeg raakt, wordt het algoritme zonder succes beëindigd, wat aangeeft dat er geen geldig pad is vanaf het startknooppunt naar het doel.
Complexiteit
De tijdscomplexiteit van het A*-algoritme in het slechtste geval is exponentieel in de grootte van de grafiek. In de praktijk presteert A* echter goed bij veel problemen, en vindt het vaak binnen een redelijke tijd optimale oplossingen. |
