A*-algoritme: verschil tussen versies

38 bytes toegevoegd ,  12 jaar geleden
k
DEFAULTSORT toegevoegd
(→‎Externe link: - Commons)
k (DEFAULTSORT toegevoegd)
'''A*''' (uitgesproken als ''A-star'' of ''A-ster'') is een [[algoritme]] om in een [[graaf (wiskunde)|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]].
 
== Intuïtief ==
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.
 
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.
 
== 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 [[schatten|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.
 
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.
 
== Referenties ==
* {{en}} P. E. Hart, N. J. Nilsson, B. Raphael: ''A Formal Basis for the Heuristic Determination of Minimum Cost Paths'', [[Institute of Electrical and Electronics Engineers|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"'', [[Association for Computing Machinery|SIGART]] Newsletter, 37, pp. 28-29, 1972.
* {{en}} N. J. Nilsson, ''Principles of Artificial Intelligence'', Tioga Publishing Company, Palo Alto, California, 1980.
 
== Externe link ==
* {{en}}[http://www.policyalmanac.org/games/aStarTutorial.htm A* Tutorial]. (Engels)
 
{{Commons|A* Algorithm}}
 
{{DEFAULTSORT:A ster-algoritme}}
[[Categorie:Grafentheorie]]
[[Categorie:Zoekalgoritme]]
150.337

bewerkingen