A*-algoritme: verschil tussen versies

5 bytes toegevoegd ,  4 jaar geleden
k (→‎Externe link: status artikel loopt nu via Wikidata)
Labels: Bewerking via mobiel bewerking via mobiele app
 
== Beschrijving ==
Het A*-algoritme begint in een geselecteerde knoop. Van deze knoop bepaalt men de "kostkosten" 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.
 
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 "kostkosten" om de knoop te bezoeken en slaat deze op in de knoop. Deze kostkosten wordtworden berekend als de cumulatieve som van de kosten in de ouderknopen, plus de kostkosten 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 kostkosten, 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 kostkosten 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.
Anonieme gebruiker