A*-zoeken
Het algoritme van Dijkstra vindt de kortste weg naar een doel, maar zoekt in alle richtingen tegelijk, ook van het doel af. A*-zoeken voegt één stukje kennis toe, een schatting van hoe ver het doel nog is, en ineens gaat het zoeken recht op het doel af.
Het idee
Als je op een kaart een route zoekt, bekijk je wegen die van je bestemming af leiden niet even zorgvuldig als wegen die ernaartoe leiden. A*-zoeken doet hetzelfde. Elke knoop krijgt een score: de afstand vanaf de start tot nu toe, g, plus een schatting van de afstand die nog rest, h. Het zoeken gaat altijd verder vanaf de knoop met de laagste score, dus knopen in de richting van het doel komen eerst.
Stap voor stap
Geef de start afstand 0 en zet die in een wachtrij met score h(start). Herhaal: neem de knoop met de laagste score en maak de afstand definitief. Is het het doel, stop dan: wie de onthouden knopen terug volgt, krijgt het pad. Bereken anders voor elke buur die nog niet definitief is de afstand via deze knoop. Is die korter dan de afstand tot nu toe, verlaag die dan, onthoud deze knoop als de weg erheen en geef de buur als score de nieuwe afstand plus de schatting. Bij gelijke scores bereik je het doel meestal sneller als je eerst de knoop met de kleinste schatting neemt.
Een voorbeeld
Neem een start A en een doel D. A–B is 2 lang en B–D 2, terwijl A–C 1 is en C–D 5. De hemelsbrede schattingen naar D zijn 3 vanaf A, 2 vanaf B en 3 vanaf C. A begint met score 0 + 3 = 3. A nemen geeft B de score 2 + 2 = 4 en C de score 1 + 3 = 4. Bij gelijke stand neemt A* B, de knoop met de kleinere schatting, en B geeft D de score 4 + 0 = 4. D heeft nu de laagste score met de kleinste schatting en wordt dus genomen: het kortste pad is A → B → D, met lengte 4, en C, dat de verkeerde kant op leidt, wordt nooit definitief. Het algoritme van Dijkstra had C eerst definitief gemaakt, omdat dat de knoop is die het dichtst bij A ligt.
Een goede schatting
De schatting mag nooit langer zijn dan de echte afstand tot het doel; zo'n schatting heet toelaatbaar, en daarmee vindt A* altijd een kortste pad. De rechte lijn is toelaatbaar, want geen route is korter dan een rechte lijn. Als de schatting van de ene knoop naar de volgende ook nooit meer daalt dan de lengte van de kant, is ze consistent, en hoeft geen definitieve knoop ooit opnieuw bekeken te worden. Hoe dichter de schatting bij de werkelijkheid ligt, hoe minder knopen A* nodig heeft. Een schatting van 0 is toelaatbaar maar nutteloos: A* wordt dan het algoritme van Dijkstra. Een te grote schatting maakt A* sneller, maar kan het kortste pad missen.
Geschiedenis en toepassingen
Peter Hart, Nils Nilsson en Bertram Raphael van het Stanford Research Institute publiceerden A* in 1968, terwijl ze werkten aan Shakey, een van de eerste mobiele robots. Hun eerdere versies heetten A1 en A2; de ster markeerde de versie waarvan ze bewezen dat die optimaal was. Tegenwoordig laat A* personages in videogames om obstakels heen lopen, plant het routes en robotbewegingen, en lost het puzzels op zoals de 15-puzzel, waar de schatting optelt hoe ver elke steen van zijn plek ligt.
Zelf proberen
Open de app en druk op Stap. De getallen op de kanten zijn hun lengtes, die hier overeenkomen met hoe lang ze getekend zijn, en de stippellijn toont de hemelsbrede schatting naar het doel. De wachtrij onder de graaf zet de knopen op score, laagste eerst. Als het doel definitief is, vergelijkt de statusregel hoeveel knopen A* definitief maakte met hoeveel het algoritme van Dijkstra nodig zou hebben gehad. Kies een doel in een verre hoek van een grote graaf om het grootste verschil te zien.
Veelgestelde vragen
Wat betekent de ster in A*?
Hart, Nilsson en Raphael beschreven eerst algoritmen die ze A1 en A2 noemden. A* ("A-ster") was de versie waarvan ze bewezen dat die een kortste pad vindt en daarbij, onder vergelijkbare algoritmen met dezelfde schatting, de minste knopen uitwerkt, als de schatting consistent is.
Wat is de tijdcomplexiteit van A*?
In het slechtste geval, met een nutteloze schatting, doet A* hetzelfde werk als het algoritme van Dijkstra: O((V + E) log V) met een binaire heap. Met een goede schatting maakt het maar een fractie van de knopen definitief, en daarom is het in de praktijk snel.
Wat maakt een goede heuristiek voor A*?
Ze moet snel te berekenen zijn, de echte afstand nooit overschatten en er zo dicht mogelijk bij liggen. Op een rooster waar je alleen omhoog, omlaag, naar links en naar rechts kunt, is de Manhattan-afstand een gangbare keus; op een kaart de hemelsbrede afstand.
Wat als de heuristiek overschat?
Dan kan A* een pad teruggeven dat niet het kortste is, omdat het klaar kan zijn voordat het de betere route heeft bekeken. Sommige programma's doen dit bewust (gewogen A*) om een beetje padkwaliteit te ruilen voor veel snelheid.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer A*-zoeken