A*-zoeken
Dijkstra met richtingsgevoel. Bij de kosten van elke plek telt hij een schatting van de resterende kosten op, dus probeert hij eerst de plekken die het dichtst bij het doel lijken.
- tijd O((V + E) log V)
- geheugen O(V)
- gebruikt een prioriteitswachtrij
Wat betekent dit?
- Kosten: wat een zet kost. In het doolhof kost grond 1, modder 3 en water 9; in de graaf het getal op de kant.
- Prioriteitswachtrij: een wachtrij waarin de goedkoopste eerst gaat, niet wie het eerst kwam.
- Schatting (h): een gok van de resterende kosten. A* blijft alleen exact als die nooit te hoog is.
- Een kant relaxeren: nagaan of de weg via de huidige plek een buur lagere kosten geeft, en die dan overnemen.
- in de wachtrij
- huidige
- afgerond
- goedkoopste weg
- grond · 1
- modder · 3
- water · 9
- muur
Nieuw: Start bij A1 met kosten 0 en een schatting van 26 tot het doel. Het is het enige in de wachtrij.
Spatie: afspelen of pauzeren. Pijltjes links/rechts: stap. Home en End: springen.
Probeer dit: Kies het open veld en wissel tussen Dijkstra en A*: beide vinden een weg met dezelfde kosten, maar A* haalt veel minder vakjes uit de wachtrij.
Hoe het werkt
A* werkt als Dijkstra, maar ordent de wachtrij op f = kosten tot nu toe + h, waarbij h de resterende kosten schat. In het doolhof is h het aantal zetten tot M zonder muren en modder; in de graaf de afstand in rechte lijn gedeeld door 10. Zolang h nooit te hoog schat, is de weg die A* heeft als hij het doel neemt de goedkoopste, precies zoals bij Dijkstra. Hoe beter de schatting, hoe minder plekken hij hoeft te bekijken.
Wanneer het een goede keuze is
Gebruik A* als je één doel zoekt en kunt schatten hoe ver het is: padvinding in games, robots, routeplanners op een kaart. Met h = 0 is het precies Dijkstra. Een schatting die te hoog kan uitvallen maakt A* sneller, maar kan je de goedkoopste weg kosten.