A*-algoritme: verschil tussen versies

Geen verandering in de grootte ,  10 jaar geleden
k (robot Erbij: cs:A*)
 
== Beschrijving ==
Het A*-algortimealgoritme 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.
 
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.
Anonieme gebruiker