Definitief
In de wachtrij
Bekeken kanten

  • Huidig
  • In de wachtrij
  • Definitief
  • Pad
  • Hemelsbrede schatting
Een klik op een knoop kiest

Meer over A*-zoeken

A*-zoeken

A*-zoeken vindt een kortste pad van een start naar een doel, net als het algoritme van Dijkstra, maar weet ongeveer waar het doel ligt. Elke knoop krijgt een schatting van de afstand die nog rest, de rechte lijn naar het doel, en het zoeken gaat altijd verder vanaf de knoop met de laagste afstand tot nu toe plus die schatting. Klik op een knoop om daar te beginnen, kies een doel en ga stap voor stap om te zien hoe het zoeken op het doel afgaat en hele hoeken van de graaf onaangeroerd laat. Druk op Afspelen om het zoeken te volgen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen. Klik op een knoop om die de start te maken; zet de klik op Doel en klik op een andere knoop om die het doel te maken. Het getal op elke kant is de lengte ervan, het getal op elke knoop de afstand tot nu toe, en de stippellijn de hemelsbrede schatting van de afstand die nog rest. De rij onder de graaf is de wachtrij, laagste score eerst, met bij elke knoop de score: de afstand tot nu toe plus de schatting. Nieuwe graaf maakt een andere graaf; kies hoeveel knopen en kanten die heeft. Als het bord geselecteerd is, gaan de pijltjestoetsen een stap verder of terug, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het einde.

Hoe het werkt

  1. Klik op een knoop om die de start te maken. Zet de klik op Doel en klik op een andere knoop om die het doel te maken.
  2. Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om naar elk punt in het zoeken te springen.
  3. Volg de scores in de wachtrij en de gestippelde hemelsbrede schatting. Vergelijk aan het eind hoeveel knopen A* nodig had met het algoritme van Dijkstra.

Hoe A*-zoeken werkt

Geef de start afstand 0 en zet die in een wachtrij. Elke knoop in de wachtrij heeft een score: de afstand tot nu toe plus een schatting van de afstand die nog rest. Herhaal: neem de knoop met de laagste score en maak de afstand definitief. Is het het doel, stop dan. Tel anders voor elke buur die nog niet definitief is de lengte van de kant op bij de afstand van de knoop; is dat korter dan de afstand van de buur tot nu toe, verlaag die dan, onthoud de knoop als de weg erheen en zet de buur in de wachtrij met de nieuwe score.

Waarom de schatting nooit te lang mag zijn

A* vindt een kortste pad zolang de schatting het doel nooit verder weg noemt dan het echt is: een toelaatbare schatting. De rechte lijn is er een, want geen weg tussen twee plekken is korter dan de rechte lijn. Een te lange schatting kan A* de beste route laten overslaan; een schatting van 0 overal maakt van A* het algoritme van Dijkstra, dat veilig is maar in alle richtingen zoekt. Hoe beter de schatting, hoe minder knopen A* nodig heeft. In de app is elke kant zo lang als hij getekend is, naar boven afgerond, dus de rechte lijn is een veilige schatting.

Veelgestelde vragen

Wat is A*-zoeken?

Een padvindingsalgoritme dat een kortste pad van een start naar een doel vindt. Het werkt als het algoritme van Dijkstra, maar ordent de wachtrij op de afstand tot nu toe plus een schatting van de afstand die nog rest, zodat het op het doel afgaat in plaats van zich in alle richtingen uit te breiden.

Wat is een toelaatbare heuristiek?

Een schatting van de afstand tot het doel die nooit langer is dan de echte kortste afstand. Met een toelaatbare schatting vindt A* altijd een kortste pad. De hemelsbrede afstand op een kaart is het klassieke voorbeeld.

Is A* sneller dan het algoritme van Dijkstra?

Meestal wel, als je de weg naar één doel zoekt en een goede schatting hebt: A* maakt minder knopen definitief, omdat knopen die van het doel af liggen hoge scores krijgen. Met een schatting van 0 doet het precies hetzelfde als het algoritme van Dijkstra. Het algoritme van Dijkstra is de betere keus als je de afstanden tot alle knopen nodig hebt.

Waar wordt A* gebruikt?

In videogames om personages om obstakels heen te laten lopen, in routeplanners, bij het plannen van robotbewegingen en in puzzeloplossers, bijvoorbeeld voor de 15-puzzel, waar de schatting telt hoe ver de stenen van hun plek liggen.

Wordt mijn graaf ergens heen gestuurd?

Nee. De graaf wordt in je browser gemaakt en doorzocht, en je laatste instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor