A*-sökning

Dijkstras algoritm hittar den kortaste vägen till ett mål, men den letar åt alla håll på en gång, även bort från målet. A*-sökning lägger till en enda kunskap, en gissning av hur långt det är kvar till målet, och plötsligt styr sökningen rakt mot det.

En graf där de slutgiltiga noderna bildar ett smalt band från starten mot målet, med en streckad rak linje som pekar mot målet och en kö ritad under
En graf där de slutgiltiga noderna bildar ett smalt band från starten mot målet, med en streckad rak linje som pekar mot målet och en kö ritad under

Idén

När du letar efter en väg på en karta undersöker du inte vägar som leder bort från målet lika noga som vägar som leder mot det. A*-sökning gör likadant. Varje nod får en poäng: avståndet från starten hittills, g, plus en gissning av avståndet som återstår, h. Sökningen fortsätter alltid från noden med lägst poäng, så noder som ligger mot målet kommer först.

Steg för steg

Ge starten avstånd 0 och lägg den i en kö med poängen h(start). Upprepa: ta noden med lägst poäng och gör dess avstånd slutgiltigt. Om det är målet, sluta: följer du de sparade noderna bakåt får du vägen. Annars, för varje granne som inte är slutgiltig, räkna ut dess avstånd via den här noden. Om det är kortare än grannens avstånd hittills, sänk det, kom ihåg den här noden som vägen dit och ge grannen poängen för sitt nya avstånd plus sin gissning. När två poäng är lika når man oftast målet snabbare om man först tar noden med minst gissning.

Ett exempel

Ta en start A och ett mål D. A–B är 2 lång och B–D 2, medan A–C är 1 och C–D 5. Gissningarna fågelvägen till D är 3 från A, 2 från B och 3 från C. A börjar med poängen 0 + 3 = 3. Att ta A ger B poängen 2 + 2 = 4 och C poängen 1 + 3 = 4. Vid lika poäng tar A* B, noden med minst gissning, och B ger D poängen 4 + 0 = 4. D har nu lägst poäng med minst gissning, så den tas: den kortaste vägen är A → B → D, med längd 4, och C, som leder åt fel håll, blir aldrig slutgiltig. Dijkstras algoritm skulle ha gjort C slutgiltig först, eftersom den är den nod som ligger närmast A.

En bra gissning

Gissningen får aldrig vara längre än det verkliga avståndet till målet; en sådan gissning kallas tillåten, och med den hittar A* alltid en kortaste väg. Den raka linjen är tillåten eftersom ingen väg är kortare än en rak linje. Om gissningen dessutom aldrig sjunker mer än en kants längd från en nod till nästa är den konsistent, och ingen slutgiltig nod behöver någonsin ses på igen. Ju närmare sanningen gissningen ligger, desto färre noder behöver A*. Gissningen 0 är tillåten men värdelös: då blir A* Dijkstras algoritm. En för stor gissning gör A* snabbare men kan missa den kortaste vägen.

Historia och användning

Peter Hart, Nils Nilsson och Bertram Raphael vid Stanford Research Institute publicerade A* 1968, medan de arbetade med Shakey, en av de första mobila robotarna. Deras tidigare versioner hette A1 och A2; stjärnan markerade den version som de bevisade var optimal. I dag flyttar A* figurer runt hinder i datorspel, planerar rutter och robotrörelser och löser pussel som 15-spelet, där gissningen summerar hur långt varje bricka är från sin plats.

Shakey, Stanford Research Institutes mobila robot, fotograferad på Computer History Museum. Peter Hart, Nils Nilsson och Bertram Raphael publicerade A* 1968 medan de arbetade med den.
Shakey, Stanford Research Institutes mobila robot, fotograferad på Computer History Museum. Peter Hart, Nils Nilsson och Bertram Raphael publicerade A* 1968 medan de arbetade med den.

Utforska själv

Öppna appen och tryck på Steg. Talen på kanterna är deras längder, som här stämmer med hur långa de är ritade, och den streckade linjen visar gissningen fågelvägen till målet. Kön under grafen listar noderna efter poäng, lägst först. När målet är slutgiltigt jämför statusraden hur många noder A* gjorde slutgiltiga med hur många Dijkstras algoritm skulle ha behövt. Prova ett mål i ett avlägset hörn av en stor graf för att se den största skillnaden.

Ofta ställda frågor

Vad betyder stjärnan i A*?

Hart, Nilsson och Raphael beskrev först algoritmer som de kallade A1 och A2. A* ("A-stjärna") var den version som de bevisade hittar en kortaste väg och expanderar minst antal noder bland jämförbara algoritmer med samma gissning, när gissningen är konsistent.

Vilken tidskomplexitet har A*?

I värsta fall, med en värdelös gissning, gör A* samma arbete som Dijkstras algoritm: O((V + E) log V) med en binär heap. Med en bra gissning gör den bara en bråkdel av noderna slutgiltiga, och därför är den snabb i praktiken.

Vad är en bra heuristik för A*?

Den ska gå snabbt att räkna ut, aldrig överskatta det verkliga avståndet och ligga så nära det som möjligt. På ett rutnät där man bara kan gå upp, ner, vänster och höger är manhattanavståndet ett vanligt val; på en karta avståndet fågelvägen.

Vad händer om heuristiken överskattar?

Då kan A* returnera en väg som inte är den kortaste, eftersom den kan bli klar innan den har tittat på den bättre vägen. Vissa program gör så med flit (viktad A*) för att byta lite vägkvalitet mot mycket fart.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Prova A*-sökning