A*-algoritme: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
k Robot: de:A*-Algorithmus is een goed artikel |
Geen bewerkingssamenvatting |
||
Regel 4:
Stel bij wijze van voorbeeld dat je op een [[kruispunt (verkeer)|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 [[graaf (wiskunde)|knopen]] en de wegen de [[graaf (wiskunde)|takken]] van de graaf.
Wanneer men een [[
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
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.
Regel 34:
{{DEFAULTSORT:A ster-algoritme}}
[[Categorie:Grafentheorie]]
[[Categorie:Zoekalgoritme]]
{{Link GA|de}}
|