A*-algoritme
A* (uitgesproken als A-star of A-ster) is een algoritme om in een graaf de kortste weg te vinden tussen twee knopen van die graaf. Het algoritme zoekt een pad van een startknoop naar een gevraagde knoop door middel van een "heuristische schatting", die elke knoop rangschikt volgens een schatting van de beste route door die knoop. Het algoritme bezoekt de knopen in de volgorde van deze heuristische schatting, het A*-algoritme is zo een voorbeeld van een "beste-eerst" algoritme. Het werd in 1968 voor het eerst beschreven door Peter Hart, Nils Nilsson, en Bertram Raphael.
Inhoud |
[bewerk] Intuïtief
Stel bij wijze van voorbeeld dat je op een kruispunt A staat, en je naar kruispunt B wil toegaan, waarvan je weet dat dit kruispunt ergens ten noorden van je huidige locatie ligt. In dit geval zijn de kruispunten de knopen en de wegen de takken van de graaf.
Wanneer men een breedte-eerst-algoritme uitvoert, zoals Dijkstra's algoritme , zou men eerst alle punten afzoeken binnen een vaste straal van het begin, en zo stap voor stap de cirkel uitbreiden naar verdergelegen kruispunten. Dit kan een efficiënte strategie zijn wanneer je niet weet waar de bestemming zich bevindt.
Deze zoekmethode is echter tijdsverlies wanneer je meer informatie hebt. Een betere strategie bestaat erin eerst het kruispunt direct ten noorden van je huidige locatie te gaan bezoeken, omdat dit kruispunt immers dichter bij punt B zal liggen. Wanneer de wegen goed liggen kan je zo verder kruispunten afzoeken die steeds dichter bij de bestemming B liggen. Af en toe kan men even op zijn stappen moeten terugkomen, maar op typische kaarten is dit een snelle strategie. Bovendien kan bewezen worden dat deze strategie de best mogelijke route zal vinden, net als een breedte-eerst-zoektocht. Dit principe vormt de essentie van het A*-algoritme.
Er is echter geen enkele garantie dat het A*-algoritme beter presteert dan een eenvoudiger zoekalgoritme. In een omgeving die op een doolhof lijkt, kan bijvoorbeeld de enige weg naar de bestemming zo liggen dat men eerst een stuk zuidwaarts moet gaan eer men een bocht naar het noorden maakt. In dit geval zal het verkennen van de knopen in het noorden, die op de kaart dichter bij de bestemming liggen, aanvankelijk wat tijd kosten.
[bewerk] Beschrijving
Het A*-algortime begint in een geselecteerde knoop. Van deze knoop bepaalt men de "kost" om de knoop te bezoeken, voor de initiële knoop is dit gewoonlijk nul. A* schat dan de afstand vanaf de huidige knoop tot de bestemming. Deze schatting en de kost worden opgeteld, en vormen de heuristiek die aan het pad naar deze knoop wordt toegekend. De knoop wordt vervolgens toegevoegd in een prioriteitswachtlijn, die soms "open" genoemd wordt.
Het algoritme haalt vervolgens een knoop uit de prioriteitswachtlijn; door de werking van deze wachtlijn zal dit de knoop met de laagste heuristiek zijn. Wanneer de wachtlijn leeg is, is er geen pad van de startknoop naar de doelknoop en stopt het algoritme. Is de knoop die uit de wachtrij gehaald wordt de doelknoop, dan reconstrueert A* het succesvolle pad, geeft het weer, en stopt. Deze reconstructie van het pad uit de opgeslagen gesloten knopen betekent dat het niet nodig is om het voorlopig pad op te slaan in elke knoop.
Wanneer de knoop die uit de wachtlijn gehaald wordt niet de doelknoop is, worden nieuwe knopen gecreëerd voor alle aanvaardbare aangrenzende knopen; de manier waarop dit precies gebeurt hangt af van het specifieke probleem. Voor elk van die knopen berekent A* de "kost" om de knoop te bezoeken en slaat deze op in de knoop. Deze kost wordt berekend als de cumulatieve som van de kosten in de ouderknopen, plus de kost van de bewerking om de nieuwe knoop te bereiken.
Het algoritme houdt ook een "gesloten" lijst bij met knopen die reeds gecontroleerd zijn. Wanneer een nieuw gegenereerde knoop al in de lijst staat met een gelijke of lagere kost, doet men verder niets met deze knoop of het pad dat ermee geassocieerd is. Wanneer de nieuwe knoop al in de gesloten lijst staat, maar nu een lagere kost heeft, wordt deze oude knoop uit de gesloten lijst verwijderd, en werkt men verder met de nieuwe knoop.
Vervolgens wordt een schatting van de afstand van de nieuwe knoop naar de bestemming gemaakt, en wordt deze opgeteld om de heuristiek voor de nieuwe knoop te vormen. Deze wordt vervolgens aan de "open" prioriteitswachtlijn toegevoegd, tenzij hier al een identieke knoop met lagere of gelijke heuristiek in zit.
Wanneer de vorige stappen herhaald zijn voor elke nieuwe aangrenzende knoop, kan de originele knoop uit de prioriteitswachtrij geschrapt wordenen aan de "gesloten" lijst worden toegevoegd. Vervolgens haalt men de volgende knoop uit de prioriteitswachtlijn, en herhaalt men het proces.
[bewerk] Referenties
- (en) P. E. Hart, N. J. Nilsson, B. Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics SSC4 (2), pp. 100-107, 1968.
- (en) P. E. Hart, N. J. Nilsson, B. Raphael: Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", SIGART Newsletter, 37, pp. 28-29, 1972.
- (en) N. J. Nilsson, Principles of Artificial Intelligence, Tioga Publishing Company, Palo Alto, California, 1980.
[bewerk] Externe link
- A* Tutorial. (Engels)
- A* Tutorial. (Nederlands)
