A*-algoritme: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
k →Externe link: status artikel loopt nu via Wikidata |
Labels: Bewerking via mobiel Bewerking via mobiele app |
||
Regel 11:
== Beschrijving ==
Het A*-algoritme begint in een geselecteerde knoop. Van deze knoop bepaalt men de "
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 "
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
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.
| |||