- Aktuell
- I kön
- Slutgiltiga
- Väg
- Gissning fågelvägen
A*-sökning
A*-sökning hittar en kortaste väg från en start till ett mål, precis som Dijkstras algoritm, men den vet ungefär var målet ligger. Varje nod får en gissning av avståndet som återstår, den raka linjen till målet, och sökningen fortsätter alltid från noden med lägst avstånd hittills plus den gissningen. Klicka på en nod för att starta där, välj ett mål och stega igenom för att se sökningen styra mot målet och lämna hela hörn av grafen orörda. Tryck på Spela för att se sökningen, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst. Klicka på en nod för att göra den till start; byt klicket till Mål och klicka på en annan nod för att göra den till mål. Talet på varje kant är dess längd, talet på varje nod dess avstånd hittills, och den streckade linjen gissningen fågelvägen av avståndet som återstår. Raden under grafen är kön, lägst poäng först, med varje nods poäng: avståndet hittills plus gissningen. Ny graf skapar en annan graf; välj hur många noder och kanter den har. När brädet är markerat stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Klicka på en nod för att göra den till start. Byt klicket till Mål och klicka på en annan nod för att göra den till mål.
- Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst i sökningen.
- Följ poängen i kön och den streckade gissningen fågelvägen. Jämför till sist hur många noder A* behövde med Dijkstras algoritm.
Så fungerar A*-sökning
Ge starten avstånd 0 och lägg den i en kö. Varje nod i kön har en poäng: dess avstånd hittills plus en gissning av avståndet som återstår. Upprepa: ta noden med lägst poäng och gör dess avstånd slutgiltigt. Om det är målet, sluta. Annars, för varje granne som inte är slutgiltig, lägg kantens längd till nodens avstånd; om det är kortare än grannens avstånd hittills, sänk det, kom ihåg noden som vägen dit och lägg grannen i kön med sin nya poäng.
Varför gissningen aldrig får vara för lång
A* hittar en kortaste väg så länge gissningen aldrig säger att målet ligger längre bort än det verkligen gör: en tillåten gissning. Den raka linjen är en sådan, eftersom ingen väg mellan två platser är kortare än den raka linjen. En för lång gissning kan få A* att hoppa över den bästa vägen; gissningen 0 överallt gör A* till Dijkstras algoritm, som är säker men letar åt alla håll. Ju bättre gissning, desto färre noder behöver A*. I appen är varje kant lika lång som den är ritad, avrundat uppåt, så den raka linjen är en säker gissning.
Ofta ställda frågor
Vad är A*-sökning?
En vägsökningsalgoritm som hittar en kortaste väg från en start till ett mål. Den fungerar som Dijkstras algoritm, men ordnar sin kö efter avståndet hittills plus en gissning av avståndet som återstår, så att den styr mot målet i stället för att breda ut sig åt alla håll.
Vad är en tillåten heuristik?
En gissning av avståndet till målet som aldrig är längre än det verkliga kortaste avståndet. Med en tillåten gissning hittar A* alltid en kortaste väg. Avståndet fågelvägen på en karta är det klassiska exemplet.
Är A* snabbare än Dijkstras algoritm?
Oftast, när du behöver vägen till ett enda mål och har en bra gissning: A* gör färre noder slutgiltiga, eftersom noder som ligger bort från målet får höga poäng. Med gissningen 0 gör den exakt samma sak som Dijkstras algoritm. Dijkstras algoritm är det bättre valet när du behöver avstånden till alla noder.
Var används A*?
I datorspel för att flytta figurer runt hinder, i ruttplanerare, i planering av robotrörelser och i program som löser pussel som 15-spelet, där gissningen räknar hur långt brickorna är från sina platser.
Skickas min graf någonstans?
Nej. Grafen skapas och genomsöks i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor