A*-algoritme: verschil tussen versies

4 bytes verwijderd ,  13 jaar geleden
k
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 [[kruispunt]]en de [[graaf (wiskunde)|knopen]] en de wegen de [[graaf (wiskunde)|takken]] van de graaf.
 
Wanneer men een [[breedte-eerst]]-algoritme uitvoert, zoals [[kortstepadalgoritme|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.
11.932

bewerkingen